关于后端:快速排序算法实现及优化

本文已被 Github 仓库收录 https://github.com/silently9527/JavaCore

程序员罕用的 IDEA 插件：https://github.com/silently9527/ToolsetIdeaPlugin

齐全开源的淘客我的项目：https://github.com/silently9527/mall-coupons-server

微信公众号：贝塔学 Java

前言

疾速排序能够说是应用最广的排序算法了，次要的特点是基于原地排序（不须要应用辅助数组，节俭空间）；其实对于长度为 N 的数组应用疾速排序工夫复杂度为 NlogN；在前几篇也一起探讨了其余的排序算法，都没可能把这两个特点联合起来。

疾速排序思路

疾速排序也是一种分治的排序算法，把数组划分为两个子数组，而后递归对子数组进行排序，最终保障整个数组有序。

算法思路：

1. 随机抉择一个切分元素，通常抉择的是数组的第一个元素
2. 从数组的右边开始扫描找出大于等于切分元素的值，从数组的左边开始扫描找出小于等于切分元素的值，替换这两个值
3. 循环这个过程直到左右两个指针相遇，这样就排定了一个元素，保障了切分元素右边的值都是小于它的值，左边的元素都是大于它的值
4. 递归这个过程，最终保障整个数组有序

算法实现

依据疾速排序算法的思路，咱们能够写出第一版实现：

public class QuickSort implements SortTemplate {
    @Override
    public void sort(Comparable[] array) {quickSort(array, 0, array.length - 1);
    }

    private void quickSort(Comparable[] array, int lo, int hi) {if (lo >= hi) {return;}
        int partition = partition(array, lo, hi);
        quickSort(array, lo, partition - 1);
        quickSort(array, partition + 1, hi);
    }

    private int partition(Comparable[] array, int lo, int hi) {
        int i = lo, j = hi + 1;
        Comparable el = array[lo];
        while (true) {while (less(array[++i], el)) {if (i == hi) {break;}
            }
            while (less(el, array[--j])) {if (j == lo) {break;}
            }
            if (i >= j) {break;}
            exch(array, i, j);
        }
        exch(array, lo, j);
        return j;
    }
}

其中 exch、less 办法的实现请看之前的文章《常见的高级排序算法，这次全搞懂》

这段代码是实现疾速排序的惯例实现，思考最蹩脚的状况，如果须要排序的数组是曾经有序的[1,2,3,4,5,6,7,8]，执行疾速排序的过程如图：

对一个长度为 N 的数组，最蹩脚的状况下须要递归 N - 1 次，所以工夫复杂度是 O(n²)，为了防止这种状况呈现，咱们来看下算法如何改良

算法改良

• 保障随机性

为了防止最蹩脚的状况呈现，有两个方法，第一是在排序数组之前先随机打乱数组；第二是在 partition 办法中随机取切分元素，而不是固定取第一个，简略实现：

private int partition(Comparable[] array, int lo, int hi) {
    int i = lo, j = hi + 1;
    int random = new Random().nextInt(hi - lo) + lo;
    exch(array, lo, random);
    Comparable el = array[lo];
    while (true) {while (less(array[++i], el)) {if (i == hi) {break;}
        }
        while (less(el, array[--j])) {if (j == lo) {break;}
        }
        if (i >= j) {break;}
        exch(array, i, j);
    }
    exch(array, lo, j);
    return j;
}

• 切换到插入排序

这点和归并排序一样，对于小数组的排序间接切换成插入排序

private void quickSort(Comparable[] array, int lo, int hi) {if (lo >= hi) {return;}
    
    if (hi - lo < 5) {  // 测试，小于 5 就切换到插入排序
        insertionSort(array, lo, hi);
        return;
    }

    int partition = partition(array, lo, hi);
    quickSort(array, lo, partition - 1);
    quickSort(array, partition + 1, hi);
}

// 插入排序
private void insertionSort(Comparable[] array, int lo, int hi) {for (int i = lo; i <= hi; i++) {for (int j = i; j > lo && less(array[j], array[j - 1]); j--) {exch(array, j, j - 1);
        }
    }
}

• 三向切分

当咱们须要排序的数组中呈现了大量的反复元素，咱们实现的疾速排序在递归的时候会遇到许多全副反复的子数组，咱们的算法仍然会对其进行切分，这里有很大的晋升空间。

思路就是先随便抉择一个切分元素 (el)，而后把数组切换成大于、等于、小于三个局部，一次递归能够排定所有等于切分元素的值；
保护一个指针 lt、gt，使得 a[lo..lt-1]都小于切分元素，a[gt+1..hi]都大于切分元素；

• 初始化变量：lt=lo, i=lo+1, gt=hi
• if a[i] < el ; 替换 a[i]与 a[lt], i++, lt++
• if a[i] > el ; 替换 a[gt]与 a[i], gt–
• a[i] == el; i++

代码实现：

public class Quick3waySort implements SortTemplate {
    @Override
    public void sort(Comparable[] array) {quickSort(array, 0, array.length - 1);
    }

    @SuppressWarnings("unchecked")
    private void quickSort(Comparable[] array, int lo, int hi) {if (lo >= hi) {return;}
        int lt = lo, i = lo + 1, gt = hi;
        Comparable el = array[lo];
        while (i <= gt) {int tmp = el.compareTo(array[i]);
            if (tmp > 0) {exch(array, lt++, i++);
            } else if (tmp < 0) {exch(array, i, gt--);
            } else {i++;}
        }
        quickSort(array, lo, lt - 1);
        quickSort(array, gt + 1, hi);
    }
}

最初（点关注，不迷路）

文中或者会存在或多或少的有余、谬误之处，有倡议或者意见也十分欢送大家在评论交换。

最初，写作不易，请不要白嫖我哟 ，心愿敌人们能够 点赞评论关注 三连，因为这些就是我分享的全副能源起源????

文中所有源码已放入到了 github 仓库 https://github.com/silently9527/JavaCore