跳到主要内容Java 常见排序算法实现与原理分析 | 极客日志Javajava算法
Java 常见排序算法实现与原理分析
本文系统讲解了 Java 中常见的排序算法，涵盖插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序（含霍尔法、挖坑法、前后指针法及优化）、归并排序（递归与非递归）以及非比较排序（计数、基数、桶排序）。内容包含各算法的核心思想、Java 代码实现、时间复杂度、空间复杂度及稳定性分析，适合算法学习与面试准备。
ApiHolic3 浏览 排序
- 稳定的排序：排序之前和排序之后它们俩的相对顺序没有发生变化
- 内部排序：在内存上的排序
- 外部排序：需要借助磁盘等外部空间进行的排序
插入排序
- 思想：假设这组数据的第一个元素是有序的，从第二个元素和前面的元素进行比较，找到合适的位置进行插入
public static void insertSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int j = i - 1;
int tmp = array[i];
for (; j >= 0; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
分析
- 时间复杂度：O(N^2)
最坏情况：O(N^2)
最好情况：有序的数组，O(N)
数据越有序，排序越快
适用于待排序数组基本上趋于有序了，时间复杂度趋于 O(N)
- 空间复杂度：O(1)
- 稳定性：是一个稳定的排序
例子：5 5 7
稳定的排序可以改成不稳定的排序，但是不稳定的排序不能改成稳定的排序
希尔排序
- 对直接插入排序进行了优化，如果是 5 4 3 2 1 会退化为 O(N^2)
- 分组：分完组后，每组都采用直接插入排序
- 中间隔一些元素进行分组的好处：比较大的元素都往后走了，比较小的元素都往前走了
- 缩小增量到最后会把整体看成是一组，5 3 1 组，前面的 5 3 都是预排序，真正的排序是最后的一组
- 缩小增量的目的：为了让排序更接近 O(N)，为了让排序更快
public static void shellSort([] array) {
array.length;
(gap > ) {
gap /= ;
shell(array, gap);
}
}
{
( gap; i < array.length; i++) {
i - gap;
array[i];
(; j >= ; j -= gap) {
(array[j] > tmp) {
array[j + gap] = array[j];
} {
;
}
}
array[j + gap] = tmp;
}
}
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- Keycode 信息
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
- Escape 与 Native 编解码
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
- JavaScript / HTML 格式化
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
- JavaScript 压缩与混淆
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
int
int
gap
=
while
1
2
public
static
void
shell
(int[] array, int gap)
for
int
i
=
int
j
=
int
tmp
=
for
0
if
else
break
分析
- 时间复杂度：O(N^1.3 - N ^ 1.5)，时间复杂度不好计算
- 空间复杂度：O(1)
- 稳定性：不稳定的排序
public static void testInsert(int[] array) {
long startTime = System.currentTimeMillis();
int[] tmp = Arrays.copyOf(array, array.length);
Sort.insertSort(tmp);
long endTime = System.currentTimeMillis();
System.out.println(" " + (endTime - startTime));
}
public static void testShell(int[] array) {
long startTime = System.currentTimeMillis();
int[] tmp = Arrays.copyOf(array, array.length);
Sort.shellSort(tmp);
long endTime = System.currentTimeMillis();
System.out.println(" " + (endTime - startTime));
}
public static void initOrder(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = array.length - i;
}
}
public static void main(String[] args) {
int[] arr = new int[10000];
initOrder(arr);
testInsert(arr);
testShell(arr);
}
选择排序
在当前 i 下标对应的值的后面，找到后面最小的值和 i 下标对应的值交换
public static void swap(int i, int j, int[] array) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static void selectSort(int[] array) {
int n = array.length;
for (int i = 0; i < n; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (array[j] < array[i]) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
}
swap(i, minIndex, array);
}
}
双向选择排序
时间复杂度还是 O(N^2)
左边找最大的，右边找最小的，和第一个数和最后一个数交换
存在缺陷，maxIndex 下标可能是在 0 下标是最大的，0 下标会和最小值小标的值交换，那么 0 下标就不是最大值下标，应该更新为 maxIndex = minIndex
public static void selectSort2(int[] array) {
int left = 0;
int right = array.length - 1;
while (left < right) {
int minIndex = left;
int maxIndex = left;
for (int i = left + 1; i <= right; i++) {
if (array[i] < array[minIndex]) {
minIndex = i;
}
if (array[i] > array[maxIndex]) {
maxIndex = i;
}
}
swap(left, minIndex, array);
if (maxIndex == left) {
maxIndex = minIndex;
}
swap(right, maxIndex, array);
left++;
right--;
}
}
分析
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定的排序
堆排序
private static void shiftDown(int[] array, int parent, int len) {
int child = 2 * parent + 1;
while (child < len) {
if (child + 1 < len && array[child] < array[child + 1]) {
child++;
}
if (array[child] > array[parent]) {
swap(child, parent, array);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
private static void createHeap(int[] array) {
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
shiftDown(array, parent, array.length);
}
}
public static void heapSort(int[] array) {
createHeap(array);
int end = array.length - 1;
while (end > 0) {
swap(end, 0, array);
shiftDown(array, 0, end);
end--;
}
}
分析
- 时间复杂度：O(N * logN)
- 空间复杂度：O(1)
- 稳定性：不稳定的排序
冒泡排序
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length; i++) {
boolean flag = true;
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(j, j + 1, array);
flag = false;
}
}
if (flag) {
break;
}
}
}
分析
- 时间复杂度：O(N ^ 2)
- 空间复杂度：O(1)
- 稳定性：稳定的排序
快速排序
霍尔法
public static void quickSort(int[] array) {
quick(array, 0, array.length - 1);
}
private static void quick(int[] array, int start, int end) {
if (start >= end) {
return;
}
int pivot = partitionHoare(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
private static int partitionHoare(int[] array, int left, int right) {
int tmp = array[left];
int i = left;
while (left < right) {
while (left < right && array[right] >= tmp) {
right--;
}
while (left < right && array[left] <= tmp) {
left++;
}
swap(left, right, array);
}
swap(i, left, array);
return left;
}
- 为什么有等于号？
没有等于号，会死循环，比如两端都是 6
为什么先从右边开始，不先从左边开始？
先走左边的话，先遇到大的停下来，如果相遇的话，那么相遇位置的值就是大于基准元素的，这时候交换的话，6 的左边有一个数比 6 大
分析
- 时间复杂度：
最好情况下：O(N * logN)
每层都有 N 个节点，高度为 logN，需要每个节点都遍历到，N * logN 次遍历
最坏情况下：O(N^2)，有序/逆序，单分支的树
- 空间复杂度：
最好情况下：O(logN)
最坏情况下：O(N)，有序/逆序，单分支的树
递归左边再递归右边，递归右边左边没有释放
- 稳定性：不稳定的排序
挖坑法找基准
- 先走右边再走左边，以第一个元素为基准，并且拿出基准元素，基准元素的位置就是坑，如果右边找到比基准小的，把它放入坑中，左边找到比基准元素大的放到坑中，最后两者相遇，把基准元素放入其中
private static int partitionHole(int[] array, int left, int right) {
int tmp = array[left];
while (left < right) {
while (left < right && array[right] >= tmp) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= tmp) {
left++;
}
array[right] = array[left];
}
array[left] = tmp;
return left;
}
前后指针法
- 如果 cur 比基准元素小并且 cur 下标的值和 prev 下标的值不相等
public static int partition(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
while (cur <= right) {
while (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(cur, prev, array);
}
cur++;
}
swap(prev, left, array);
return prev;
}
题目
- 优先试挖坑法，其次是 Hoare，最后是前后指针法
快排的优化
三数取中法
- 三数取中法：left，right，mid 三个下标中的中间值和第一个数交换位置，然后右边找比基准元素小的值，左边找比基准元素大的值
规定 array[mid] <= array[left] <= array[right]
private static int middleNum(int[] array, int left, int right) {
int mid = (left + right) / 2;
if (array[left] < array[right]) {
if (array[mid] < array[left]) {
return left;
} else if (array[mid] > array[right]) {
return right;
} else {
return mid;
}
} else {
if (array[mid] > array[left]) {
return left;
} else if (array[right] > array[mid]) {
return right;
} else {
return mid;
}
}
}
private static void quick(int[] array, int start, int end) {
if (start >= end) {
return;
}
int index = middleNum(array, start, end);
swap(index, start, array);
int pivot = partition(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
只剩最后几层时，使用插入排序进行优化，降低递归次数，可以使用插入排序是因为前面递归成有序的序列了
public static void insertSort(int[] array, int left, int right) {
for (int i = left + 1; i <= right; i++) {
int j = i - 1;
int tmp = array[i];
for (; j >= left; j--) {
if (array[j] > tmp) {
array[j + 1] = array[j];
} else {
break;
}
}
array[j + 1] = tmp;
}
}
private static void quick(int[] array, int start, int end) {
if (start >= end) {
return;
}
if (end - start + 1 <= 15) {
insertSort(array, start, end);
return;
}
int index = middleNum(array, start, end);
swap(index, start, array);
int pivot = partition(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
非递归实现快排
- 找基准里面会进行交换元素，进行排序，外面就进行找到左右下标位置
public static void quickSortNor(int[] array) {
int start = 0;
int end = array.length - 1;
Stack<Integer> stack = new Stack<>();
int pivot = partitionHoare(array, start, end);
if (pivot - 1 > start) {
stack.push(start);
stack.push(pivot - 1);
} else if (pivot + 1 < end) {
stack.push(pivot + 1);
stack.push(end);
}
while (!stack.empty()) {
end = stack.pop();
start = stack.pop();
pivot = partitionHoare(array, start, end);
if (pivot - 1 > start) {
stack.push(start);
stack.push(pivot - 1);
} else if (pivot + 1 < end) {
stack.push(pivot + 1);
stack.push(end);
}
}
}
归并排序
- 分解：根据 mid 进行分解
合并：第一个有序段和第二个有序段，比较大小放入一个新的数组中
public static void mergeSort(int[] array) {
merge(array, 0, array.length - 1);
}
private static void merge(int[] array, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) / 2;
merge(array, start, mid);
merge(array, mid + 1, end);
mergeHeB(array, start, mid, end);
}
private static void mergeHeB(int[] array, int left, int mid, int right) {
int s1 = left;
int e1 = mid;
int s2 = mid + 1;
int e2 = right;
int k = 0;
int[] tmpArray = new int[right - left + 1];
while (s1 <= e1 && s2 <= e2) {
if (array[s1] < array[s2]) {
tmpArray[k++] = array[s1++];
} else {
tmpArray[k++] = array[s2++];
}
}
while (s1 <= e1) {
tmpArray[k++] = array[s1++];
}
while (s2 <= e2) {
tmpArray[k++] = array[s2++];
}
for (int i = 0; i < tmpArray.length; i++) {
array[i + left] = tmpArray[i];
}
}
分析
- 时间复杂度：O(N * logN)
- 空间复杂度：O(N)，因为每次合并数组的时候要开 O(N) 大小的额外空间
- 稳定性：稳定的排序
非递归实现归并排序
- 先一个一个有序，两个两个有序，四个四个有序，八个八个有序…
- gap = 1
left = i
mid = left + gap - 1
right = mid + gap
gap *= 2
- 每组合并完，最终就有序了
public static void mergeSortNor(int[] array) {
int gap = 1;
while (gap < array.length) {
for (int i = 0; i < array.length; i = i + 2 * gap) {
int left = i;
int mid = left + gap - 1;
int right = mid + gap;
if (mid >= array.length) {
mid = array.length - 1;
}
if (right >= array.length) {
right = array.length - 1;
}
mergeHeB(array, left, mid, right);
}
gap *= 2;
}
}
海量数据的排序
非比较的排序
计数排序
- 通过统计每次数字出现的次数，最后按照顺序从小到大输出这些数字
- 适用的场景：指定范围内的数据
public static void countSort(int[] array) {
int minVal = array[0];
int maxVal = array[0];
for (int i = 0; i < array.length; i++) {
if (minVal > array[i]) {
minVal = array[i];
}
if (maxVal < array[i]) {
maxVal = array[i];
}
}
int len = maxVal - minVal + 1;
int[] count = new int[len];
for (int i = 0; i < array.length; i++) {
count[array[i] - minVal]++;
}
int k = 0;
for (int i = 0; i < count.length; i++) {
while (count[i] > 0) {
array[k++] = i + minVal;
count[i]--;
}
}
}
分析
- 时间复杂度：O(Max(N，范围))
- 空间复杂度：O(范围)
- 稳定性：稳定的排序
基数排序
- 开 10 个大小的空间，分别依次比较个位大小，十位大小和百位大小，最终达到有序，每个空间都是一个队列
桶排序
- 先把数字放入一个范围的区间内进行排序，排好序依次拿出来，最终就有序了
