网站开发所用到的技术,最近三天的新闻大事简短,wordpress文本组件使用,中国航发网上商城首页C语言——快速排序 一、 含义二、算法思想三、实现步骤代码实现 一、 含义
快速排序算法是在几种排序算法中效率最高的一个排序算法了#xff0c;故称为快速排序#xff0c;它的时间复杂度为#xff1a;O(nlog2n)#xff0c;相比冒泡排序算法的O(n2)有很大的提升。
二、算… C语言——快速排序 一、 含义二、算法思想三、实现步骤代码实现 一、 含义
快速排序算法是在几种排序算法中效率最高的一个排序算法了故称为快速排序它的时间复杂度为O(nlog2n)相比冒泡排序算法的O(n2)有很大的提升。
二、算法思想
1、选取一个基准元素(一般我们将待排序序列中的第一个元素选取为基准元素) 2、将其他元素与基准元素进行比较比基准元素大的放到基准元素的右边比基准元素小的放到基准元素的右边。(以基准元素为中心将元素重新分成两个序列并返回基准元素的下标) 3、将新生成的两个序列继续执行1和2两步(此处可以用递归实现)
三、实现步骤
快速排序的算法步骤 1.丛数列中挑出一个元素一般都是左边的第一个数字称为基准数 2.创建两个指针一个从前往后走一个从后往前走 3.先执行后面的指针找出第一个比基准数小的数字 4.在执行后面的指针找出第一个比基准数大的数字 5.交换两个指针指向的数字 6.直到两个指针相遇 7.将基准数跟指针指向的位置的数字交换位置称之为基准数归位 8.第一轮结束后基准数左边的数字都是比基准数小的基准数右边的数字都是比基准数大的 9.把基准数左边的看作是一个序列把基准数右边的看作一个序列按照刚刚的规则进行递归排序
代码实现
int main()
{int arr[10] {9,5,3,8,1,2,6,7,4,10};void quicksort(int a[10],int i,int j); //函数的声明printf(排列前:);for(int i 0; i 10;i){printf(%d ,arr[i]);}printf(\n);quicksort(arr,0,9); //调用函数printf(排列后);for(int i 0; i 10;i){printf(%d ,arr[i]);}system(pause);return 0;
}void quicksort(int a[10],int first,int end)
{if(first end) //递归结束条件{return;}int i first,j end,flag a[i],exchange 0;while(i ! j){while(i j a[j] flag)//只找小的等于要过滤找前判断right有没有走过{j--;}while(i j a[i] flag){i;}if(j i){exchange a[i];a[i] a[j];a[j] exchange;}}a[first] a[i];a[i] flag;quicksort(a,first,i - 1);quicksort(a,i 1,end);
}总结快速排序优点排列速度快比较简单缺点不稳定如果数组是递增的有序数组对它用快速排序需要N^2/2次操作。
