Javajava算法
常见排序算法原理及代码实现
常见排序算法的原理、实现及性能分析。内容涵盖插入排序（含希尔排序）、选择排序（含堆排序）、交换排序（冒泡、快速）及归并排序。每种算法均提供了 Java 代码示例、时间复杂度、空间复杂度及稳定性说明。此外，还探讨了海量数据的外部排序问题及其解决方案。适合希望系统掌握排序算法的开发者阅读参考。
常见排序算法的原理、实现及性能分析。内容涵盖插入排序（含希尔排序）、选择排序（含堆排序）、交换排序（冒泡、快速）及归并排序。每种算法均提供了 Java 代码示例、时间复杂度、空间复杂度及稳定性说明。此外，还探讨了海量数据的外部排序问题及其解决方案。适合希望系统掌握排序算法的开发者阅读参考。
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且 r[i] 在 r[j] 之前，而在排序后的序列中，r[i] 仍在 r[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
当插入第 i(i>=1) 个元素时，前面的 array[0],array[1],…,array[i-1] 已经排好序，此时用 array[i] 的排序码与 array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将 array[i] 插入，原来位置上的元素顺序后移。
代码实现：
import java.util.Arrays;
public class InsertionSort {
/**
* 直接插入排序算法
* @param arr 待排序的数组
*/
public static void insertionSort(int[] arr) {
// 数组为空或只有一个元素时，直接返回
if (arr == null || arr.length <= 1) {
return;
}
// 从第二个元素开始遍历（第一个元素默认已排序）
for (int i = 1; i < arr.length; i++) {
// 待插入的元素
int key = arr[i];
// 与已排序部分的元素比较，从已排序部分的末尾开始
int j = i - 1;
// 将大于 key 的元素向后移动一位
while (j >= 0 && key < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
// 将 key 插入到正确位置
arr[j + 1] = key;
}
}
// 测试方法
public static void main(String[] args) {
// 测试数组
int[] testArr = {32, 26, 87, 72, 26, 17};
System.out.print("原始序列：");
printArray(testArr);
// 调用排序方法
insertionSort(testArr);
System.out.print("排序后序列：");
printArray(testArr);
}
// 辅助方法：打印数组
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
希尔排序法又称缩小增量法。希尔排序法的基本思想是：选定一个整数（增量），把待排序文件里的所有记录分成多个组，所有距离为该增量的记录分在同一组内，然后对每一组内的记录进行排序。之后，减小这个增量，重复上述分组和排序的操作。当增量最终变为 1 时，所有记录在同一个组内排好序。
下面为一个希尔排序的流程：
希尔排序代码实现：
public class ShellSort {
public 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;
// 对间隔为 gap 的子序列进行直接插入排序
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {12, 34, 54, 2, 26, 9, 17, 5};
System.out.print("原始数组：");
for (int num : arr) {
System.out.print(num + " ");
}
shellSort(arr);
System.out.print("\n排序后的数组：");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
- 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定。
- 稳定性：不稳定
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
在元素集合 array[i]–array[n-1] 中选择关键码最大 (小) 的数据元素。若它不是这组元素中的最后一个 (第一个) 元素，则将它与这组元素中的最后一个（第一个）元素交换。在剩余的 array[i]–array[n-2]（array[i+1]–array[n-1]）集合中，重复上述步骤，直到集合剩余 1 个元素。
直接选择排序代码示例：
public class SelectionSort {
// 直接选择排序方法
public static void selectionSort(int[] arr) {
// 数组为空或长度小于 2，无需排序
if (arr == null || arr.length < 2) {
return;
}
// 从第一个元素开始遍历
for (int i = 0; i < arr.length - 1; i++) {
// 假设当前元素是最小的
int minIndex = i;
// 在剩余元素中找到更小的
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 如果找到了更小的元素，则交换
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
// 测试方法
public static void main(String[] args) {
int[] array = {35, 26, 18, 47, 52, 9, 13};
System.out.print("排序前：");
for (int num : array) {
System.out.print(num + " ");
}
selectionSort(array);
System.out.print("\n排序后：");
for (int num : array) {
System.out.print(num + " ");
}
}
}
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
堆排序 (Heapsort) 是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
代码实现：
import java.util.ArrayList;
import java.util.List;
class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
this.parent = null;
}
}
public class HeapSortWithTree {
// 堆的根节点
private TreeNode root;
// 记录堆的大小
private int size;
// 记录最后一个节点（用于插入和交换）
private TreeNode lastNode;
/**
* 堆排序主方法
* @param array 待排序数组
* @return 排序后的数组
*/
public int[] sort(int[] array) {
if (array == null || array.length <= 1) {
return array;
}
// 1. 构建最大堆
buildMaxHeap(array);
// 2. 执行堆排序
int[] result = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
// 提取堆顶元素（最大值）
result[i] = extractMax();
}
return result;
}
/**
* 构建最大堆
*/
private void buildMaxHeap(int[] array) {
root = null;
size = 0;
lastNode = null;
// 逐个插入元素并调整堆
for (int num : array) {
insert(num);
}
}
/**
* 向堆中插入元素
*/
private void insert(int value) {
TreeNode newNode = new TreeNode(value);
size++;
if (root == null) {
root = newNode;
lastNode = root;
return;
}
// 找到插入位置（按完全二叉树规则）
TreeNode parent = findInsertParent();
if (parent.left == null) {
parent.left = newNode;
} else {
parent.right = newNode;
}
newNode.parent = parent;
lastNode = newNode;
// 向上调整以维持最大堆特性
bubbleUp(newNode);
}
/**
* 找到新元素应该插入的父节点（保持完全二叉树结构）
*/
private TreeNode findInsertParent() {
List<TreeNode> queue = new ArrayList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode current = queue.remove(0);
if (current.left == null || current.right == null) {
return current;
}
queue.add(current.left);
queue.add(current.right);
}
return null;
}
/**
* 向上调整：将节点与父节点比较，确保父节点值更大
*/
private void bubbleUp(TreeNode node) {
while (node.parent != null && node.value > node.parent.value) {
int temp = node.value;
node.value = node.parent.value;
node.parent.value = temp;
node = node.parent;
}
}
/**
* 向下调整：从指定节点开始，确保子树满足最大堆特性
*/
private void bubbleDown(TreeNode node) {
while (true) {
TreeNode largest = node;
if (node.left != null && node.left.value > largest.value) {
largest = node.left;
}
if (node.right != null && node.right.value > largest.value) {
largest = node.right;
}
if (largest == node) {
break;
}
int temp = node.value;
node.value = largest.value;
largest.value = temp;
node = largest;
}
}
/**
* 提取堆顶最大元素，并重新调整堆
*/
private int extractMax() {
if (root == null) {
throw new IllegalStateException("堆为空");
}
int maxValue = root.value;
size--;
if (size == 0) {
root = null;
lastNode = null;
return maxValue;
}
root.value = lastNode.value;
TreeNode newLastNode = findNewLastNode();
if (lastNode.parent != null) {
if (lastNode.parent.right == lastNode) {
lastNode.parent.right = null;
} else {
lastNode.parent.left = null;
}
}
lastNode = newLastNode;
bubbleDown(root);
return maxValue;
}
/**
* 找到删除最后一个节点后的新最后一个节点
*/
private TreeNode findNewLastNode() {
if (size == 1) {
return root;
}
List<TreeNode> queue = new ArrayList<>();
queue.add(root);
TreeNode result = root;
for (int i = 0; i < size - 1; i++) {
TreeNode current = queue.remove(0);
result = current;
if (current.left != null) {
queue.add(current.left);
}
if (current.right != null) {
queue.add(current.right);
}
}
return result;
}
public static void main(String[] args) {
HeapSortWithTree heapSort = new HeapSortWithTree();
int[] array = {14, 10, 8, 7, 9, 3, 2, 4, 1};
System.out.print("排序前：");
for (int num : array) {
System.out.print(num + " ");
}
int[] sortedArray = heapSort.sort(array);
System.out.print("\n排序后：");
for (int num : sortedArray) {
System.out.print(num + " ");
}
}
}
堆排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
代码实现：
public class BubbleSort {
/**
* 基础版冒泡排序
* 每次遍历将最大元素"浮"到末尾
*/
public static void bubbleSortBasic(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
/**
* 优化版冒泡排序
* 添加标志位，当某轮未发生交换时说明数组已有序，可提前结束
*/
public static void bubbleSortOptimized(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int n = arr.length;
boolean swapped;
for (int i = 0; i < n - 1; i++) {
swapped = false;
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] testArr1 = {64, 34, 25, 12, 22, 11, 90};
int[] testArr2 = {5, 1, 4, 2, 8};
System.out.print("基础版排序前：");
printArray(testArr1);
bubbleSortBasic(testArr1);
System.out.print("基础版排序后：");
printArray(testArr1);
System.out.print("\n优化版排序前：");
printArray(testArr2);
bubbleSortOptimized(testArr2);
System.out.print("优化版排序后：");
printArray(testArr2);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
// 假设按照升序对 array 数组中 [left, right) 区间中的元素进行排序
void QuickSort(int[] array, int left, int right) {
if (right - left <= 1) {
return;
}
int div = partion(array, left, right);
QuickSort(array, left, div);
QuickSort(array, div + 1, right);
}
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有：
private static int partition(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left];
while (i < j) {
while (i < j && array[j] >= pivot) {
j--;
}
while (i < j && array[i] <= pivot) {
i++;
}
swap(array, i, j);
}
swap(array, i, left);
return i;
}
private static int partition(int[] array, int left, int right) {
int i = left;
int j = right;
int pivot = array[left];
while (i < j) {
while (i < j && array[j] >= pivot) {
j--;
}
array[i] = array[j];
while (i < j && array[i] <= pivot) {
i++;
}
array[j] = array[i];
}
array[i] = pivot;
return i;
}
写法一：
private static int partition(int[] array, int left, int right) {
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (array[cur] < array[left] && array[++prev] != array[cur]) {
swap(array, cur, prev);
}
cur++;
}
swap(array, prev, left);
return prev;
}
写法二：
private static int partition(int[] array, int left, int right) {
int d = left + 1;
int pivot = array[left];
for (int i = left + 1; i <= right; i++) {
if (array[i] < pivot) {
swap(array, i, d);
d++;
}
}
swap(array, d - 1, left);
return d - 1;
}
快速排序优化
快速排序总结
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤：
代码示例：
public class MergeSort {
/**
* 归并排序主方法
* @param arr 待排序的数组
*/
public static void mergeSort(int[] arr) {
if (arr == null || arr.length <= 1) {
return;
}
int[] temp = new int[arr.length];
sort(arr, 0, arr.length - 1, temp);
}
private static void sort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = left + (right - left) / 2;
sort(arr, left, mid, temp);
sort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
}
private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[t++] = arr[i++];
} else {
temp[t++] = arr[j++];
}
}
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
t = 0;
while (left <= right) {
arr[left++] = temp[t++];
}
}
public static void main(String[] args) {
int[] testArr = {12, 11, 13, 5, 6, 7};
System.out.print("排序前：");
printArray(testArr);
mergeSort(testArr);
System.out.print("排序后：");
printArray(testArr);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
- 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
外部排序：排序过程需要在磁盘等外部存储进行的排序 前提：内存只有 1G，需要排序的数据有 100G 因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
先把文件切分成 200 份，每个 512 M 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以进行 2 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
| 排序方法 | 最好 | 平均 | 最坏 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 希尔排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不稳定 |
| 快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不稳定 |
| 归并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 稳定 |
本篇文章介绍了常见的排序，通过对代码和原理解释了各个算法的特征。最后介绍了对各种算法的复杂度及稳定度分析。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online