快排算法为什么会这样写？

快排算法是什么？

快速排序，顾名思义，就是一种快速对数字进行大小 排序 的算法，据我所知，它应该是最快的算法了，它的时间复杂度为o（n ² ）。但同样地，它的算法要比简单的冒泡排序要复杂的多。如果你去网上搜，你可以搜到它的各种语言实现，比如这个 C 语言版本：

int partition(int a[], int low, int high){ 
     
    int k = a[low]; 
    
    while(low < high){ 
        while(low < high && a[high] > k) --high;
        
        a[low] = a[high];
        
        while(low < high && a[low] < k) ++low;
        
        a[high] = a[low];
    }
    a[low] = k;
    return low;
}
void quicksort(int arr[], int low, int high)
{
    if(low < high)
    {
        int position = partition(arr, low, high);
        quicksort(arr, low, position - 1);
        quicksort(arr, position + 1, high);
    }
}

代码不多，但是很难看懂。尽管网上有不少高人对这段代码作了各种各样的注释和说明，但完全不能说清楚：为什么快排算法要这样写？

快排算法真的有那么难理解吗？其实不是的，通过对算法的描述来看，算法本很好理解，但读起代码来就让人一脸懵逼，完全不知道这段代码在写什么。这是因为这段代码是以牺牲可读性为代价的高度凝练和简化后的版本，读不懂它也就是自然的了。

算法描述

虽然我们说快排算法从理论上并不难理解，但有我们还是要尽量更深入地解析它，这对于接下来的编码至关重要。快排算法有许多变异的版本，我们以最基本的快速排序为例。百度百科对快排的定义是：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

这里有几个概念，需要分别阐述一下。

1. 一趟快排

   快排是通过递归进行的，因此它需要反复多次调用函数自身才能完成排序。而每一次调用，我们称之为 一趟快排 。

2. 分区

   在一趟快排中，存在 分区 的概念。所谓的分区，即完整数组的一个子集，我们进行一趟快排，暂时只会处理这个分区中的数字。当然在第一次调用快排函数时（即进行第一次 一趟快排 时），这个分区是整个数组。我们会从分区中任意取一个数 k，找出这个数 应该 摆放的正确位置。这里的任意数，可以是分区的第一个数（一般情况），也可以是分区的最后一个数，或者任意位置的数。在一趟快排中，如何找出这个数的 正确位置 呢？

3. 两条军规

   这里需要强调一下 正确位置 的概念。怎样才能认为一个数在数组中的位置是 正确 的呢？其实这里两条判断标准：

   • 规则 1

     如果在数组中，这个数左边还有数其它数字，那么这些数字都应该比它小

   • 规则 2

     如果在数组中，这个数右边还有其它数字，那么这些数字应该都比它大

   严格来说，就算一个数达到了这个标准，这个数组也不能说是排好序了。比如：3,5,2,8,9，其中 8 这个数字，已经符合 位置正确 的标准，这个数组仍然不是有序的。只有当数组中每一个数都符合这个标准，都达到了 位置正确 的程度，这个数组才是有序的。虽然这样，单个数的 位置正确 对于快排来说仍然有重要的意义，因为它达到 位置正确 后，它的位置就固定下来了，其它数无论怎么排序，都不会影响它的位置，因为它已经站在了 正确位置 上，它可以提前结束排序。当然它左右两边如果还有数字（即它不是分区的最大数或最小数），那么我们还要将它左右两边的数字分成两个更小的分区（即将左边小于它的数分一个区，右边大于它的数分另一个去），分别进行 一趟快排 (即递归调用快排函数)。这样每次递归找出一个 位置正确 的数，直至所有数都排好序。

   关键是如何对分区中的单个数进行排序（也叫分区算法或一趟快排算法）。如果用冒泡排序法，这很简单，我们可以把这个数和分区里其它数挨个进行比较。但是快排法之所以叫快排法，显然不能这么简单。因为这样需要进行更多的比较，效率比较低。它实际上是这样做的：

   1. 先取分区第一个数，记作 k。
   2. 从分区尾开始向左扫描，查看是否有比 k 小的数。

      位置正确
      正确位置
      

   3. 进行左扫描，即从分区首向右扫描，一直到抵达右指针的位置。查看左边的数是否有比 k 大的。

      正确位置
      

还原快排算法

看完上面的算法描述，我们可以根据自己的理解来编写自己的快排算法了。可能这样实现的代码和前面所列的代码不太一样，但无疑是未经删减的原始版本，真实还原了快排算法的原型，理解起来相对容易一些。

工具函数

