快速排序算法
2021-01-07 10:30
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。
算法是：
1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与key交换；（我看有的小伙伴会问为什么要从右开始，不从左开始。因为我们一般是选取第一个数即最左边的数字作为关键元素，也就是基准数，其余的都要与它相比较，所以就是从最后一个数字即最右边开始比较）
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与key交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。
找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。)
来实践一下吧：（都跟基准数去比较）
也有小伙伴会说，为什么第一个数字这么恰巧就是最中间的数呢？其实在设计这组数据我也是故意这样设置的，看起来比较方便（最优情况）。当然平时的数据，可不是让我们用上帝视角来解决的，但解决的方法都一样，一样的步骤。但是交换次数会多一些，但是总体时间复杂度相对还是比较低的（快速排序的平均时间复杂度也是：O(nlogn)；最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况。 最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况）。
|
排序法 |
最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
| 冒泡排序 | O(n2) | O(n2) | 稳定 | O(1) |
| 快速排序 | O(n2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
| 选择排序 | O(n2) | O(n2) | 不稳定 | O(1) |
| 二叉树排序 | O(n2) | O(n*log2n) | 不一顶 | O(n) |
|
插入排序 |
O(n2) | O(n2) | 稳定 | O(1) |
| 堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
| 希尔排序 | O | O | 不稳定 | O(1) |
实现代码：
#include// 打印数组 void print_array(int *array, int length) { int index = 0; printf("array:\n"); for(; index ){ printf(" %d,", *(array+index)); } printf("\n\n"); } void quickSort(int array[], int length) { int start = 0; int end = length-1; int value = array[start];// 得到哨兵元素 if (1 > length) return;// 递归出口 while(start // 以哨兵元素为标准，分成大于它和小于它的两列元素 while(start // 从数组尾部往前循环得到小于哨兵元素的一个元素 if ( array[end--] value ){ array[start++] = array[++end]; break; } } while( start // 从数组头部往后循环得到大于哨兵元素的一个元素 if( array[start++] > value){ array[end--] = array[--start]; break; } } } array[start] = value;// 放置哨兵元素 printf("\nstart:%d, end:%d\n", start, end);// 这个是测试下start和end是否一样 quickSort(array, start);// 递归排序小于哨兵元素的那一列元素 quickSort(array + start + 1, length - start - 1);// 递归排序大于哨兵元素的那一列 } int main(void) { int array[7] = {15,8,12,23,25,6,36}; print_array(array, 7);// 开始前打印下 quickSort(array, 7);// 快速排序 print_array(array, 7);// 排序后打印下 return 0; }