Articles tagged with: 快排

快排的算法其实不复杂，但是很少时候，偶尔整的自己头晕，所以写一篇博客，以免以后忘记。

假设我们的数组为：{5,2,1,8,9,3,7,0,4,6}，一共10个数字，现在需要将这个数组进行排序。首先我们需要找一个基准数，其实就是参照物，得有个东西跟你对比吧？不然怎么可以呈现出你的美？

假设左边为i=0; 右边j = 9;

方法很简单，分别从数组的左右边两段进行“探测”。首先是左边移动，最左边的第一个数字是5，而最右边的数字是6。

6 >= 5 条件成立，接着左边往右边移动一位（j–）

……

4>=5条件不成立，这个时候就换一下位置，4跟5换。现在的数组应该就是这样子：{4,2,1,8,9,3,7,0,5,6}

接着轮到右边探测，左边的数字已经被替换为4，而右边的是5（因为j自减了一次）；那么现在条件对比：

5>=4条件成立，右边往左边靠拢（i++）

5>=2条件成立，右边往左边靠拢（i++）

……

5>=8条件不成立，换位置：{4,2,1,5,9,3,7,0,8,6}

到此，第一轮交换结束。接下来j继续向左挪动（再友情提醒，每次必须是j先出发）。他发现了0（比基准数5要小，满足要求）之后停了下来。此时再次进行交换，交换之后的序列如下：

{4,2,1,0,9,3,7,5,8,6}

第二次交换结束，“探测”继续。接着轮到i继续向右挪动，他发现了9（比基准数5要大，满足要求）之后又停了下来。交换之后的序列如下：

{4,2,1,0,5,3,7,9,8,6}

….以此类推，哨兵i继续向右移动，悲剧！！！此时i和j撞上了，说明此时“探测”结束。我们将基准数5和3进行交换。交换之后的序列如下：

{4,2,1,0,3,5,7,9,8,6}

到此“探测”真正结束。此时以基准数5为分界点，5左边的数都小于等于5，5右边的数都大于等于5。

回顾一下刚才的过程，其实j的使命就是要找小于基准数（5）的数，而哨兵i的使命就是要找大于基准数（5）的数，直到i和j撞在一起为止为止。

那么现在数据可以区分为两组：

{4,2,1,0,3,        5       ,7,9,8,6}

左边：4  2  1  0  3

右边：7  9  8  6

数组被分为了两组，然后按照直接的方法进行对比，只是开始i=0;j=9，要变为（先从左边开始）：

指针位置：i=0; j=4

数组：4  2  1  0  3

还是上一张图吧，比较好理解：

注：图片是网上找的，数组的排序跟我的不一致，但是看的明白。

最后：

• 快排的原理很简单；
• 就是把数组分为两节；
• 左边的是最小的，而右边的是最大的；
• 然后再拿左、右边的来继续递归，递归的原理也一样，也是拆分为两节，以此类推。

上代码吧，我写了java跟c的代码：

2.java代码:

public static void main(String[] args) {
    int[] arr = {5,2,1,8,9,3,7,0,4,6};
    sort(arr, 0, arr.length - 1);
    for (int i : arr) {
        System.out.print(i + " ");
    }
}

private static void sort(int[] arr, int l, int r) {
    int i = l;
    int j = r;
    if (l < r) {
        while (l < r) {
            while (l < r && arr[r] >= arr[l]) {
                r--;
            }
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

            while (l < r && arr[l] <= arr[r]) {
                l++;
            }
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;

        }
        sort(arr, i, l - 1);//递归左边，此时l=5
        sort(arr, l + 1, j);//递归右边，此时l=5
    }
}

2.那么c++的代码会是怎么样呢？

#include "pch.h"
#include <iostream>

using namespace std;

void sortQ(int *arr, int l, int r) {
   int i = l;
   int j = r;
   int tmp;
   if (i < j) {
      while (l < r) {
         while (l < r && arr[r] >= arr[l])
         {
            r--;
         }

         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;

         while (l < r && arr[r] >= arr[l]) {
            l++;
         }
         tmp = arr[l];
         arr[l] = arr[r];
         arr[r] = tmp;
      }

      sortQ(arr, i, l - 1);//处理左边，此时l=5
      sortQ(arr, l + 1, j);//处理右边，此时l=5
   }

}

int main()
{
    std::cout << "Hello World!\n"; 

   int arr[] = {5,2,1,8,9,3,7,0,4,6};
   int size = sizeof(arr) / sizeof(arr[0]);

   sortQ(arr, 0, size - 1);
   for (int i : arr) {
      cout << i << " ";
   }

}