在这之前，我们先从简单的地方入手。实现两个 工具 函数，比如前面提到的交换算法：

void swap(int a[],int i,int j){
    int tmp = a[i];
    a[i] = a[j];
}

比如循环打印一个数组中的数字：

void printArray(int a[],int len){
    NSMutableString* str = [NSMutableString new];
    for(int i = 0 ;i<len;i++){
        [str appendString:@(a[i]).stringValue];
        [str appendString:@","];
    }
    NSLog(@"%@",str);
}

都是很简单的代码，不用解释了。

快排算法基于递归，因此在快排函数中，主要是这么一个递归函数：

void quicksort(int a[],int left,int right){
    if(left < right){
        int correctPos = partition(a, left, right);// 排好一个数        
        quicksort(a, left, correctPos - 1); // 递归左边
        quicksort(a, correctPos + 1, right);// 递归右边
    }
}

并没有太多代码，关键的代码还是在分区算法（或一趟快排算法）中。

分区算法

按照前面的算法描述，分区算法（一趟快排算法）的初步实现如下：

int partition(int a[],int left,int right){ // 1
    int k = a[left]; // 2
    while(left < right){ // 3
        while(left < right){ // 4
            if(a[right] >= k){ // 5
                right --;
            }else{ // 6
                break;
            }
        }
        
        if(right == left){ // 7
            break;
        }else{ // 8
				  swap(a, right, left);
        }
        while(left < right){ // 9
            if(a[left] <= k){ // 10
                left ++;
            }else{ // 11
                break;
            }
        }
        if(right == left){ // 12
            break;
        }else{ // 13
            swap(a, left, right);
        }
    }
    return left; // 14
}

