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

  1. 前言
  2. 思路
  3. 标准思路
  4. 源码下载
  5. 写在最后
  6. 关于我

前言

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

思路

有一个数组,里面的数字分别是{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方法,

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

本文说的思路

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

博客:hanhan12312的专栏

知乎:MartinHan01


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 jaytp@qq.com

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

文章字数:1.3k

本文作者:MartinHan

发布时间:2018-03-12, 22:07:00

最后更新:2020-03-30, 19:29:09

原始链接:http://cpphello.com/2018-03-12/%E7%AE%97%E6%B3%95---%E4%B8%80%E7%A7%8D%E7%AE%80%E5%8D%95%E7%9A%84%E6%80%9D%E8%B7%AF%E7%90%86%E8%A7%A3%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F(%E9%99%84%E6%BA%90%E7%A0%81).html

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏

github