算法学习 - 快速排序

首先放上我学习快速排序的知识来源，得益于慕课网上的一位良师，波波老师，放上课程链接：coding.imooc.com/class/71.ht… 诚心推荐。另外波波老师在慕课网上还有很多优质的课程，关于python3机器入门学习, 玩转数据结构,玩转算法面试等等，都是精品，如果你需要这方面的学习资料，选择波波老师准没错，相信会对你有所帮助。波波老师让我佩服的是表达上的功力，能够用很清晰的语言把知识点讲述清楚，逻辑性强。

快速排序简介

快速排序算法被列为20世纪十大算法之一，由图灵奖的获得者Tony Hoare发明。

快速排序算法的实现

快速排序算法的实现思路和冒泡排序有相似之处，两者都是通过比较两个元素的大小来变动位置达到排序的目的。不同之处是两种排序方式拿来比较的两个元素不同，冒泡排序逐一比较相邻的两个元素的大小，每一轮遍历后确定最大或最小的元素。而快速排序是选取某一个元素值，让其他元素都与这一个固定的元素比较，假设是从小到大排序，那么比这个固定元素值小的放到它的左边，比这个固定元素值大的放到它的右边。然后分别对这两部分继续按照上述方法进行排序，最后使整体达到有序。

如下图所示：选取一个特定的元素V作为标定点,让小于V的元素在V的左边，让大于V的元素在V的右边。实现这个操作的过程被称为partition，能实现partition的方法有很多种，先讲最简单的方法。

代码实现(使用c++语言)

如下函数调用了一个子函数 __quickSort,这是一个递归函数。

template <typename T>
void quickSort(T arr[], int n){

    __quickSort(arr, 0, n-1);
}

这个递归函数的作用就是对要排序的数组的arr[l...r]区间范围内进行排序，注意是前闭后闭的区间。这个递归函数终止的条件是l >= r，当l >= r 时，区间[l...r]也就不存在要比较的元素了，直接return。如果l < r,就说明存在要排序的元素，往下看。接下来会调用__aprtition函数进行快速排序，这个函数会返回一个索引p,这个索引表示作为标定点在排好序后数组中的索引，在该元素前面的元素值比他小，在该元素后面的元素值比他大，所以接下来根据这个索引把该数组分成两个子数组，继续递归下去进行快速排序。

// 对arr[l...r]部分进行快速排序
template <typename T>
void __quickSort(T arr[], int l, int r){

    if( l >= r )
        return;

    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1 );
    __quickSort(arr, p+1, r);
}

这个函数就是快速排序的核心：partition操作。

1   template <typename T>
2   int __partition(T arr[],int l,int r){
3       T v = arr[l];
4     
5       int j = l;
6       for (int i = l + 1; i <= r; i++) {
7           if (arr[i] < v) {
8               swap(arr[j + 1],arr[i]);
9               j ++;
10          }
11      }
12      swap(arr[l],arr[j]);
13    
14      return j;
   }

partition函数要传入的三个参数：待排序的数组arr,待排序数组的起始元素的索引l,待排序数组的最后一个元素的索引r。
partition函数标定点的选择：选取传入数组的第一个元素，即：arr[l];

我们选取partition到某一部分的情况进行讲解，请看下图：

图中有一个变量j,我们给这个变量j的意义是在partition过程中小于V的区间中的最后一个元素，那么我们就可以根据j的定义确定小于v部分的范围为[l + 1...j]，注意是前闭后闭。给j这个变量赋初始值的时候应该赋值为i,这样刚开始未遍历时小于v的区间[l + 1...j] 也就是区间[l + 1...l],这样就可以保证未开始遍历时的小于v的区间内的元素一个也没有,请看partition过程中的第五行代码。

图中的i是循环排序过程中将要排序的索引，e是元素值。现在我们就比较e与表定点v的大小来将e放入合适的区间，放入合适的区间后，再维持区间的范围不变，分二种情况讨论，具体代码是partition过程中的第7行代码：

当e>=v时，需要将e放入图中绿色部分，此时只需要将i移到下一个元素，也就是i++,大于等于v的部分的区间依旧保持着[j+1...i-1];
当e<v时，需要将e放入图中黄色部分，此时将j+1位置的元素与e交换位置，然后再将j往后移动一个位置，维持小于v的部分的区间[l+1...j]不变，具体代码是partition过程中的第8，9行代码。

下面我们来讨论循环结束的条件，也就是当i <= r的时候，循环结束，具体代码是partition过程中的第6行代码，for循环中的循环终止条件。

循环结束后，排序的结果呈如下状态：这时候v还在数组的首元素位置。显然需要将v放到合适的位置。

我们可以将v与j对应的元素交换位置即可，请看partition过程中的第12行代码交换后如图：

此时v所在的位置就是他在整个数组中的位置，这一次递归结束，将j作为函数的返回值返回，依据j的值，继续将小于v的区间[l...j-1]与大于v的区间[j+1...r]进行partition操作。

前面说过，实现partition操作有很多方式，比如还有三路快排，这里我就不再细讲了，另外这里还有很多可优化的地方，我会另写一篇文章详谈快排的优化，敬请期待。