最近花了几天重温了一下《算法(第四版)》, 重新把书中的算法实现了一下, 并且思索了一下, 把常见的比较排序算法都给优化了一下, 然后进行了性能测试. 也算是复习了一下排序算法吧.
阅读本篇之前最好有常见几种基于的比较排序算法的基础
本文内容包括:
- 归并排序优化及性能测试
- 快速排序优化及性能测试
- 堆排序序优化及性能测试
- 非比较排序介绍
- 计数排序
- 桶排序
- 基数排序
源代码:
- 排序类: https://github.com/JasonkayZK/Java_Algorithm/tree/master/src/main/java/algorithm/sort
- 排序测试: https://github.com/JasonkayZK/Java_Algorithm/tree/master/src/test/java/algorithm/sort
如果觉得文章写的不错, 可以关注微信公众号: Coder张小凯
内容和博客同步更新~
一.归并排序优化及性能测试
归并排序是建立在归并操作上的一种有效的排序算法
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用:
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序; 特别的, 若将两个有序表合并成一个有序表，称为2-路归并
1.算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列
2.动图演示(自底向上)
3.代码实现(自顶向下)
MergeSort.java
package algorithm.sort;
import java.util.Arrays;
/**
* 归并排序
*
* 归并排序的核心是: 归并操作
*
* 归并操作将两个有序的数组归并为更大的一个有序数组
*
* 要将一个数组排序, 可以先(递归的)将它分为两半分别排序, 然后将结果归并起来
*
* 平均时间: O(NlgN)
*
* 最坏时间: O(6NlgN) 此时数组为完全树
*
* 最好时间: O(N) 数组元素全部相同
*
* 空间: O(N) 开辟了一个和排序数组相同大小的数组用于归并
*
* @author zk
*/
@SuppressWarnings("unchecked")
public class MergeSort extends BaseSort {
/**
* 使用成员变量防止使用递归过多的创建数组!
*/
private static Comparable[] aux;
private MergeSort() {
}
public static <K extends Comparable<K>> void sortTopDown(K[] a) {
aux = new Comparable[a.length];
sortTopDown(a, 0, a.length - 1);
}
/**
* 自顶向下的归并排序(lo...hi)区间
*
* @param a 待排序数组
* @param lo 排序左边界
* @param hi 排序右边界(包括)
*/
private static <K extends Comparable<K>> void sortTopDown(K[] a, int lo, int hi) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
// 将左半边排序
sortTopDown(a, lo, mid);
// 将右半边排序
sortTopDown(a, mid + 1, hi);
// 归并结果
merge(a, lo, mid, hi);
}
/**
* 原地归并的方法
* <p>
* 将子数组a[lo...mid]和a[mid+1...hi]归并成一个有序的数组
* <p>
* 并将结果放在a[lo...hi]中
*
* @param a 待归并数组
* @param lo 左边界
* @param mid 中间
* @param hi 右边界
*/
private static <K extends Comparable<K>> void merge(K[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
// 将a[lo...hi]复制到aux[lo...hi]
if (hi + 1 - lo >= 0) {
System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
}
// 在这里由于Java不允许创建静态泛型, 所以采用了强制类型转换: 父类 -> 子类
for (int k = lo; k <= hi; k++) {
// 左半边用尽
if (i > mid) a[k] = (K) aux[j++];
// 右半边用尽
else if (j > hi) a[k] = (K) aux[i++];
// 右半边小于左半边
else if (less(aux[j], aux[i])) a[k] = (K) aux[j++];
// 右半边大于等于左半边
else a[k] = (K) aux[i++];
}
}
}归并排序是一种稳定的排序方法
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度, 代价是需要额外的内存空间
4.优化方法
① 自底向上的归并排序
自底向上的归并排序(和上述图例对应的算法)不算是上述自顶向下算法的优化, 事实上在我的测试上显示, 在一般情况下它的性能反而下降;
提出这个算法的原因在于: 在链表型数据结构使用自底向上的归并排序时, 可以通过操作指针实现空间复杂度O(1)的排序
/**
* 自底向上的归并排序:
* <p>
* 自底向上进行lgN次的两两归并
*
* 当数组长度为2的幂时: 自顶向下和自底向上仅仅是访问次序不同(比较次数和数组访问次数相同)
*
* 但其他时候不同;
*
* 非常适合链表的原地归并!(此时空间复杂度为O(1))
*
* @param a 待排序数组
*/
public static <K extends Comparable<K>> void sortBottomUp(K[] a) {
aux = new Comparable[a.length];
for (int sz = 1, len = a.length; sz < len; sz *= 2)
for (int lo = 0; lo < len - sz; lo += sz + sz)
merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, len - 1));
}
/**
* 原地归并的方法
* <p>
* 将子数组a[lo...mid]和a[mid+1...hi]归并成一个有序的数组
* <p>
* 并将结果放在a[lo...hi]中
*
* @param a 待归并数组
* @param lo 左边界
* @param mid 中间
* @param hi 右边界
*/
private static <K extends Comparable<K>> void merge(K[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
// 将a[lo...hi]复制到aux[lo...hi]
if (hi + 1 - lo >= 0) {
System.arraycopy(a, lo, aux, lo, hi + 1 - lo);
}
// 在这里由于Java不允许创建静态泛型, 所以采用了强制类型转换: 父类 -> 子类
for (int k = lo; k <= hi; k++) {
// 左半边用尽
if (i > mid) a[k] = (K) aux[j++];
// 右半边用尽
else if (j > hi) a[k] = (K) aux[i++];
// 右半边小于左半边
else if (less(aux[j], aux[i])) a[k] = (K) aux[j++];
// 右半边大于等于左半边
else a[k] = (K) aux[i++];
}
}② 针对多个方面进行归并排序的优化
针对自底向上和自顶向下的归并排序可以进行的优化有:
对小规模子数组采用插入排序:
递归对于小规模的数组将产生过多的小数组甚至是空数组调用栈
测试数组是否已经有序:
若a[mid]<=a[mid+1], 认为数组已经有序, 可以跳过merge()方法
不将元素复制到辅助数组aux:
调用两种排序方法: 一种将数据从输入数组排序到辅助数组, 另一个方法反之;
将这三个优化作用在自顶向下的归并排序中, 代码如下:
/**
* threshold to insertion sort
*/
private static final int THRESHOLD = 7;
public static <K extends Comparable<K>> void advancedSort(K[] a) {
// 此次未使用成员变量的辅助数组
var helper = Arrays.copyOf(a, a.length);
advancedSort(helper, a, 0, a.length - 1);
}
/**
* 优化的自顶向下的归并排序(lo...hi)区间
*
* 1.对小规模子数组采用插入排序:
* - 递归对于小规模的数组将产生过多的小数组甚至是空数组调用栈
*
* 2.测试数组是否已经有序:
* - 若a[mid]<=a[mid+1], 认为数组已经有序, 可以跳过merge()方法
*
* 3.不将元素复制到辅助数组aux
* - 调用两种排序方法: 一种将数据从输入数组排序到辅助数组, 另一个方法反之;
*
* @param src 源数组
* @param dst 目标数组(当前递归中的辅助数组)
* @param lo 排序左边界
* @param hi 排序右边界(包括)
*/
private static <K extends Comparable<K>> void advancedSort(K[] src, K[] dst, int lo, int hi) {
// 1.当排序大小小于THRESHOLD, 使用插排
if (hi <= lo + THRESHOLD) {
insertionSort(dst, lo, hi);
return;
}
// 归并
int mid = lo + (hi - lo) / 2;
advancedSort(dst, src, lo, mid);
advancedSort(dst, src, mid + 1, hi);
// if (!less(src[mid+1], src[mid])) {
// for (int i = lo; i <= hi; i++) dst[i] = src[i];
// return;
// }
// 2.测试数组是否已经有序, 跳过归并
// 使用System.arraycopy()比上述循环略快
if (!less(src[mid + 1], src[mid])) {
System.arraycopy(src, lo, dst, lo, hi - lo + 1);
return;
}
merge(src, dst, lo, mid, hi);
}
/**
* 不使用辅助数组进行复制归并(但是仍需要空间)
*
* @param src 源数组
* @param dst 目标数组
* @param lo 归并左边界
* @param hi 归并右边界
*/
private static <K extends Comparable<K>> void merge(K[] src, K[] dst, int lo, int mid, int hi) {
// assert isSorted(src, lo, mid);
// assert isSorted(src, mid + 1, hi);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) dst[k] = src[j++];
else if (j > hi) dst[k] = src[i++];
// 保证稳定性
else if (less(src[j], src[i])) dst[k] = src[j++];
else dst[k] = src[i++];
}
// PostCondition: dst[lo .. hi] is sorted subarray
// assert isSorted(dst, lo, hi);
}
/**
* 使用插排排序a[lo...hi]子区间
*
* @param a 排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static void insertionSort(Comparable[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}5.性能测试
对归并排序的各种方法进行性能测试
分别对一千万个随机数组和随机重复数组排序
MergeSortTest.java
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.BaseSort.show;
import static algorithm.sort.MergeSort.advancedSort;
import static algorithm.sort.MergeSort.sortTopDown;
import static algorithm.sort.MergeSort.sortBottomUp;
public class MergeSortTest {
/**
* 对归并排序的各种方法进行性能测试
*
* 分别对一千万个随机数组和随机重复数组排序
*/
@Test
public void compareSort() {
// 正常随机数组
Integer[] a11 = RandomArrayUtil.getRandomBoxedIntArray(0, 100000000, 10000000);
Integer[] a12 = Arrays.copyOf(a11, a11.length);
Integer[] a13 = Arrays.copyOf(a11, a11.length);
// 大量重复数组
Integer[] a21 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000, 10000000);
Integer[] a22 = Arrays.copyOf(a21, a21.length);
Integer[] a23 = Arrays.copyOf(a21, a21.length);
System.out.println("Array created!");
Stopwatch stopwatch = new Stopwatch();
sortTopDown(a11);
StdOut.printf("%s (%.2f seconds)\n", "sortTopDown [random]:", stopwatch.elapsedTime());
sortTopDown(a21);
StdOut.printf("%s (%.2f seconds)\n", "sortTopDown [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a11);
assert isSorted(a21);
System.out.println();
stopwatch = new Stopwatch();
sortBottomUp(a12);
StdOut.printf("%s (%.2f seconds)\n", "sortBottomUp [random]:", stopwatch.elapsedTime());
sortBottomUp(a22);
StdOut.printf("%s (%.2f seconds)\n", "sortBottomUp [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a12);
assert isSorted(a22);
System.out.println();
stopwatch = new Stopwatch();
advancedSort(a13);
StdOut.printf("%s (%.2f seconds)\n", "advancedSort [random]:", stopwatch.elapsedTime());
advancedSort(a23);
StdOut.printf("%s (%.2f seconds)\n", "advancedSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a13);
assert isSorted(a23);
System.out.println();
}
}排序结果如下:
sortTopDown [random]: (4.22 seconds)
sortTopDown [random + duplicate]: (7.40 seconds)
sortBottomUp [random]: (5.06 seconds)
sortBottomUp [random + duplicate]: (9.26 seconds)
advancedSort [random]: (3.80 seconds)
advancedSort [random + duplicate]: (6.56 seconds)6.性能测试总结
可知:
- 含有重复元素的排序反而稍快!
- 自顶向下的排序稍快于自底向上的排序(但是自底向上归并的优势在于: 针对链表排序的空间复杂度为O(n))
- 优化后的自顶向下的归并排序显然性能更加优越(一千万个数的排序用了3.8秒!)
归并排序性能冠军: advancedSort
性能优化原因:
- 对小规模子数组采用插入排序: 避免了对小规模的数组进行递归而产生过多的小数组甚至是空数组调用栈
- 测试数组是否已经有序: 不需要对有序的两个子数组进行归并操作
- 不将元素复制到辅助数组aux: 优化了空间复杂度
二.快速排序优化及性能测试
快速排序的基本思想:
通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序
1.算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）
具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
2.动图演示
3.代码实现
QuickSort.java
package algorithm.sort;
import algorithm.util.random.StdRandom;
/**
* 快速排序
*
* - 选定一个轴(为了便于处理, 一般选择子数组的首个元素)
*
* - 然后基于切分算法: 将数组a切分为a[lo...j-1] < a[j] < a[j+1...hi]
*
* - 递归地在左右子数组进行上述步骤
*
* 平均时间: O(2NlnN ≈ 1.39NlgN) 平均需要2NlnN次比较
*
* 最好时间: O(NlgN) 每次选中中位数进行对半切分
*
* 最坏时间: O(N^2/2) 当数组已经是一个有序数组时, 每次切分一个元素, 需要N^2/2次比较
*
* 空间: O(1)
*
* 为了避免最差情况, 我们需要合理选择轴元素, 方法有:
*
* 1.排序前将数组重排: 如使用: StdRandom.shuffle(a);
*
* 2.选择合适的key(轴元素), 如使用left, mid, right的中位数
* (为了保证排序的统一性, 可以将中位数和最左侧left元素交换, 从而保证排序算法不变)
*
* @author zk
*/
public class QuickSort extends BaseSort {
private QuickSort() {
}
public static <K extends Comparable<K>> void sort(K[] a) {
// 重排数组a, 消除对输入的依赖
StdRandom.shuffle(a);
sort(a, 0, a.length - 1);
}
/**
* 最基本的快速排序实现
*
* @param a 待排序子数组
* @param lo 数组左边界
* @param hi 数组右边界
*/
private static <K extends Comparable<K>> void sort(K[] a, int lo, int hi) {
if (hi <= lo) return;
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
/**
* 切分(交换法): 将数组a切分为a[lo...j-1] < a[j] < a[j+1...hi]
*
* 快速排序的切分算法(快排核心)
*
* @param a 待排序数组
* @param lo 子数组左边界
* @param hi 子数组右边界
* @return 切分后的标准元素key的index
*/
private static <K extends Comparable<K>> int partition(K[] a, int lo, int hi) {
// 将数组切分为a[lo...j-1], a[j], a[j+1...hi]
int i = lo, j = hi + 1;
// 选定开头为标准元素
K key = a[lo];
while (true) {
// 左右移动, 跳过已经有序的位置
while (less(a[++i], key)) if (i == hi) break;
while (less(key, a[--j])) if (j == lo) break;
// 切分完毕, 跳过交换
if (i >= j) break;
// 找到乱序的, 交换
exch(a, i, j);
}
// 将key放入对应位置
exch(a, lo, j);
return j;
}
}除此之外, 快排还有另一种算法, 即通过挖坑法:
public static <K extends Comparable<K>> void sort2(K[] a) {
StdRandom.shuffle(a);
sort2(a, 0, a.length - 1);
}
/**
* 基本快排的另一种实现方法
* <p>
* (将partition方法inline, 并使用挖坑法代替交换!)
*
* @param a 待排序数组
* @param lo 子数组左边界
* @param hi 子数组右边界
*/
private static <K extends Comparable<K>> void sort2(K[] a, int lo, int hi) {
if (a.length <= 1 || lo >= hi) return;
int left = lo, right = hi;
// 选定数组第一个数字作为key
var key = a[left];
while (left < right) {
// 从右向左遍历,找到小于key的,放入下标left中
// !less(a[right], key) <=> !(a[right] < key) <=> a[right] >= key
// 相等也要移动
while (left < right && !less(a[right], key)) right--;
a[left] = a[right];
// 从左向右遍历,找到大于key的,放入下标right中
// !less(key, a[left]) <=> !(key < a[left]) <=> a[left] <= key
// 相等也要移动
while (left < right && !less(key, a[left])) left++;
a[right] = a[left];
}
// 此时left == right, 这就是所谓的轴
// 把key放入轴中，轴左边的都<key,轴右边的都>key
a[left] = key;
// 此时轴在数组中间，说明把数组分成两部分，此时要对这两部分分别进行快排
sort2(a, lo, left - 1);
sort2(a, left + 1, hi);
}
说明:
关于这个方法, 在我的另一篇文章有更详细的说明: QuickSort总结
需要注意的是, 在后来的性能测试中显示这个算法的性能并不是很好(虽然很好写)
4.优化方法
① 针对排序基准轴优化
针对基本快排进行优化的思路主要有以下几个:
- 在排序之前进行打乱操作(上述代码已经使用)
- 小数组切换到插入排序: 通常THRESHOLD选择5~15均可
- 三取样切分, 选择子数组一小部分的中位数来切分(保证尽量均匀)
下面为使用上述代码优化的代码:
/**
* 子数组切换为插排的阈值
*/
private static final int INSERTION_SORT_THRESHOLD = 8;
public static <K extends Comparable<K>> void advancedSort(K[] a) {
advancedSort(a, 0, a.length - 1);
}
/**
* 针对基本快排进行优化的排序算法
*
* 优化包括:
* - 1.小数组切换到插入排序: 通常THRESHOLD选择5~15均可
*
* - 2.三取样切分, 选择子数组一小部分的中位数来切分
*
* @param a 待排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static <K extends Comparable<K>> void advancedSort(K[] a, int lo, int hi) {
if (hi <= lo) return;
// 子数组长度小于阈值, 使用插排
int n = hi - lo + 1;
if (n <= INSERTION_SORT_THRESHOLD) {
insertionSort(a, lo, hi);
return;
}
int j = advancedPartition(a, lo, hi);
advancedSort(a, lo, j - 1);
advancedSort(a, j + 1, hi);
}
/**
* 优化的切分算法, 选择[lo, (lo+hi)/2 , hi]三者中的中位数作为轴
*
* @param a 待切分数组
* @param lo 切分左边界
* @param hi 切分右边界
* @return 轴元素
*/
private static <K extends Comparable<K>> int advancedPartition(K[] a, int lo, int hi) {
// 选择[lo, (lo+hi)/2 , hi]三者中的中位数作为轴
int n = hi - lo + 1, m = median3(a, lo, lo + n / 2, hi);
exch(a, m, lo);
int i = lo, j = hi + 1;
var key = a[lo];
// 若a[lo]是唯一最大元素
// 将a[lo]与a[hi]交换, 此时即: a[lo...hi-1] < a[hi]
while (less(a[++i], key)) {
if (i == hi) {
exch(a, lo, hi);
return hi;
}
}
// 若a[lo]是唯一最小元素
// 此时不需要动, 直接返回lo的index, 因为a[lo] < a[lo+1...hi]
while (less(key, a[--j])) {
if (j == lo + 1) return lo;
}
// 其他情况
while (i < j) {
exch(a, i, j);
while (less(a[++i], key)) ;
while (less(key, a[--j])) ;
}
// 将轴key放到指定位置
exch(a, lo, j);
// 此时, a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
return j;
}
/**
* 寻找数组a中三个元素的中位数, 返回index
*
* @return 中位数元素index
*/
private static <K extends Comparable<K>> int median3(K[] a, int i, int j, int k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}
/**
* 使用插排排序a[lo...hi]子区间
*
* @param a 排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static <K extends Comparable<K>> void insertionSort(K[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}
另一个版本的实现(挖坑法)
public static <K extends Comparable<K>> void advancedSort2(K[] a) {
advancedSort2(a, 0, a.length - 1);
}
/**
* 针对基本快排进行优化的排序算法的另一种实现(挖坑法)
* <p>
* 将advancedPartition进行inline操作
*
* @param a 待排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static <K extends Comparable<K>> void advancedSort2(K[] a, int lo, int hi) {
if (hi <= lo) return;
// 子数组长度小于阈值, 使用插排
int n = hi - lo + 1;
if (n <= INSERTION_SORT_THRESHOLD) {
insertionSort(a, lo, hi);
return;
}
// 选择[lo, (lo+hi)/2 , hi]三者中的中位数作为轴
int m = median3(a, lo, lo + (hi - lo + 1) / 2, hi);
exch(a, m, lo);
int left = lo, right = hi;
var key = a[left];
while (left < right) {
// 从右向左遍历,找到小于key的,放入下标left中
// !less(a[right], key) <=> !(a[right] < key) <=> a[right] >= key
// 相等也要移动
while (left < right && !less(a[right], key)) right--;
a[left] = a[right];
// 从左向右遍历,找到大于key的,放入下标right中
// !less(key, a[left]) <=> !(key < a[left]) <=> a[left] <= key
// 相等也要移动
while (left < right && !less(key, a[left])) left++;
a[right] = a[left];
}
// 此时left == right, 这就是所谓的轴
// 把key放入轴中，轴左边的都<key,轴右边的都>key
a[left] = key;
// 此时轴在数组中间，说明把数组分成两部分，此时要对这两部分分别进行快排
advancedSort2(a, lo, left - 1);
advancedSort2(a, left + 1, hi);
}
/**
* 使用插排排序a[lo...hi]子区间
*
* @param a 排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static <K extends Comparable<K>> void insertionSort(K[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}
/**
* 寻找数组a中三个元素的中位数, 返回index
*
* @return 中位数元素index
*/
private static <K extends Comparable<K>> int median3(K[] a, int i, int j, int k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}
需要再次强调的是: 挖坑法在后面的测试中性能并不令人满意
② 三向切分的快排
三向切分的快排(信息量最优的快速排序): 适用于大量重复元素的排序
从左至右遍历数组一次:
指针lt使得a[lo…lt-1]中的元素都小于key
指针gt使得a[gt+1…hi]中的元素都大于key
指针i使得a[lt…i-1]中的元素都等于key
而a[i…gt]中的元素为未确定
处理时一开始i和lo相等, 进行三向比较:
- a[i] < key: 将a[lt]和a[i]交换, 将lt和i加一;
- a[i] > key: 将a[gt]和a[i]交换, 将gt减一;
- a[i] = key: 将i加一;
上述操作均会保证数组元素不变并且缩小gt-i的值(这样循环才会结束)
代码如下:
public static <K extends Comparable<K>> void threeWaySort(K[] a) {
threeWaySort(a, 0, a.length - 1);
}
/**
* 三向切分的快排(信息量最优的快速排序): 适用于大量重复元素的排序
*
* 从左至右遍历数组一次:
*
* - 指针lt使得a[lo...lt-1]中的元素都小于key
*
* - 指针gt使得a[gt+1...hi]中的元素都大于key
*
* - 指针i使得a[lt...i-1]中的元素都等于key
*
* - 而a[i...gt]中的元素为未确定
*
* 处理时一开始i和lo相等, 进行三向比较:
*
* - a[i] < key: 将a[lt]和a[i]交换, 将lt和i加一;
* - a[i] > key: 将a[gt]和a[i]交换, 将gt减一;
* - a[i] = key: 将i加一;
*
* 上述操作均会保证数组元素不变并且缩小gt-i的值(这样循环才会结束)
*
* @param a 待排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static <K extends Comparable<K>> void threeWaySort(K[] a, int lo, int hi) {
if (hi <= lo) return;
// 子数组长度小于阈值, 使用插排
int n = hi - lo + 1;
if (n <= INSERTION_SORT_THRESHOLD) {
insertionSort(a, lo, hi);
return;
}
// 选择[lo, (lo+hi)/2 , hi]三者中的中位数作为轴
int m = median3(a, lo, lo + (hi - lo + 1) / 2, hi);
exch(a, m, lo);
int lt = lo, gt = hi;
var key = a[lt];
int i = lo + 1;
while (i <= gt) {
int cmp = a[i].compareTo(key);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else ++i;
}
threeWaySort(a, lo, lt -1);
threeWaySort(a, gt + 1, hi);
}
/**
* 寻找数组a中三个元素的中位数, 返回index
*
* @return 中位数元素index
*/
private static <K extends Comparable<K>> int median3(K[] a, int i, int j, int k) {
return (less(a[i], a[j]) ?
(less(a[j], a[k]) ? j : less(a[i], a[k]) ? k : i) :
(less(a[k], a[j]) ? j : less(a[k], a[i]) ? k : i));
}
/**
* 使用插排排序a[lo...hi]子区间
*
* @param a 排序数组
* @param lo 排序左边界
* @param hi 排序右边界
*/
private static <K extends Comparable<K>> void insertionSort(K[] a, int lo, int hi) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}5.性能测试
对快排的各种方法进行性能测试(注意测试同时对比了快排的另一种实现)
分别对五百万个随机数组和随机重复数组排序
package algorithm.sort;
import algorithm.util.iostream.StdOut;
import algorithm.util.random.RandomArrayUtil;
import algorithm.util.watch.Stopwatch;
import org.junit.Test;
import java.util.Arrays;
import static algorithm.sort.BaseSort.isSorted;
import static algorithm.sort.BaseSort.show;
import static algorithm.sort.QuickSort.advancedSort;
import static algorithm.sort.QuickSort.advancedSort2;
import static algorithm.sort.QuickSort.sort;
import static algorithm.sort.QuickSort.sort2;
import static algorithm.sort.QuickSort.threeWaySort;
public class QuickSortTest {
/**
* 对快排的各种方法进行性能测试
*
* 分别对五百万个随机数组和随机重复数组排序, 结果如下:
*/
@Test
public void compareSort() {
// 正常随机数组
Integer[] a11 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000000000, 5000000);
Integer[] a12 = Arrays.copyOf(a11, a11.length);
Integer[] a13 = Arrays.copyOf(a11, a11.length);
Integer[] a14 = Arrays.copyOf(a11, a11.length);
Integer[] a15 = Arrays.copyOf(a11, a11.length);
// 大量重复数组
Integer[] a21 = RandomArrayUtil.getRandomBoxedIntArray(0, 1000, 5000000);
Integer[] a22 = Arrays.copyOf(a21, a21.length);
Integer[] a23 = Arrays.copyOf(a21, a21.length);
Integer[] a24 = Arrays.copyOf(a21, a21.length);
Integer[] a25 = Arrays.copyOf(a21, a21.length);
System.out.println("Array created!");
Stopwatch stopwatch = new Stopwatch();
sort(a11);
StdOut.printf("%s (%.2f seconds)\n", "sort [random]:", stopwatch.elapsedTime());
sort(a21);
StdOut.printf("%s (%.2f seconds)\n", "sort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a11);
assert isSorted(a21);
System.out.println();
stopwatch = new Stopwatch();
sort2(a12);
StdOut.printf("%s (%.2f seconds)\n", "sort2 [random]:", stopwatch.elapsedTime());
sort2(a22);
StdOut.printf("%s (%.2f seconds)\n", "sort2 [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a12);
assert isSorted(a22);
System.out.println();
stopwatch = new Stopwatch();
advancedSort(a13);
StdOut.printf("%s (%.2f seconds)\n", "advancedSort [random]:", stopwatch.elapsedTime());
advancedSort(a23);
StdOut.printf("%s (%.2f seconds)\n", "advancedSort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a13);
assert isSorted(a23);
System.out.println();
stopwatch = new Stopwatch();
advancedSort2(a14);
StdOut.printf("%s (%.2f seconds)\n", "advancedSort2 [random]:", stopwatch.elapsedTime());
advancedSort2(a24);
StdOut.printf("%s (%.2f seconds)\n", "advancedSort2 [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a14);
assert isSorted(a24);
System.out.println();
stopwatch = new Stopwatch();
threeWaySort(a15);
StdOut.printf("%s (%.2f seconds)\n", "threeWaySort [random]:", stopwatch.elapsedTime());
threeWaySort(a25);
StdOut.printf("%s (%.2f seconds)\n", "threeWaySort [random + duplicate]:", stopwatch.elapsedTime());
assert isSorted(a15);
assert isSorted(a25);
System.out.println();
}
}测试的结果如下:
sort [random]: (2.23 seconds)
sort [random + duplicate]: (4.22 seconds)
sort2 [random]: (2.58 seconds)
sort2 [random + duplicate]: (32.91 seconds)
advancedSort [random]: (1.16 seconds)
advancedSort [random + duplicate]: (2.14 seconds)
advancedSort2 [random]: (1.55 seconds)
advancedSort2 [random + duplicate]: (26.64 seconds)
threeWaySort [random]: (2.38 seconds)
threeWaySort [random + duplicate]: (3.73 seconds)6.性能测试总结
由测试可见:
- advancedSort性能最优(因为优化的最好)
- threeWaySort处理重复数组的能力与advancedSort几乎相同, 且优于普通的快排
- 对于sort2系列, 优于采用的是挖坑法, 且没有对重复子数组进行特殊处理, 所以很容易陷入N^2复杂度!
快速排序的性能优胜者是: advancedSort
性能优化原因:
- 对小规模子数组采用插入排序: 避免了对小规模的数组进行递归而产生过多的小数组甚至是空数组调用栈
- 三取样切分, 选择子数组一小部分的中位数来切分(保证尽量切分均匀)
三.堆排序序优化及性能测试
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法
堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
1.算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)
- 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
2.动图演示
3.代码实现
package algorithm.sort;
/**
* 堆排序
*
* 主要借助维护最大堆稳定的sink()方法:
*
* 现将一个数组构造成为一个最大堆
*
* 然后以类似于每次在堆中将头元素(当前堆中最大值)放入末尾并删除的操作完成排序
*
* 时间: < O(2NlgN + 2N) 2N来自于堆的构造, 2NlgN来自于每次下沉操作最大可能需要2lgN次比较
*
* 空间: O(1)
*
* 堆排序的空间复杂度是O(1), 这在嵌入式等内存要求严格的场景下很有用!!!
*
* @author zk
*/
public class HeapSort extends BaseSort {
public static <K extends Comparable<K>> void sort(K[] a) {
int len = a.length;
buildMaxHeap(a);
for (int i = len - 1; i > 0; i--) {
exch(a, 0, i);
len--;
heapify(a, 0, len);
}
}
/**
* 建立最大堆
*
* @param a 原始数组
*/
private static <K extends Comparable<K>> void buildMaxHeap(K[] a) {
for (int len = a.length, i = len >> 1; i >= 0; i--) {
heapify(a, i, a.length);
}
}
/**
* 堆调整, 针对第i个元素重建堆
*
* @param a 堆数组
* @param i 针对第i个元素重建堆
*/
private static <K extends Comparable<K>> void heapify(K[] a, int i, int bound) {
int largest = i;
int left = 2 * i + 1, right = 2 * i + 2;
if (left < bound && less(a[largest], a[left])) {
largest = left;
}
if (right < bound && less(a[largest], a[right])) {
largest = right;
}
if (largest != i) {
exch(a, i, largest);
heapify(a, largest, bound);
}
}
}4.排序实例
public void sortTest() {
Integer[] a = RandomArrayUtil.getRandomBoxedIntArray(0, 1000, 50);
sort(a);
show(a);
assert isSorted(a);
}四.非比较排序介绍
本章介绍一些非比较算法, 这些非比较算法有时可以达到线性的时间复杂度(而已证明基于比较的排序不可能超过nlogn!)
但是需要注意的是, 这些非比较排序算法或多或少都有一定的局限性
1.计数排序
计数排序不是基于比较的排序算法，其核心在于: 将输入的数据值转化为键存储在额外开辟的数组空间中
作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数
① 算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
② 动图演示
③ 代码实现
代码说明:
为简单起见, 示例代码仅仅对int数组排序
package algorithm.sort;
/**
* 计数排序（Counting Sort）
*
* 计数排序不是基于比较的排序算法
*
* 其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中
*
* 作为一种线性时间复杂度的排序，计数排序要求: 输入的数据必须是有确定范围的整数
*
* 算法步骤:
*
* - 1.找出待排序的数组中最大和最小的元素；
* - 2.统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
* - 3.对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）;
* - 4.反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
*
* 评价:
*
* - 计数排序是一个稳定的排序算法
*
* - 当输入的元素是n个0到k之间的整数时: 时间复杂度是O(n+k),空间复杂度也是O(n+k),其排序速度快于任何比较排序算法
*
* - 当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法
*
* @author zk
*/
public class CountSort extends BaseSort {
public static void sort(int[] a) {
// 一：求取最大值和最小值，计算中间数组的长度
// 中间数组是用来记录原始数据中每个值出现的频率
int max = a[0], min = a[0];
for (int i : a) {
if (i > max) {
max = i;
}
if (i < min) {
min = i;
}
}
// 二：有了最大值和最小值能够确定中间数组的长度
int[] aux = new int[max - min + 1];
// 三.循环遍历旧数组计数排序: 统计原始数组值出现的频率到中间数组B中
for (int i : a) {
// 对应位置上+1
aux[i - min] += 1;
}
// 四.遍历输出
// 创建最终数组，就是返回的数组，和原始数组长度相等，但是排序完成的
// 记录最终数组的下标
int index = 0;
// 先循环每一个元素, 在计数排序器的下标中
for (int i = 0; i < aux.length; i++) {
// 循环出现的次数
// aux[i]:这个数出现的频率
for (int j = 0; j < aux[i]; j++) {
// 原来减少了min现在加上min，值就变成了原来的值
a[index++] = i + min;
}
}
}
}计数排序是一个稳定的排序算法
当输入的元素是 n 个0~k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法
当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法
④ 排序实例
public void sortTest() {
int[] a = RandomArrayUtil.getRandomIntArray(0, 1000, 20);
sort(a);
System.out.println(Arrays.toString(a));
assert isSorted(a);
}
public void sortTest2() {
int[] a = RandomArrayUtil.getRandomIntArray(0, 10, 100);
sort(a);
System.out.println(Arrays.toString(a));
assert isSorted(a);
}2.桶排序
桶排序是计数排序的升级版, 它利用了函数的映射关系，高效与否的关键就在于: 这个映射函数的确定
桶排序 (Bucket sort)的工作原理:
假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）
① 算法描述
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来
② 图片演示
③ 代码实现
算法说明:
作为演示, 排序要求: 输入的桶大小bucketSize, 应当大于待排序浮点数的整数部分, 且浮点数均大于零才行
(因为在getBucketIndex方法中仅仅取了浮点数的整数部分作为桶的index)
实际使用时, 应当使用不同的getBucketIndex()方法进行桶切分
package algorithm.sort;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
/**
* 桶排序（Bucket Sort）
*
* 桶排序是计数排序的升级版
*
* 它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定
*
* 工作原理:
*
* - 假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序
* （有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）
*
* 算法过程:
*
* - 1.设置一个定量的数组当作空桶；
* - 2.遍历输入数据，并且把数据一个一个放到对应的桶里去；
* - 3.对每个不是空的桶进行排序；
* - 4.从不是空的桶里把排好序的数据拼接起来
*
* 评价:
*
* - 桶排序最好情况下使用线性时间O(n)
*
* - 桶排序的时间复杂度取决于对各个桶之间数据进行排序的时间复杂度, 因为其它部分的时间复杂度都为O(n)
*
* - 很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
*
* 最坏时间: O(N^2) 所有的数据都放入了一个桶内，桶内自排序算法为插入排序
*
* 最好时间: O(N) 桶的数量越多，理论上分到每个桶中的元素就越少，桶内数据的排序就越简单，其时间复杂度就越接近于线性
*
* 极端情况下，区间小到只有1，即桶内只存放一种元素
*
* 此时桶内的元素不再需要排序，因为它们都是相同的元素，这时桶排序差不多就和计数排序一样了
*
* @author zk
*/
public class BucketSort extends BaseSort {
/**
* 设置桶的默认数量为5
*/
private static final int DEFAULT_BUCKET_SIZE = 5;
/**
* 这里仅仅作为演示, 排序要求:
*
* 输入的桶大小bucketSize, 应当大于待排序浮点数的整数部分, 且浮点数均大于零才行!
*
* (因为在getBucketIndex方法中仅仅取了浮点数的整数部分作为桶的index)
*
* @param arr 待排序数组
* @param bucketSize 桶大小(在本例中为浮点数整数部分最大值+1)
*/
public static void sort(double[] arr, int bucketSize) {
// 新建一个桶的集合
ArrayList<LinkedList<Double>> buckets = new ArrayList<>();
bucketSize = Math.max(bucketSize, DEFAULT_BUCKET_SIZE);
for (int i = 0; i < bucketSize; i++) {
// 新建一个桶，并将其添加到桶的集合中去
// 由于桶内元素会频繁的插入，所以选择 LinkedList作为桶的数据结构
buckets.add(new LinkedList<>());
}
// 将输入数据全部放入桶中并完成排序
for (double data : arr) {
int index = getBucketIndex(data);
insertSort(buckets.get(index), data);
}
// 将桶中元素全部取出来并放入arr中输出
int index = 0;
for (LinkedList<Double> bucket : buckets) {
for (Double data : bucket) {
arr[index++] = data;
}
}
}
/**
* 计算得到输入元素应该放到哪个桶内
*/
private static int getBucketIndex(double data) {
// 这里例子写的比较简单，仅使用浮点数的整数部分作为其桶的索引值
// 实际开发中需要根据场景具体设计
return (int) data;
}
/**
* 我们选择插入排序作为桶内元素排序的方法
* <p>
* 每当有一个新元素到来时，我们都调用该方法将其插入到恰当的位置
*/
private static void insertSort(List<Double> bucket, double data) {
ListIterator<Double> it = bucket.listIterator();
boolean insertFlag = true;
while (it.hasNext()) {
if (data <= it.next()) {
// 把迭代器的位置偏移回上一个位置
it.previous();
// 把数据插入到迭代器的当前位置
it.add(data);
insertFlag = false;
break;
}
}
if (insertFlag) {
// 否则把数据插入到链表末端
bucket.add(data);
}
}
}桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)
桶排序最好情况下使用线性时间O(n);
很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大
④ 排序实例
public void bucketSortTest() {
int maxBound = 1000;
double[] a = RandomArrayUtil.getRandomDoubleArray(0, maxBound, 20);
sort(a, maxBound + 1);
System.out.println(Arrays.toString(a));
assert isSorted(a);
}3.基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位
有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序, 最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前
① 算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
② 动图演示
③ 代码实现
package algorithm.sort;
/**
* 基数排序（Radix Sort）
*
* 基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前
*
* 算法步骤:
*
* - 1.取得数组中的最大数，并取得位数；
* - 2.arr为原始数组，从最低位开始取每个位组成radix数组；
* - 3.对radix进行计数排序（利用计数排序适用于小范围数的特点）
*
* 算法分析:
*
* 基数排序分别排序，分别收集，所以是稳定的
*
* 时间: 待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n)
*
* - 基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度
*
* - 而且分配之后得到新的关键字序列又需要O(n)的时间复杂度
*
* - 当然d要远远小于n，因此基本上还是线性级别的
*
* 空间: 基数排序的空间复杂度为O(n+k)，其中k为桶的数量
* (一般来说n>>k，因此额外空间需要大概n个左右)
*
* @author zk
*/
public class RadixSort extends BaseSort {
private static final int[] RADIX_DICT = {1, 10, 100, 1000, 10000, 1000000, 1000000, 10000000, 100000000, 100000000};
/**
* 基数排序
*
* @param arr 要排序的数组
* @param max 数组中最大的数有几位
*/
public static void sort(int[] arr, int max) {
// count数组用来计数
int[] count = new int[arr.length];
// bucket用来当桶
int[] bucket = new int[arr.length];
// k表示第几位，1代表个位，2代表十位，3代表百位, ...
for (int k = 1; k <= max; k++) {
// 把count置空，防止上次循环的数据影响
for (int i = 0; i < arr.length; i++) {
count[i] = 0;
}
// 分别统计第k位是0,1,2,3,4,5,6,7,8,9的数量
// 此循环用来统计每个桶中的数据的数量
for (int value : arr) {
count[getFigure(value, k)]++;
}
// 利用count[i]来确定放置数据的位置
for (int i = 1; i < arr.length; i++) {
count[i] = count[i] + count[i - 1];
}
// 执行完此循环之后的count[i]就是第i个桶右边界的位置
// 利用循环把数据装入各个桶中，注意是从后往前装
// 这里是重点，一定要仔细理解
for (int i = arr.length - 1; i >= 0; i--) {
int j = getFigure(arr[i], k);
bucket[count[j] - 1] = arr[i];
count[j]--;
}
// 将桶中的数据取出来，赋值给arr
for (int i = 0, j = 0; i < arr.length; i++, j++) {
arr[i] = bucket[j];
}
}
}
/**
* 此函数返回整型数i的第k位是什么
*
* @param i 整数i
* @param k 求i的第k位
* @return 整型数i的第k位的值
*/
private static int getFigure(int i, int k) {
return (i / RADIX_DICT[k - 1]) % 10;
}
}④ 排序实例
public void sortTest() {
int[] a = RandomArrayUtil.getRandomIntArray(0, 9999, 20);
sort(a, 4);
System.out.println(Arrays.toString(a));;
assert isSorted(a);
}附录
上篇见: 几种常见排序方法的优化(上)
文中部分说明内容转自: 十大经典排序算法（动图演示）
源代码:
- 排序类: https://github.com/JasonkayZK/Java_Algorithm/tree/master/src/main/java/algorithm/sort
- 排序测试: https://github.com/JasonkayZK/Java_Algorithm/tree/master/src/test/java/algorithm/sort
如果觉得文章写的不错, 可以关注微信公众号: Coder张小凯
内容和博客同步更新~