快排算法的实现与讲解(java/C++)

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

假设我们的数组为:{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

还是上一张图吧,比较好理解:

wKiom1MUSRPjUTOIAAC-kWvhNhc591

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

最后:

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

上代码吧,我写了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 << " ";
   }

}

 

 

 

Leave a Comment