快速排序思想与实现

无整理 不简书

快速排序相对其他排序算法比较难理解，有大牛曾形象的比喻成挖坑填数，我会把大牛的博客链接放在本文末尾，共同学习，在此我把快速排序比喻成挖坑填数 + 分治法。分治法就是将复杂的问题分解成规模较小的问题，再各个击破，分而治之。

例：快速排序算法把整数 32 56 14 6 78 23 按照从小到大的顺序排序。
在数列中选择某一个数作为基数(本例中选择第一个元素作为基数)，以基数为准，小于等于基数的元素交换到基数的前面，大于基数的元素交换到基数的后面，这样就实现了把数列分成了小于等于基数的数列和大于基数的数列。再从小于等于基数的数列和大于基数的数列中再选择另一个基数重复上述操作，直到不能再分成更小的数列排序完成。

基数 32 挖第一个坑

32（坑） 56 14 6 78 23
从右向左与基数进行比较直到遇到第一个小于等于基数的元素
23小于32 把23填到32的坑里
23 56 14 6 78 23（坑）
从左往右与基数进行比较直到遇到第一个大于基数的元素(填入坑中的元素不再比较)
56大于32 把56填到23的坑里
23 56（坑） 14 6 78 56
从右向左与基数进行比较直到遇到第一个小于等于基数的元素(填入坑中的元素不再比较)
78 大于 32 比较前一个元素
6 小于 32 把6填到56 的坑里
23 6 14 6（坑） 78 56
从左往右与基数进行比较直到遇到第一个大于基数的元素(填入坑中的元素不再比较)
14 小于 32 比较后一个元素到达坑
从左往右与从右往左都到达坑的位置，把基数32填入坑，比较结束
23 6 14 32（基） 78 56

原数列分成两部分
I.小于等于32的部分：23 6 14
I.大于32的部分：78 56

I.小于等于32的部分：23 6 14

基数 23 挖第一个坑
23（坑） 6 14
从右向左与基数进行比较直到遇到第一个小于等于基数的元素(填入坑中的元素不再比较)
14 小于23 14填到23的坑里
14 6 14（坑）
从左往右与基数进行比较直到遇到第一个大于基数的元素(填入坑中的元素不再比较)
6 小于 23 比较后一个元素到达坑
从左往右与从右往左都到达坑的位置，把基数23填入坑，比较结束
14 6 23（基）

原数列分成一部分
（1）.小于等于23的部分：14 6

基数 14 挖第一个坑
14（坑） 6
从右向左与基数进行比较直到遇到第一个小于等于基数的元素(填入坑中的元素不再比较)
6 小于 14 6 填到14的坑里
6 6（坑）
从左往右与从右往左都到达坑的位置，把基数14填入坑，比较结束
6 14（基）

II.大于32的部分：78 56

基数 78 挖第一个坑
78（坑） 56
从右向左与基数进行比较直到遇到第一个小于等于基数的元素(填入坑中的元素不再比较)
56 小于 78 56填入78的坑里
56 56（坑）
从左往右与从右往左都到达坑的位置，把基数14填入坑，比较结束
56 78（基）

排序结束 6 14 23 32 56 78

实现代码：

//快速排序
public int fastSort(int[] a, int l, int r)
{
    int i = l;
    int j = r;
    int x = a[i];
    while(i < j)
    {
        while(i < j && a[j] > x)
        {
            j--;
        }
        if(i < j)
        {
            a[i] = a[j];
            i++;
        }
        while(i < j && a[i] <= x)
        {
            i++;
        }
        if(i < j)
        {
            a[j] = a[i];
            j--;
        }
    }
    a[i] = x;
    return i;
}

//分治法
public void divide(int[] a, int l, int r)
{
    int m = fastSort(a, l, r);
    if(l != m)
    {
        divide(a , l, m - 1);
    }
    if(r != m)
    {
        divide(a, m + 1, r);
    }
}

如有错误之处，请指正。

扩展文章
常用三种排序算法的思想与实现
大牛博客链接
白话经典算法系列之六 快速排序 快速搞定