前言
说起快速排序，可能是一个很基础的排序了，不管是不是第一次听到这个词，还是听过但是没有试过，或者没有理
解过。都希望今天你读完这篇文章能够加深理解。不懂的话希望你能懂，懂了的话希望你能多一种思路来理解。
思路
有一个数组，里面的数字分别是{3, 9, 4, 2, 5, 8, 7, 6, 1}，然后请你用快速排序实现把数组从小到大的顺序排列好。
我用图的方法演示来看，更便于理解。
如下：
<img src="http://martinhan.site/images/list1.jpeg" width="568" height="42">
下面开始讲思路了：
我们先找最中间的5，把它固定住，也可以理解为以5为基准。
然后我们在剩下的8个数字里面把比5小的放到5左面。
然后把比5大的放到5的右面。
首先我们从前往后看，用一个箭头表示我们程序当前走到了哪个位置
第一步：a箭头指向第一个数字,第一个数字是3，3 < 5，所以3其实不用动。
第二步：a箭头指向了第二个数字，第二个数字是9，9 > 5，所以9其实应该是放到5的右边的。
那么问题来了，9这个数字放到5的右边，具体要放到第几位的？
<img src="http://martinhan.site/images/list2.jpeg" width="568" height="176">
这个时候，我们要是从5的右边找一个比5小的，然后和刚刚的那个数字调换，是不是就正好可以了。
那我们从右侧开始找，
第一步：b箭头指向第一个数字，右侧第一个数字是1，1 < 5，所以1应该放到5的左边。
想想刚刚我们从左边找到了9，右边找到了1，然后将他俩互换，如下
<img src="http://martinhan.site/images/list3.jpeg" width="568" height="107">
结果如下
<img src="http://martinhan.site/images/list4.jpeg" width="568" height="170">
上面这个a和b是我们刚刚说的，我们两个箭头指向的位置，然后这次我们继续从左侧找一个比5大的数字停下
第一步：a箭头指向了4，4 < 5，所以4不用动，箭头指向下一个位置
第二步：a箭头指向了2，2 < 5，所以2不用动，箭头指向下一个位置
第三步：a箭头指向了5，5 = 5, 所以箭头指到5的时候需要等一等，此时此刻，虽然5的左边肯定都小于5了，可是5右边的数字万一要是还有小于5的呢，5还是需要往右移动的
第四步：b箭头当前指向6，6 > 5，所以6不用动，箭头指向前一个位置
第五步：b箭头指向了7，7 > 5，所以7不用动，箭头指向前一个位置
第六部：b箭头指向了8，8 > 5，所以8不用动，箭头指向前一个位置
经过了上面的一系列操作，我们得到了如下的数组。
<img src="http://martinhan.site/images/list5.jpeg" width="568" height="161">
a和b现在都指向了我们这个基准的数字5。
现在我们这么想，已经把比5小的都排列到了5的左边，比5大的都排列到了5的右边。
现在我们把数组堪称两部分，
左半部分：3 1 4 2
右半部分：8 7 6 9
我们依次类推：
根据刚刚的规则，我们把上面的一系列操作再分别排序左半部分和右半部分。
然后用我们刚刚所使用的规则再进行排序。
其实这就是大概快速排序的思路了。
标准思路
说完了我写一下标准思路。其实称之为标准思路，原因就是书本上大概都讲的这个，好多老师也上来就讲的这个。
还以3 1 4 2 5 8 7 6 9为例，我们开始做的是以5为基准，其实标准思路就是以1为基准的了。
源码下载
本文所讲的思路是源码中的QuickSortMiddleBase方法
标准思路是QuickSort方法，
为了方便大家阅读，我把方法贴到下面
本文说的思路
void QuickSortMiddleBase(int array[], int begin, int end) {
if(begin >= end) {
return ;
}
int base_pos = (begin + end) / 2;
int base_value = array[base_pos];
int left_pos = begin, right_pos = end;
int temp_val;
while(left_pos != right_pos) {
while(array[left_pos] < base_value && left_pos <= right_pos) {
left_pos++;
}
while(array[right_pos] > base_value && right_pos >= left_pos) {
right_pos--;
}
if(left_pos <= right_pos) {
temp_val = array[left_pos];
array[left_pos] = array[right_pos];
array[right_pos] = temp_val;
}
}
array[left_pos] = base_value;
PrintArray(array, 9);
QuickSortMiddleBase(array, begin, left_pos - 1);
QuickSortMiddleBase(array, left_pos + 1, end);
}
标准思路
void QuickSort(int array[], int begin, int end) {
if(begin >= end) {
return ;
}
int base_pos = begin;
int base_value = array[base_pos];
int left_pos = begin, right_pos = end;
int temp_val;
while(left_pos != right_pos) {
while(array[left_pos] < base_value && left_pos < right_pos) {
left_pos++;
}
while(array[right_pos] > base_value && left_pos < right_pos) {
right_pos--;
}
if(left_pos < right_pos) {
temp_val = array[left_pos];
array[left_pos] = array[right_pos];
array[right_pos] = temp_val;
}
}
//array[left_pos] = base_value;
//array[base_pos] = temp_val;
printf("sort result:");
PrintArray(array, 9);
QuickSort(array, begin, left_pos);
QuickSort(array, left_pos + 1, end);
}
写在最后
克服懒惰，争取从一个看心情更的博主，做一个周更的博主~
关于我
个人网站：MartinHan的小站
知乎：MartinHan01
网友评论