vlambda博客
学习文章列表

前言

话不多说，店长上课要求要写快速排序法，我就来写一篇快速排序的一种方法——双路快排。

目录：

• 一、快排方法
  

• 二、代码美图

一条上课冒死都更文的分界线

是的，没错，现在老师就在我面前😱，问题不大。开干！开干！开干！ 

一、快排方法

首先对上面的数字进行快速排序。暂时定为数组a[10]。

一、

先在这个序列中随便找一个数作为基准数，通常选第一个数作为基准数叫他为Key吧，上面的4就是Key。（基准数的目的就是把比Key小的数放到Key的左边，把比Key大的数放到Key的右边。）

二、

①

i 作为基准数的下标，j 作为最右边数字的下标（看成一个数组）。j 向左边移动直到找到比Key(基准数)小的数（好交换到前面去）。然后i 就向右边移动直到找到比Key(基准数)大的数。（好交换到后面去）。

移动期间，j 要一直在i 的右边。i 要一直在j 的左边。（j>i），i和j遇到时就停下来。

这个时候5和1就交换。

然后继续循环①的操作

这个时候10和3就交换。

这个时候j继续向左边移动，到6时，6比4大要不得，还要望左边冲冲冲。到3下面时，j和i就碰到了。j就不可以移动了。然后i和j碰到对应的数字6就要和Key(基准数) 4 交换。

最后就成这样了

三，进行递归。（Key（4）就把一个数组分成了2个数组了）。

就是把3，1，2看成一个数组重复上面的操作。

把6，10，9，8，5，7看成一个数组重复上面的操作。

最后就会变成

二、代码美图

void Quick_Sort(int *arr, int begin, int end){
    if(begin > end) //就是数组的下标，begin要小于end，不然没得玩。
        return;
    int tmp = arr[begin];//tmp就是Key（基准数）
    int i = begin;//图上的i，begin是数组的开头
    int j = end;//图上的j，end是数组的结尾
 while(i != j){
        while(arr[j] >= tmp && j > i)//j一直往左边跑的条件。
            j--;
        while(arr[i] <= tmp && j > i)//i一直往右边跑的条件。
            i++;
 if(j > i)//主要是j先跑，i再跑。碰头了就和Key交换。{
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }//主要是j先跑，i再跑。
    }
    arr[begin] = arr[i];//这里是Key和i，j碰头对应的数交换步骤。
    arr[i] = tmp;
    Quick_Sort(arr, begin, i-1);//这是处理Key前面的新数组。
    Quick_Sort(arr, i+1, end);//这是处理Key后面的新数组。
}