Java——从插入排序到归并排序
目录
前言：
本文将详细介绍七大排序
插入排序：直接插入排序，希尔排序
选择排序：直接选择排序，堆排序
交换排序：冒泡排序，快速排序
归并排序
此外，还会拓展介绍非比较排序（计数排序，基数排序，桶排序），分析各算法的时间复杂度，空间复杂度与稳定性。
一.排序的基本概念
1.1什么是排序？
排序：是将一串记录（或数据元素）按照某个或某些关键字的大小，递增（升序）或递减（降序）排列的操作
1.2稳定性
待排序序列中存在多个相同的关键字记录。若排序后，这些记录的相对次序保持不变，则该排序算法是稳定的。
1.3内部排序和外部排序
内部排序：待排序数据全部存放在内存中完成排序。
外部排序：数据量太大，无法一次性装入内存，需要借外存进行排序，典型代表：归并排序
二.插入排序
2.1直接插入排序
将待排序序列中的元素逐个插入到已有序的子序列中，知道全部有序。
步骤：（升序）
1.从第二个元素（下标1）开始，将其视为待插入元素temp
2.从该元素的前一个位置开始向前扫描，若已排序元素大于temp，则将其后移。
3.找到合适位置后，将temp插入。
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int tmp = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > tmp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = tmp;
}
}性能分析;
最好情况（完全有序）：O（N）
最坏情况（逆序）：O（N^2）
空间复杂度：O(1)
稳定性：稳定
2.2希尔排序（缩小增量排序）
希尔排序是直插入排序的改进版。它先将整个序列按某个增量（gap）分组，对每组进行直接插入排序，然后逐渐缩小增量，直到gap=1时进行最后一次直接插入排序。目的是让序列在最后一次排序前基本有序，从而提升效率。
public static void shellSort(int[] arr) {
int gap = arr.length;
while (gap > 1) {
gap = gap / 3 + 1; // 常用增量序列
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j = i - gap;
while (j >= 0 && arr[j] > tmp) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = tmp;
}
}
}时间复杂度：非常复杂，依赖增量序列
空间复杂度：O(1)
稳定性：不稳定
三.选择排序
3.1直接选择排序
每次从未排序区间选出最小（最大）的元素，放入已排序区间的末尾。
public static void selectSort(int[] arr) {
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 tmp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = tmp;
}
}
}性能：
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
3.2堆排序
利用堆数据结构进行选择排序。升序——>建大根堆，降序——>建小根堆。每次将堆顶元素和末尾交换，堆大小减一，再向下调整。
步骤：
1.建堆（从最后一个非叶子节点开始向下调整）
2.交换堆顶与堆末尾元素，堆大小减1，然后向下调整堆顶。
3.重复步骤2，直到堆大小为1.
public static void heapSort(int[] arr) {
// 1. 建大堆
for (int i = (arr.length - 2) / 2; i >= 0; i--) {
shiftDown(arr, i, arr.length);
}
// 2. 排序
int end = arr.length - 1;
while (end > 0) {
// 交换堆顶与末尾
int tmp = arr[0];
arr[0] = arr[end];
arr[end] = tmp;
// 向下调整，范围 [0, end)
shiftDown(arr, 0, end);
end--;
}
}
private static void shiftDown(int[] arr, int parent, int size) {
int child = 2 * parent + 1;
while (child < size) {
if (child + 1 < size && arr[child + 1] > arr[child]) {
child++;
}
if (arr[parent] >= arr[child]) {
break;
}
int tmp = arr[parent];
arr[parent] = arr[child];
arr[child] = tmp;
parent = child;
child = 2 * parent + 1;
}
}性能：
时间复杂度：O(N logN)（建堆O(N)，每次调整O(logN)）
空间复杂度：O(1)
稳定性：不稳定
四.交换排序
4.1冒泡排序
相邻元素两两比较，若顺序错误就交换，每一趟将最大（或最小）元素放到最后
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
swapped = true;
}
}
if (!swapped) break; // 没有交换说明已有序
}
}性能：
时间复杂度：最好O(N)（已经有序）；最坏O(N^2)
空间复杂度：O(1)
稳定性：稳定
4.2快速排序
分治法。选择一个基准值（pivot），将数组分为左子数组和右子数组，然后递归排序左右子数组。
4.2.1三种划分法
1.Hoare（左右指针法）
private static int partitionHoare(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
while (i < j && arr[i] <= pivot) i++;
swap(arr, i, j);
}
swap(arr, left, i);
return i;
}2.挖坑法
private static int partitionPit(int[] arr, int left, int right) {
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
return i;
}3.前后指针法
private static int partitionPrevCur(int[] arr, int left, int right) {
int prev = left;
int cur = left + 1;
while (cur <= right) {
if (arr[cur] <= arr[left] && ++prev != cur) {
swap(arr, cur, prev);
}
cur++;
}
swap(arr, left, prev);
return prev;
}递归实现：
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
// 优化：三数取中（减少最坏情况概率）
int mid = left + ((right - left) >> 1);
if (arr[left] > arr[mid]) swap(arr, left, mid);
if (arr[left] > arr[right]) swap(arr, left, right);
if (arr[mid] > arr[right]) swap(arr, mid, right);
swap(arr, left, mid); // 将中值换到 left 作为基准
int pivot = partitionPit(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}4.2.2非递归实现（借助栈）
public static void quickSortNonR(int[] arr, int left, int right) {
Stack<Integer> stack = new Stack<>();
stack.push(left);
stack.push(right);
while (!stack.isEmpty()) {
int r = stack.pop();
int l = stack.pop();
if (l >= r) continue;
int pivot = partitionPit(arr, l, r);
// 左区间 [l, pivot-1]
stack.push(l);
stack.push(pivot - 1);
// 右区间 [pivot+1, r]
stack.push(pivot + 1);
stack.push(r);
}
}
4.2.3优化策略
三数取中：选取left，mid，right的中位数作为基准，避免有序序列下的O(N^2)
小区间使用插入排序：当子数组长度小于某个阈值时，改用插入排序，减少递归深度
性能：
时间复杂度：最好O(N logN); 最坏（完全有序且没优化）O(N^2)
空间复杂度：O(logN)
稳定性：不稳定
快速排序是综合性能最好的通用排序算法，Java的Array.sort对基本类型使用双轴快速排序
五.归并排序
分治法，将数组分成两半，分别排序，再合并两个有序子数组
递归版：
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left >= right) return;
int mid = left + ((right - left) >> 1);
mergeSort(arr, left, mid, temp);
mergeSort(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, j = mid + 1, 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++];
// 拷贝回原数组
for (i = 0; i < t; i++) {
arr[left + i] = temp[i];
}
}非递归
public static void mergeSortNonR(int[] arr) {
int[] temp = new int[arr.length];
for (int gap = 1; gap < arr.length; gap *= 2) {
for (int i = 0; i < arr.length; i += 2 * gap) {
int left = i;
int mid = i + gap - 1;
int right = Math.min(i + 2 * gap - 1, arr.length - 1);
if (mid < right) {
merge(arr, left, mid, right, temp);
}
}
}
}性能：
时间复杂度：O(N logN)
空间复杂度：O(N)
稳定性;稳定
归并排序是唯一稳定的O(N logN)排序算法，特别适合外部排序（海量数据排序）
5.1外部排序场景
问题：内存只有1G，需要对100G数据排序
解决方案：
1.将100G文件分成200份，每份512M
2.分别将每份数据读入内存，排序后写回磁盘
3.对200个有序文件进行多路归并（如每次读取每个文件的最小元素，选出全局最小输出），最终的到整体有序文件。
六.非基于比较的排序
6.1计数排序
统计每个值出现的次数，然后按顺序输出。适用于数据范围小且集中的场景
步骤：
1.找出数组中的最大值Max和最小值Min。
2.创建长度为Max-Min+1的计数数组
3.遍历原数组，统计每个元素的出现次数
4.根据计数数组一次输出有序序列
public static void countSort(int[] arr) {
int max = arr[0], min = arr[0];
for (int num : arr) {
max = Math.max(max, num);
min = Math.min(min, num);
}
int[] count = new int[max - min + 1];
for (int num : arr) {
count[num - min]++;
}
int index = 0;
for (int i = 0; i < count.length; i++) {
while (count[i]-- > 0) {
arr[index++] = i + min;
}
}
}性能：
时间复杂度：O(N+range)
空间复杂度：O(range)
稳定性：稳定
6.2基数排序
按为排序（个位，十位，百位……），借助队列或计数排序，适用于整数或定长字符串
6.3桶排序
将元素分配到有限数量的桶中，每个桶再单独排序，最后合并
更多推荐
8
0- 0
已为社区贡献20条内容
所有评论(0)