快速排序原理记录及实现，用了几张图示，虽然是篇笔记，但尽力让所有人明白。
快速排序的原理就是一个数组在单趟的排序中，找到一个基准值，按这个基准值的所在的位置做为分界（下标），这趟排序保证的就是这个基准值位置的左边都是小于（或者大于）基准值的数，而基准值位置的右边都是大于（或者小于）基准值的数，然后再从数组的右边开始扫描，把每个值依次与基准值相比较，大于（或者小于）基准值的值不动，小于（或者大于）基准值的就移到左边，再开始从左边开始扫描， 仍然是把每个值与基准值比较，小于（或者大于）基准值的值不动，大于（或者小于）基准值的值移到右边，接着再进行右边扫描，直到二个扫描下标相遇，这趟排序就完成了，然后再按这个基准值的位置（下标），把这个数组分为左半边与右半边，然后再次使用上面的策略进行排序，这就是快速排序的基本原理，按我的理解就是每一趟的排序找到这个基准值的准确位置（每次确定一个值的排序好之后的位置）。下面看图，一个原始数组，一个左侧的扫描指针，一个右侧的扫描指针，一个基准值，就定为数组0位置的值：
最开始的数组情况就是这样的。（下面的举例是按数组排序从小到大演示），下面开始第一趟排序，就是如上面所说，右侧扫描指针从右侧开始向左移动，并依次取出对应下标的值与基准做比较，如果值大于基准值，指针向左移，过程就是：
第一次：array[10] > 2,指针向左移。
第二次：array[9] > 2, 指针向左移。
第三次：array[8] > 2, 指针向左移。
第四次：array[7] > 2, 指针向左移。
第五次：array[6] < 2, 第五次的时候，对应下标的值不再大于基准值，那么就开始移动这个值到左侧，接下来的数组就是这样：
下面开始左侧指针移动，并依次取出下标对应的值与基准值做比较，如果小于基准值，指针向右移动，如果大于基准值，那么就开始移动这个值到右侧，过程就是：
第一次：array[0] < 2, 指针右移。
第二次：array[1] > 10, 此次左侧指针下取出的值大于基准值2，那么开始把这个值移动到右侧，数组就变成这样：
左侧移动完成，下面又开始移动右侧，如上所述，大于基准值就左移，直到遇到小于基准值的位置，过程如下：
第一次：array[6] > 2, 指针左移。
第二次：array[5] > 2, 指针左移。
第三次：array[4] > 2, 指针左移。
第四次：array[3] > 2, 指针左移。
第五次：array[2] < 2, 此时指针下取出的值小于基准值，这个值要移动到左侧，数组情况如下：
再次开始移动左侧，小于基准值不动，大于基准值向右移，过程如下：
第一次：array[1] < 2, 指针右移。
第二次：array[2], 此时右侧指针也在array[2]处，此趟排序调整到此完成。
二个指针相遇的地方也就是开始确定基准值应该所在的位置，这趟排序过后数组变成：
也就是像上面所说的，每趟的排序都会把排序好之后的基准值的位置找到。
这是第一趟排序，下面就是使用分治，分别对现在基准值的位置的左半部分与右关部分运用像上面一样的策略来分别排序。
那么根据此原理就可以写出代码，如下：
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
void quick_sort(int *array, int low, int high)
{
//保证是左右二个部分
if (low < high)
{
int left = low;
int right = high;
//找到基准值
int base_value = array[low];
// 确定每次移动都是左侧与右侧不交叉
while (left < right)
{
//右侧指针向左移动
while (left < right && base_value <= array[right])
{
right--;
}
//找到了小于基准值的值，直接移动左侧
array[left] = array[right];
//开始左侧扫描
while (left < right && base_value >= array[left])
{
left++;
}
//找到大于基准值的值，直接移动到右侧
array[right] = array[left];
}
//二个指针相遇，base_value值位置找到
array[left] = base_value;
//按base_value所在位置分别按上面的策略进行分别处理
quick_sort(array, low, left - 1);
quick_sort(array, left + 1, high);
}
}
int main(int argc, char *argv[])
{
int unsort_array[10] = {1, 0, 10, 9, 23, -1, 3, 19, 89, 11};
quick_sort(unsort_array, 0, 9);
for (int i = 0; i < 10; i++)
{
printf("%d\n", unsort_array[i]);
}
return 0;
}这就是快速排序的基本原理与实现图解与代码。