算法---一种简单的思路理解快速排序(附源码)

前言

说起快速排序,可能是一个很基础的排序了,不管是不是第一次听到这个词,还是听过但是没有试过,或者没有理
解过。都希望今天你读完这篇文章能够加深理解。不懂的话希望你能懂,懂了的话希望你能多一种思路来理解。

思路

有一个数组,里面的数字分别是{3, 9, 4, 2, 5, 8, 7, 6, 1},然后请你用快速排序实现把数组从小到大的顺序排列好。
我用图的方法演示来看,更便于理解。

如下:

下面开始讲思路了:
我们先找最中间的5,把它固定住,也可以理解为以5为基准。
然后我们在剩下的8个数字里面把比5小的放到5左面。
然后把比5大的放到5的右面。

首先我们从前往后看,用一个箭头表示我们程序当前走到了哪个位置
第一步:a箭头指向第一个数字,第一个数字是3,3 < 5,所以3其实不用动。
第二步:a箭头指向了第二个数字,第二个数字是9,9 > 5,所以9其实应该是放到5的右边的。

那么问题来了,9这个数字放到5的右边,具体要放到第几位的?

这个时候,我们要是从5的右边找一个比5小的,然后和刚刚的那个数字调换,是不是就正好可以了。
那我们从右侧开始找,
第一步:b箭头指向第一个数字,右侧第一个数字是1,1 < 5,所以1应该放到5的左边。

想想刚刚我们从左边找到了9,右边找到了1,然后将他俩互换,如下

结果如下

上面这个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不用动,箭头指向前一个位置

经过了上面的一系列操作,我们得到了如下的数组。

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方法,

为了方便大家阅读,我把方法贴到下面

本文说的思路

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
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);
}

标准思路

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
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的小站

博客:hanhan12312的专栏

知乎:MartinHan01