十种排序算法
冒泡排序
一共进行 n - 1 轮，在每一轮排序中对相邻两元素进行比较，大的排在后面。
/**
* 冒泡排序
* 时间复杂度：最优 O(n)，最坏 O(n²)，平均 O(n²)
* 空间复杂度：O(1)，原地排序
* 稳定性：稳定
*/
private static void bubbleSort(int[] arr) {
int n = arr.length;
boolean flag = true;
for (int i = 0; i < n - 1; i++) {
flag = true;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
flag = false;
}
}
if (flag) break;
}
}
选择排序
同样进行 n - 1 轮，每一轮从待排序序列中挑出最小的元素，将其放至已排序序列的末尾。
/**
* 选择排序
* 时间复杂度：最优 O(n²)，最坏 O(n²)，平均 O(n²)
* 空间复杂度：O(1) 原地排序
* 稳定性：不稳定
* @param arr
*/
private static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
swap(arr, i, minIndex);
}
}
插入排序
同样进行 n - 1 轮，每一轮把待排序序列的第一个元素插进已排序序列里的核心位置。可以想想打牌时理牌的过程。
/**
* 插入排序
* 时间复杂度：最优 O(n)，最坏 O(n²)，平均 O(n²)
* 空间复杂度： O(1) 原地排序
* 稳定性：稳定
*/
private static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= 0 && temp < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
希尔排序
插入排序改进版，将待排序序列分为若干组，步长为 gap，分组执行插入排序，逐渐缩小步长至 1。目的就是在初期就让元素接近它的最终位置，减少整体的比较次数。
/**
* 希尔排序
* 时间复杂度：最优 O(n)，最坏和平均与间距序列的选取有关
* 空间复杂度： O(1) 原地排序
* 稳定性：不稳定
*/
private static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i - gap;
while (j >= 0 && temp < arr[j]) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
}
}
}
归并排序
分治法采用分而治之的思想，将大数组拆为小数组，对小数组排序，然后合并为大数组。 倍增法： 从左往右依次合并两个长度为 1 的有序段，等到若干长度为 2 的有序段； 从左往右依次合并两个长度为 2 的有序段，等到若干长度为 3 的有序段； 直至有序段长度为数组长度。
/**
* 归并排序
* 时间复杂度：最优 O(nlong)，，最坏 O(nlogn)，平均 O(nlogn)
* 空间复杂度： O(n) 不是原地排序
* 稳定性：稳定
* 分治法和倍增法两种实现方式
*/
private static void mergeSort(int[] arr) {
int n = arr.length;
if (n < 2){ return;}
int mid = n / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, n);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) arr[k++] = left[i++];
while (j < right.length) arr[k++] = right[j++];
}
快速排序
同样分治的思想，关键操作 partition，随机选取一个元素 pivot 来将数组分为两部分，经过partition 操作来使前一部分的元素值小于 pivot ，后一部分大于 pivot。然后递归的对两部分进行快速排序。
/**
* 快速排序
* 时间复杂度：最优 O(nlong)，，最坏 O(n²)，平均 O(nlogn)
* 空间复杂度： 考虑递归栈空间O(logn) 原地排序
* 稳定性：不稳定
*/
private static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int i = partition(arr, left, right);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
private static int partition(int[] arr, int left, int right) {
Random rand = new Random();
int i = left + rand.nextInt(0, right - left + 1);
int pivot = arr[i];
swap(arr, i, left);
i = left + 1;
int j = right;
while (true) {
while (i <= j && arr[i] < pivot) i++;
while (i <= j && arr[j] > pivot) j--;
if (i >= j) break;
swap(arr, i, j);
i++;
j--;
}
swap(arr, left, j);
return j;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
堆排序
思想就是将数组每一个元素给映射到一颗完全二叉树（堆）上，该树的每一个节点的值都大于子节点的值（大根堆）。每一步交换堆顶和数组的最后一个元素，然后重新调整堆。
/**
* 堆排序
* 时间复杂度：最优 O(nlong)，最坏 O(nlogn)，平均 O(nlogn)
* 空间复杂度： O(1) 原地排序
* 稳定性：不稳定
*/
private static void heapSort(int[] arr) {
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i >= 0 ; i--) {
swap(arr, 0, i);
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
计数排序
前面的七种都算是比较排序。而后三种通过额外的数据结构来统计元素的出现次数从而实现排序。
/**
* 计数排序
* 时间复杂度：最好 O(n+k)；最坏 O(n+k)；平均 O(n+k)
* 空间复杂度：O(n + k)（我觉得是） 不是原地排序
* 稳定性：从后往前填充稳定
*/
private static void countingSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
int range = max - min + 1;
int[] count = new int[range];
for (int num : arr) {
count[num - min]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
//count[i] 等于小于等于 i 的元素个数
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
output[count[arr[i] - min] - 1] = arr[i];
count[arr[i] - min]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
基数排序
以自然数为例，基数排序就是先对每个数按个位排序，然后十位百位。每一位的排序基于计数排序（不一定）。从第 1 关键字到第 k 关键字顺序比较为 MSD基数排序，反过来是 LSD基数排序。我实现的是后者
/**
* 基数排序
* 时间复杂度：最好 O(nk)；最坏 O(nk)；平均 O(nk)
* 空间复杂度：O(n+k), k 为最大元素位数，不是原地排序
* 稳定性：从后往前填充稳定
*/
private static void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for (int radix = 1; max / radix > 0 ; radix *= 10) {
countingSortByDigit(arr, radix);
}
}
private static void countingSortByDigit(int[] arr, int radix) {
int[] count = new int[10];
for (int i = 0; i < arr.length; i++) {
int digit = (arr[i] / radix) % 10;
count[digit]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int digit = (arr[i] / radix) % 10;
output[count[digit] - 1] = arr[i];
count[digit]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
桶排序
将数组元素分到若干个桶中，对每个桶内元素进行排序（使用其他排序算法），然后合并桶
/**
* 桶排序
* 时间复杂度：最优 O(n + k)，最坏 O(n²)，平均 O(n + k)
* 空间复杂度： O(n + k) 不是原地排序
* 稳定性：稳定
*/
private static void bucketSort(int[] arr, int bucketNum) {
int max = Arrays.stream(arr).max().getAsInt();
int min = Arrays.stream(arr).min().getAsInt();
List<List<Integer>> list = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
list.add(new ArrayList<>());
}
for (int num : arr) {
int index = (num - min) * (bucketNum - 1) / (max - min);
List<Integer> bucket = list.get(index);
bucket.add(num);
}
int arrIndex = 0;
for (List<Integer> bucket : list) {
Collections.sort(bucket);
for (Integer i : bucket) {
arr[arrIndex++] = i;
}
}
}
Java内置排序
Arrays.sort()
当数组元素为基本数据类型时，会根据数据类型进入对应的 sort 方法（方法重载）。随后调用 DualPivotQuickSort 类的 sort 方法。
关于 DualPivotQuickSort 类，源代码中是这样注释的（jdk21）
This class implements powerful and fully optimized versions, both sequential and parallel, of the Dual-Pivot Quicksort algorithm by Vladimir Yaroslavskiy, Jon Bentley and Josh Bloch. This algorithm offers O(n log(n)) performance on all data sets, and is typically faster than traditional (one-pivot) Quicksort implementations. There are also additional algorithms, invoked from the Dual-Pivot Quicksort, such as mixed insertion sort, merging of runs and heap sort, counting sort and parallel merge sort.
大致意思就是这个类是超级版本的双轴快速排序（两个 pivot）实现，性能超强，根据数据规模也会采用其他排序算法如混合插入排序、堆排序等。为什么是双轴呢，因为三个人研究证明双轴的改进针对长度较大的序列是一种有效的方式。
int end = high - 1, size = high - low;
/*
* Run mixed insertion sort on small non-leftmost parts.
*/
if (size < MAX_MIXED_INSERTION_SORT_SIZE + bits && (bits & 1) > 0) {
mixedInsertionSort(a, low, high - 3 * ((size >> 5) << 3), high);
return;
}
/*
* Invoke insertion sort on small leftmost part.
*/
if (size < MAX_INSERTION_SORT_SIZE) {
insertionSort(a, low, high);
return;
}
/*
* Check if the whole array or large non-leftmost * parts are nearly sorted and then merge runs.
*/
if ((bits == 0 || size > MIN_TRY_MERGE_SIZE && (bits & 1) > 0)
&& tryMergeRuns(sorter, a, low, size)) {
return;
}
/*
* Switch to heap sort if execution * time is becoming quadratic.
*/
if ((bits += DELTA) > MAX_RECURSION_DEPTH) {
heapSort(a, low, high);
return;
}
整个DualPivotQuickSort 类的 sort 方法就是一个巨大的 while 循环，循环前半部分进行一些条件判断，就是上面的代码，如果待排序的元素数量满足一定条件，则调用不同的排序方法。如果都不满足，则会执行双轴快排或普通快排，然后在快排里再次递归调用 sort，直至待排序元素数量满足上面的条件，调用其他排序然后 return 退出 while 循环。
当数组元素不为基本数据类型时，要么类实现了 Comparable 接口，自定义重写 compareTo 方法，要么调用 sort 方法时，传进去一个 Comparator 比较器，一般用 lamda 表达式。否则会报异常。
当执行 Arrays.sort() 方法时，进入的是下面的方法。方法注释中表明：该实现是一种稳定、自适应、迭代的归并排序。默认情况下排序实现为 Timsort，它结合了插入排序和归并排序的优点，是 python 标准库的默认排序算法。
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a, c);
else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
Collections.sort()
该方法根据 List 接口的具体实现会有不同的调用链路，但最终调用的还是 Arrays.sort()。
整理完毕。别人写出如此优秀的代码，如今能学习到也算是我的荣幸了。
这篇博客就到这里，错误不可避免，欢迎指正。我会持续更新，欢迎收藏我的网站。
参考文章：