1. int partition(int a[],int left,int right){ // 1

   partition 函数有 3 个参数：要排序的数组 a，本次分区的头位置 left 和尾位置 right（也就是左指针和右指针）。

2. int k = a[left]; // 2

   首先随便取一个数 k（这里取的是分区第一个数），我们将在方法中计算出它的 正确位置 然后 return。

3. while(left < right){ // 3

   这是一个大循环，将左右扫描的代码放到这个大循环里。我们需要在这个循环中不停地扫描并移动左右指针（left 和 right），直到两个指针相等（left == right）时，才终止循环。当然，如果参数中传来的 left 本来就等于 right，说明本次分区中只有一个数，则直接跳到方法最后一句返回 return right。

4. while(left < right){ // 4

   在大循环中，首先进行的是右扫描，即从分区尾向左扫描。扫描的方式是循环，循环条件同样是 left < right。

5. if(a[right] >= k){ // 5

   右扫描的方式是依次取出右指针所在的数和 k 进行比较，如果这个数大于 k，则不管（因为它符合规则 2，位于 k 右侧，且大于 k），右指针减一，right – ; 继续比较下一个数，直到左右指针碰头，即 right == left。

6. }else{ // 6

   如果扫描到的数字违反了规则 2，则指针在这个位置停下，退出右扫循环（即 break;）。

7. if(right == left){ // 7

   如果是没找到，那么肯定满足 right == left 条件，那么 break 退出大循环。退出大循环后就只有一句 return 语句了。这是因为右扫找不到，左扫肯定也扫不到（k 是第一个数啊，它左边没数了），那么同时满足规则 1 和规则 2，于是证明 k 就是 正确位置 了，肯定返回。

8. else{ // 8

   如果找到，那么让它和 k 调换一下位置。这样调换后它就位于 k 右边了，符合规则 2。 也就是说，到此为止，right 右边的数全都符合规则 2 的了。

9. while(left < right){ // 9

   右扫完成，开始左扫。左扫完成的条件也是 left == right。

10. if(a[left] <= k){ // 10

    如果左扫中的数据 <= k，满足规则 1，则不管，继续移动指针 left ++。

11. }else{ // 11

    如果扫描到的数字 > k，违反规则 1，指针在此停下，退出左扫循环 break;

12. if(right == left){ // 12

    如果没有找到任何违反规则的数，即 right == left，则 break，再次退出大循环，去执行 return。这是因为，左扫找不到违反规则 1 的，右扫也找不到违反规则 2 的（就算曾经找到，也被我们通过 swap 处理过了，已经符合规则 2 了），那肯定这个数就是 位置正确 的了，应该返回。

13. }else{ // 13

    如果找到违反规则的数，那么同理，让它和 k 调换一下位置，这样它就位于 k 的左边了，符合规则 1。 也就是说，到此为止，left 左边的数都是符合规则 1 的了。

    注意，这里使用的交换是 swap(a, left, right)，这个 right 就是 k 目前所在的位置。为什么呢？因为如果右扫描没有找到违反规则 2 的数，则代码直接退出大循环外了。而现在代码已经执行到这里，说明右扫描是一定找到违反规则 2 的数的，这样它就一定和 k 进行过交换，即 right 指针所指的数应该是 k，而那个违反规则的数被交换到了 k 的左侧（左扫描未开始时的 left 处，即数组的第一个位置）。

    如果最后左右指针之间还有数字没有被扫描到，即 left != right，那么大循环肯定还要继续，继续对剩下的数字重复4-13 的步骤。否则退出循环，进到第 14 步。

14. 当大循环执行到这里，左右指针肯定已经碰头，k 也正好位于左右指针共同指向的位置，同时，k 也满足规则 1 和规则 2。因此可以返回了。由于 left == right，因此 return left 和 return right 其实是一样的。

注意，在方法中，基本上没执行一个步骤都要对 left < right 进行判断，防止左右指针 穿越 ，一旦发现 left == right，立即就要 return。因为左右指针遵循的规则是恰恰相反的，一旦穿越对方来到对方的区域，原来符合规则的数恰恰变成了违反规则的数，导致死循环。

简化代码

分析代码发现，其实有的判断是不必要的，交换也是不必要的。因此我们可以将代码精简为：

int partition(int a[],int left,int right){
    int k = a[left];
    while(left < right){
        while(left < right && a[right] >= k){ // 1
                right --;
        }
        if(left < right){ // 2
            a[left] = a[right];// 3
        }
        
        while(left < right && a[left] <= k){ // 4
                left ++;
        }
        if(left < right){ // 5
            a[right]=a[left]; // 6
        }
    }
    a[left] = k; // 7
    return left; // 8
}

1. 在循环条件中加入规则 2 （即右边数必须 >= k)，这样当出现违反规则 2 的情况时自动就退出循环了。这样就不需要在循环中对是否违反规则 2 的情况进行判断，节省了一条 if 语句。
2. 因为基本上后面的每个语句都添加了 left < right 判断，所以这里没有必要对 left == right 进行判断了。当 left = right 时，大循环体内的每个语句都不会执行，相当于一个 break 语句。因此 if(left==right){break;}就可以省去。
3. 省去两个数的交换，因为分区首的第一个数 a[left] 实际上在 k 中保留了拷贝，这里用 a[right] 覆盖 a[left] 即可，相当于把右指针找到的数放到了左边，维持小数居左原则。同时， 右指针所在的数是多余的了，可以用来保存其它数 。此时，找到的数同时在分区首和右指针的位置保存了两份拷贝。
4. 同 1.
5. 同 2.
6. 省去两数交换，因为在分区首和右指针处有两处重复拷贝，所以可以利用其中一个来保存找到的数，因为 右指针处的数是多余的拷贝 ，所以可以用右指针来保存左指针找到的数。相当于把左指针的数放到了右边。维持大数居右原则。这时， 左指针处的数显得有些多余了 ，可以用来放其它缺少的 k 值。
7. 当大循环退出，即 left == right 时，表明已经计算出 k 的 正确位置 ，可以将 k 放在正确的位置即可。因为 left == right，那么 a[left] = k 或者 a[right] = k 是一样的。
8. 返回 k 的 正确位置 ，因为此时 left == right，那么 return left 或者 return right 是一样的。

现在的代码已经变得和经典 C 快排代码差不多了，只要你愿意，你还可以继续简化成：

int partition(int a[],int left,int right){
    int k = a[left];
    while(left < right){
        while(left < right && a[right] >= k){
            right --;
        }
        a[left] = a[right]; // 1
        
        while(left < right && a[left] <= k){
            left ++;
        }
        a[right]=a[left]; // 2
    }
    a[right] = k;
    return left;
}

这就跟经典 C 代码一模一样了（除了变量名有所不同）。修改的地方主要是：

1. 直接省去了 if(left < right) 判断。直接执行 a[left] = a[right]; 实际上，这个判断没有必要。为 while 循环退出条件的限制，退出循环只有两种可能，一种是没找到，左右指针碰头（相等），left == right，这种情况下让 a[left] = a[right] 实际上等于 a = a，用自己对自己赋值 ，就算执行了也没什么关系；另一种情况是找到了，left < right，这种情况本来就应该执行 a[left] = a[right];
2. 同 1.

表面上看，经典 C 代码的代码行数要少许多，但是你真的很难理解它在干什么。经过从未删减版到精简版的一番推导过程，你是否觉得会更好记一些了呢？