疾速排序
- 算法思维
疾速排序的根本思维：通过一趟排序将待排记录分隔成独立的两局部，其中一部分记录的关键字均比另一部分的关键字小，则可别离对这两局部记录持续进行排序，以达到整个序列有序。
- 实现原理
2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
2.2、整个数组找基准正确地位，所有元素比基准值小的摆放在基准后面，所有元素比基准值大的摆在基准的前面
- 默认数组的第一个数为基准数据，赋值给key，即key=array[low]。
- 因为默认数组的第一个数为基准，所以从前面开始向前搜寻（high–），找到第一个小于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。（循环条件是 array[high] >= key；完结时 array[high] < key）
- 此时从后面开始向后搜寻（low++），找到第一个大于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。（循环条件是 array[low] <= key；完结时 array[low] > key）
- 循环 2-3 步骤，直到 low=high，该地位就是基准地位。
- 把基准数据赋给以后地位。
2.3、第一趟找到的基准地位，作为下一趟的分界点。
2.4、递归调用（recursive）分界点前和分界点后的子数组排序，反复2.2、2.3、2.4的步骤。
2.5、最终就会失去排序好的数组。
- 动静演示
- 残缺代码
三个函数
基准插入函数：int getStandard(int array[],int low,int high)
（返回基准地位下标）
递归排序函数：void quickSort(int array[],int low,int high)
主函数：int main()
`#include <stdio.h>#include <stdlib.h>void display(int* array, int size) { for (int i = 0; i < size; i++) { printf("%d ", array[i]); } printf("n");}int getStandard(int array[], int i, int j) { // 基准数据 int key = array[i]; while (i < j) { // 因为默认基准是从右边开始，所以从左边开始比拟 // 当队尾的元素大于等于基准数据 时,就始终向前移动 j 指针 while (i < j && array[j] >= key) { j--; } // 当找到比 array[i] 小的时，就把前面的值 array[j] 赋给它 if (i < j) { array[i] = array[j]; } // 当队首元素小于等于基准数据 时,就始终向后移动 i 指针 while (i < j && array[i] <= key) { i++; } // 当找到比 array[j] 大的时，就把后面的值 array[i] 赋给它 if (i < j) { array[j] = array[i]; } } // 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引地位 // 把基准数据赋给正确地位 array[i] = key; return i;}void QuickSort(int array[], int low, int high) { // 开始默认基准为 low if (low < high) { // 分段地位下标 int standard = getStandard(array, low, high); // 递归调用排序 // 右边排序 QuickSort(array, low, standard - 1); // 左边排序 QuickSort(array, standard + 1, high); }}// 合并到一起疾速排序// void QuickSort(int array[], int low, int high) {// if (low < high) {// int i = low;// int j = high;// int key = array[i];// while (i < j) {// while (i < j && array[j] >= key) {// j--;// }// if (i < j) {// array[i] = array[j];// }// while (i < j && array[i] <= key) {// i++;// }// if (i < j) {// array[j] = array[i];// }// }// array[i] = key;// QuickSort(array, low, i - 1);// QuickSort(array, i + 1, high);// }// }int main() { int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10}; int size = sizeof(array) / sizeof(int); // 打印数据 printf("%d n", size); QuickSort(array, 0, size - 1); display(array, size); // int size = 20; // int array[20] = {0}; // 数组初始化 // for (int i = 0; i < 10; i++) { // 数组个数 // for (int j = 0; j < size; j++) { // 数组大小 // array[j] = rand() % 1000; // 随机生成数大小 0~999 // } // printf("原来的数组："); // display(array, size); // QuickSort(array, 0, size - 1); // printf("排序后数组："); // display(array, size); // printf("n"); // } return 0;}` * 1* 2* 3* 4* 5* 6* 7* 8* 9* 10* 11* 12* 13* 14* 15* 16* 17* 18* 19* 20* 21* 22* 23* 24* 25* 26* 27* 28* 29* 30* 31* 32* 33* 34* 35* 36* 37* 38* 39* 40* 41* 42* 43* 44* 45* 46* 47* 48* 49* 50* 51* 52* 53* 54* 55* 56* 57* 58* 59* 60* 61* 62* 63* 64* 65* 66* 67* 68* 69* 70* 71* 72* 73* 74* 75* 76* 77* 78* 79* 80* 81* 82* 83* 84* 85* 86* 87* 88* 89* 90* 91* 92* 93* 94* 95* 96* 97* 98* 99* 100* 101* 102- 后果展现
（递归调用，不好展现每次排序后果）
- 算法剖析
工夫复杂度：
- 最好：O ( n l o g 2 n ) O(n log_{2} n)O(nlog2n)
- 最坏：O ( n 2 ) O(n^2)O(n2)
- 均匀：O ( n l o g 2 n ) O(n log_{2} n)O(nlog2n)
空间复杂度：O ( n l o g 2 n ) O(n log_{2} n)O(nlog2n)
稳定性：不稳固