疾速排序
- 算法思维
疾速排序的根本思维：通过一趟排序将待排记录分隔成独立的两局部，其中一部分记录的关键字均比另一部分的关键字小，则可别离对这两局部记录持续进行排序，以达到整个序列有序。
- 实现原理
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)
稳定性：不稳固