详解七大排序
目录一.直接插入排序
（1）基本头脑
（2）算法步调
（3）代码实现
（4）算法特性
（5）算法优化
（6）示例演示
二.希尔排序
（1）基本头脑
（2）算法步调
（3）代码实现
（4）算法特性
（5）算法优化
（6）实例演示
三.选择排序
（1）基本头脑
（2）算法步调
（3）代码实现
1）每次互换一个元素（最小元素）：
2）每次互换两个元素（一个最大元素，一个最小元素）：
（4）算法特性
（5）算法优化
（6）实例演示
四.堆排序
（1）基本头脑
（2）算法步调
（3）代码实现
（4）算法特性
（5）算法优化
（6）实例演示
1）建堆过程：
2）排序阶段
五.冒泡排序
（1）基本头脑
（2）算法步调
（3）代码实现
（4）算法特性
（5）算法优化
1. 提前终止（已实现）
2. 鸡尾酒排序（双向冒泡）
3. 记载末了互换位置
（6）实例演示
六.快速排序
（1）基本头脑
（2）算法步调
（3）代码实现
（4）算法特性
1. 高效的平均性能
2. 内存服从高
3. 实现灵活
最坏环境性能差
2. 不稳定排序
3. 递归实现的风险
（5）算法优化
1. 三数取中法选择基准值
2. 尾递归优化
3. 插入排序混合优化
（6）实例演示
示例1：基础快速排序流程
示例2：三数取中法优化
示例3：三路快排处理重复元素
七.归并排序
（1）基本头脑
（2）算法步调
（3）代码实现
（4）算法特性
（5）算法优化
1. 小规模数据利用插入排序
2. 淘汰不必要的数组复制
3. 提前终止合并过程
（6）实例演示
分解阶段
合并阶段
八.常见排序表
在数据结构中，排序是组织和处理数据的核心利用之一。它不仅是数据组织的核心手段，更是提升计算服从、优化资源利用的基础。其应用贯穿于数据库、利用系统、呆板学习、实时系统等领域，是算法设计与系统优化的基石。
选择适合的排序算法需综合思量数据规模、内存限定、稳定性需求及硬件特性。
这篇文章详细解析了七大排序的头脑、步调及其特点。
一.直接插入排序
（1）基本头脑
直接插入排序是一种简朴的排序算法，其基本头脑是：将待排序的元素逐个插入到已排序序列的适当位置，直到全部元素都插入完毕。
（2）算法步调
[*] 将第一个元素视为已排序序列
[*] 取出下一个元素，在已排序序列中从后向前扫描
[*] 如果已排序元素大于新元素，将该元素移到下一位置
[*] 重复步调3，直到找到已排序元素小于或等于新元素的位置
[*] 将新元素插入到该位置
[*] 重复步调2~5，直到全部元素都排序完成
（3）代码实现
for (int i = 1; i < array.length; i++) {
int temp = array;
int j = i - 1;
for (; j >= 0; j--) {
if (array > temp) {
/*array就是temp,但是1个i对应很多个j,所以i不是等于j+1;要用j+1来表示temp*/
array = array;
} else {
//不用改变元素位置,把取出来的temp再放回去
// array=temp;
break;
}
}
/*出了j的循环,证明j这时已经小于0了,也就是-1把取出来的temp再放回去j+1的位置,也就是下标0*/
array = temp;
} （4）算法特性
特性说明时间复杂度最好O(n)，最坏和平均O(n²)空间复杂度O(1)（原地排序）稳定性稳定排序适用场景小规模数据或基本有序数据长处 （1）实现简朴直观；
（2）稳定排序，不会改变雷同元素的相对次序；
（3）原地排序，不需要额外的存储空间（空间复杂度O（1））；
（4）对小规模或部分有序数据高效；
缺点 （1）时间复杂度高：平均O(n²);
（2）对逆序数据表现最差；
（3）数据移动频繁；
（5）算法优化
[*] 二分查找优化：在已排序部分利用二分查找确定插入位置（淘汰比较次数）
[*] 希尔排序：是插入排序的改进版，通过分组插入进步服从
（6）示例演示
以数组 为例：
初始:
第1轮: (插入2)
第2轮: (插入4)
第3轮: (插入6)
第4轮: (插入1)
第5轮: (插入3) 直接插入排序虽然简朴，但在处理小规模或部分有序数据时服从较高，且实现简朴，常被用作其他高级排序算法的子过程。
二.希尔排序
（1）基本头脑
希尔排序（Shell Sort）是插入排序的一种高效改进版本，由Donald Shell于1959年提出。其核心头脑是通过分组插入排序渐渐淘汰隔断（增量），最终实现整个数组的有序化。
希尔排序的头脑是通过分组来淘汰增量，提进步行多次小范围排序，使得数据有序化，末了当gap=1（末了一次排序）时，实现高服从的直接插入排序。
（2）算法步调
[*] 选择增量序列：确定一个递减的增量序列（例如初始增量为数组长度的一半，后续渐渐减半）。
[*] 分组插入排序：对每个增量隔断形成的子序列举行直接插入排序。
[*] 缩小增量：重复步调2，直到增量为1，此时整个数组作为一整个序列举行末了一次插入排序（希尔排序的末了一次排序就是直接插入排序）。
（3）代码实现
public static void shellSort(int[] array) {
int gap = array.length / 2;
/*随着gap的递减,分的组数也越来越少,直接组数为1,gap=1,这时进行直接插入排序*/
while (gap > 0) {
shell(array, gap);
gap = gap / 2;
}
}
//希尔排序内排序
public static void shell(int[] array, int gap) {
for (int i = gap; i < array.length; i++) {
int temp = array;
int j = i - gap;
for (; j >= 0; j = j - gap) {
if (array > temp) {
array = array;
} else {
break;
}
}
//此时j为负数,但不是-1
array = temp;
}
} 希尔排序是优化版的直接插入排序，旨在提升直接插入排序的服从。
并且希尔排序的末了一次排序就是直接插入排序，希尔排序之所以服从高是因为希尔排序通过前面几次小范围排序使得数组逐渐有序化（直接插入排序在数据有序化的时候服从高）。
（4）算法特性
特性说明时间复杂度最坏O(n²)，平均约 O(n log n)（当希尔增量（n/2递减）时）空间复杂度O(1)稳定性不稳定排序（雷同元素大概在排序时改变相对次序）适用场景中小规模数据排序（特殊是内存受限环境）长处 原地排序，不需要额外的存储空间；
比直接插入排序服从更高，更适合中等规模数据；
灵活性强，可以通过选择不同增量序列来优化性能。
缺点 不稳定排序，雷同元素大概在排序时改变相对次序；
增量依赖，性能受增量序列的选择影响较大；
理论复杂，最佳增量序列至今尚无统一结论。
希尔排序的时间复杂度分析是算法理论中的一个经典难题，其复杂度高度依赖增量序列的选择，现在无法精确计算全部环境下的时间复杂度。
（5）算法优化
Sedgewick增量优化：
利用Robert Sedgewick提出的增量序列实现的希尔排序改进版本。这种增量序列通过数学优化显着提升了希尔排序的性能，是现在已知综合表现最优的增量序列之一。
public static void shellSortOptimized(int[] arr) {
int n = arr.length;
// Sedgewick增量序列（部分）
int[] gaps = {1073, 281, 77, 23, 8, 1};
for (int gap : gaps) {
if (gap >= n) continue;
for (int i = gap; i < n; i++) {
int temp = arr;
int j;
for (j = i; j >= gap && arr > temp; j -= gap) {
arr = arr;
}
arr = temp;
}
}
} （6）实例演示
算法演示（以希尔增量为例）
初始数组：
增量 = 4：
分组：, , ,
排序后：
增量 = 2：
分组：,
排序后：
增量 = 1：
对整个数组插入排序，最终有序。 希尔排序的时间复杂度并非固定值，而是由增量序列决定。早期资料中的 O(n log n) 是对特定场景的简化描述，现代研究更倾向于具体分析增量序列的影响。实际开辟中，选择优化增量序列可显着提升性能，使其在小规模数据排序中具备竞争力。
三.选择排序
（1）基本头脑
选择排序是一种简朴直观的排序算法，其核心头脑是每次从未排序序列中选出最小（或最大）元素，将其放到已排序序列的末尾，直到全部元素排序完成。
（2）算法步调
[*] 初始化：整个数组视为未排序序列
[*] 寻找最小值：遍历未排序序列，找到最小元素的位置
[*] 互换位置：将最小元素与未排序序列的第一个元素互换
[*] 缩小范围：将已找到的最小元素归入已排序序列
[*] 重复利用：重复步调2~4，直到全部元素有序
（3）代码实现
1）每次互换一个元素（最小元素）：
public static void selectSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
if (array < array) {
minIndex = j;
}
}
//这时j已经遍历完数组,交换存储的最小值下标元素和array
swap(array, minIndex, i);
}
}
//定义方法:交换数组中两个下标对应的元素
public static void swap(int[] array, int i, int j) {
int temp = array;
array = array;
array = temp;
} 2）每次互换两个元素（一个最大元素，一个最小元素）：
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 > array) {
maxIndex = i;
} else if (array < array) {
minIndex = i;
}
}
//走完i循环,交换元素
swap(array, minIndex, left);
if (maxIndex == left) {
swap(array, left, right);
} else {
swap(array, maxIndex, right);
}
left++;
right--;
}
} （4）算法特性
特性说明时间复杂度固定 O(n²)（无论数据是否有序）空间复杂度O(1)（原地排序）稳定性通常不稳定（可特殊实现为稳定）互换次数最多 n-1 次互换比较次数固定 n(n−1)22n(n−1) 次长处
[*] 简朴直观：逻辑清晰，易于理解和实现
[*] 互换次数少：每轮仅需一次互换（相比冒泡排序更高效）
[*] 内存友好：原地排序，无需额外空间
[*] 适用小数据：数据量较小时实际性能尚可
缺点
[*] 服从低下：时间复杂度始终为 O(n²)，不适合大规模数据
[*] 无顺应性：无论数据初始状态如何，比较次数固定
[*] 不稳定排序：默认实现会改变雷同元素的相对次序
（5）算法优化
[*] 双向选择排序（鸡尾酒选择排序）
[*] 同时寻找最小值和最大值，淘汰循环次数
[*] 优化后比较次数淘汰约50%
[*] 堆排序优化
[*] 利用堆结构优化选择过程，时间复杂度降为 O(n log n)
[*] 实际上堆排序就是选择排序的高级变种
（6）实例演示
初始状态：
第1轮：找到最小值1 → 交换位置 →
第2轮：找到次小值2 → 无需交换 →
第3轮：找到最小值3 → 交换位置 →
第4轮：找到最小值4 → 交换位置 →
第5轮：数组已有序，排序完成 四.堆排序
（1）基本头脑
堆排序是一种基于完全二叉树结构的高效排序算法，利用堆的性质举行排序。其核心头脑是：
[*] 构建最大堆（或最小堆），将无序数组转换为堆结构
[*] 渐渐取出堆顶元素（最大值或最小值），与堆末尾元素互换并调解堆
[*] 重复调解直到堆大小为1，完成排序
（2）算法步调
[*] 构建最大堆
从末了一个非叶子节点开始，自底向上调解堆结构
[*] 堆排序阶段
[*] 互换堆顶与末尾元素（最大值归位）
[*] 缩小堆范围并重新调解堆
[*] 重复直到堆大小为1
（3）代码实现
public static void heapSort(int[] array) {
createHeap(array);
for (int end = array.length - 1; end >= 0; end--) {
//交换堆顶元素和最后一个元素
swap(array, 0, end);
//调整剩余元素为大根堆
siftDown(array, 0, end);
}
}
//定义方法:创建1个大根堆
public static void createHeap(int[] array) {
//确定最后1棵子树的位置
for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {
//siftDown是将1棵子树调整为大根堆,所以要使parent--,调整所有的子树至大根堆
siftDown(array, parent, array.length);
}
}
/*定义方法:向下调整;将1个堆调整为大根堆在数组array中向下调整到length位置*/
public static void siftDown(int[] array, int parent, int length) {
int child = 2 * parent + 1;
while (child < length) {
//拿到左右孩子最大值
if (child < array.length - 1 && array >= array) {
child++;
}
//如果孩子最大值大于父亲节点,交换两个节点的值
if (array > array) {
swap(array, child, parent);
//继续向下调整
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
} （4）算法特性
特性说明时间复杂度O(n log n)空间复杂度O(1)（原地排序）稳定性不稳定长处
[*] 时间复杂度稳定：始终包管O(n log n)的性能
[*] 内存高效：原地排序，无需额外存储空间
[*] 适合大数据：处理海量数据时不会出现快速排序的最坏环境
[*] 优先级队列基础：堆结构的紧张应用场景
缺点
[*] 不稳定排序：雷同值元素的相对位置大概改变
[*] 缓存不友好：跳跃式访问内存，大概影响实际性能
[*] 常数项较大：实际运行速率通常略慢于快速排序
（5）算法优化
[*] 非递归实现
将调解方法改为迭代实现，避免递归调用开销
[*] 多叉堆优化
利用三叉堆或四叉堆（适用于现代CPU缓存特性）
[*] 并行建堆
对大规模数据可接纳多线程并行调解子树
（6）实例演示
（以数组为例）
1）建堆过程：
初始数组：
转换为完全二叉树：
12
/\
11 13
/ \ /
56 7
调整非叶子节点（索引2→1→0）：
最终最大堆：
对应二叉树：
13
/\
11 12
/ \ /
56 7 2）排序阶段
第1次交换：13↔7 →
调整堆：
第2次交换：12↔6 →
调整堆：
...（重复过程）...
最终结果： 五.冒泡排序
（1）基本头脑
冒泡排序是一种简朴的互换排序算法，其核心头脑是通过相邻元素的比较和互换，将较大的元素渐渐“冒泡”到数组末尾。每一轮遍历都会确定一个当前未排序部分的最大值。
（2）算法步调
[*] 外层循环：控制排序轮数（共需 n-1 轮，n 为数组长度）
[*] 内层循环：遍历未排序部分，比较相邻元素
[*] 元素互换：若当前元素 > 后一个元素，则互换位置
[*] 优化判断：若某轮无互换发生，提前终止排序
（3）代码实现
public class BubbleSort {
public static void bubbleSort(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 > arr) {
// 交换元素
int temp = arr;
arr = arr;
arr = temp;
swapped = true;
}
}
// 若本轮无交换，说明已有序，提前结束
if (!swapped) break;
}
}
public static void main(String[] args) {
int[] arr = {64, 34, 25, 12, 22, 11};
bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // 输出
}
} （4）算法特性
特性说明时间复杂度最好O(n)，最坏和平均O(n²)空间复杂度O(1)（原地排序）稳定性稳定排序互换次数最多 n(n−1)22n(n−1) 次长处
[*] 实现简朴：代码逻辑直观，适合教学和小规模数据
[*] 稳定性：相等元素不会互换，保持原有次序
[*] 空间服从：无需额外内存空间
[*] 顺应性：对部分有序数据服从较高（通过优化标记）
缺点
[*] 服从低下：大规模数据排序速率显着下降
[*] 冗余比较：即便数据已有序仍需多轮遍历（未优化版本）
（5）算法优化
1. 提前终止（已实现）
[*] 通过swapped标记检测是否发生互换
[*] 最佳环境时间复杂度优化至O(n)（完全有序数组）
2. 鸡尾酒排序（双向冒泡）
[*] 瓜代举行正向和反向遍历
[*] 对包含大量无序小元素的数组更高效
鸡尾酒排序代码实例：
public static void cocktailSort(int[] arr) {
int left = 0;
int right = arr.length - 1;
boolean swapped;
while (left < right) {
// 正向遍历
swapped = false;
for (int i = left; i < right; i++) {
if (arr > arr) {
swap(arr, i, i+1);
swapped = true;
}
}
if (!swapped) break;
right--;
// 反向遍历
swapped = false;
for (int i = right; i > left; i--) {
if (arr < arr) {
swap(arr, i, i-1);
swapped = true;
}
}
if (!swapped) break;
left++;
}
}
3. 记载末了互换位置
[*] 记载每轮末了一次互换的位置，淘汰无效比较
int lastSwapIndex = 0;
int sortBorder = arr.length - 1;
for (int i = 0; i < arr.length - 1; i++) {
boolean swapped = false;
for (int j = 0; j < sortBorder; j++) {
if (arr > arr) {
swap(arr, j, j+1);
swapped = true;
lastSwapIndex = j;
}
}
sortBorder = lastSwapIndex;
if (!swapped) break;
} （6）实例演示
（以数组为例）
初始状态：
第1轮遍历：
2 5 4 6 1 3 → 2 4 5 6 1 3 → 2 4 5 1 6 3 → 2 4 5 1 3 6
确定最大值6归位
第2轮遍历：
2 4 5 1 3 → 2 4 1 5 3 → 2 4 1 3 5
确定次大值5归位
第3轮遍历：
2 4 1 3 → 2 1 4 3 → 2 1 3 4
确定4归位
第4轮遍历：
2 1 3 → 1 2 3
确定3归位（优化：此时已有序，提前结束） 六.快速排序
（1）基本头脑
快速排序是一种高效的分治算法，核心头脑是通过基准值（pivot）划分数组，将小于基准值的元素放在左侧，大于基准值的元素放在右侧，然后递归处理左右子数组，直到整个数组有序。
（2）算法步调
[*] 选择基准值（Pivot）：从数组中选取一个元素作为基准
[*] 分区利用（Partition）：重新排列数组，使小于基准值的元素在左，大于基准值的在右
[*] 递归排序：对左右两个子数组递归执行上述步调
（3）代码实现
public class QuickSort {
public static void quickSort(int[] arr) {
if (arr == null || arr.length <= 1) return;
sort(arr, 0, arr.length - 1);
}
private static void sort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
sort(arr, low, pivotIndex - 1);// 递归处理左子数组
sort(arr, pivotIndex + 1, high); // 递归处理右子数组
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr;// 选择最后一个元素为基准值
int i = low - 1; // 指向比基准值小的最后一个元素
for (int j = low; j < high; j++) {
if (arr <= pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high); // 将基准值放到正确位置
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr;
arr = arr;
arr = temp;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr);
System.out.println(Arrays.toString(arr)); // 输出
}
} （4）算法特性
特性说明平均时间复杂度O(n log n)最坏时间复杂度O(n²)（可通过优化避免）空间复杂度O(log n)（递归调用栈）稳定性不稳定最佳适用场景大规模随机数据长处 1. 高效的平均性能
[*] 时间复杂度：平均环境O(n log n)，实际应用中服从通常高于其他O(n log n)算法（如归并排序）
[*] 比较次数少：相比归并排序，快速排序的比较次数通常更少
2. 内存服从高
[*] 原地排序：只需O(log n)的栈空间（递归调用），不需要额外存储空间
[*] 缓存友好：次序访问内存，能有效利用CPU缓存
3. 实现灵活
[*] 可通过多种方式选择基准值（pivot）
[*] 可优化为三路快排处理重复元素
[*] 可与非递归实现结合
缺点 最坏环境性能差
[*] 最坏时间复杂度：O(n²)（当输入已排序且基准选择不当时）
[*] 办理方案：随机化基准选择或三数取中法
2. 不稳定排序
[*] 雷同元素的相对位置大概改变
[*] 示例：排序大概得到
3. 递归实现的风险
[*] 深度递归大概导致栈溢出
[*] 办理方案：尾递归优化或改为迭代实现
（5）算法优化
1. 三数取中法选择基准值
避免最坏环境（已排序数组导致O(n²)）
private static int selectPivot(int[] arr, int low, int high) {
int mid = low + (high - low)/2;
// 比较low/mid/high三个位置的元素
if (arr > arr) swap(arr, low, mid);
if (arr > arr) swap(arr, low, high);
if (arr > arr) swap(arr, mid, high);
return mid; // 返回中间值索引
} 2. 尾递归优化
淘汰递归调用栈深度
private static void sortOptimized(int[] arr, int low, int high) {
while (low < high) {
int pivotIndex = partition(arr, low, high);
if (pivotIndex - low < high - pivotIndex) {
sortOptimized(arr, low, pivotIndex - 1);
low = pivotIndex + 1;
} else {
sortOptimized(arr, pivotIndex + 1, high);
high = pivotIndex - 1;
}
}
}
3. 插入排序混合优化
对小规模子数组（如长度≤15）改用插入排序
private static final int INSERTION_THRESHOLD = 15;
private static void sort(int[] arr, int low, int high) {
if (high - low <= INSERTION_THRESHOLD) {
insertionSort(arr, low, high);
return;
}
// ...原快速排序逻辑
} （6）实例演示
示例1：基础快速排序流程
输入数组：
步调演示：
[*] 选择基准值：70（末尾元素）
[*] 分区过程：
[*] 10 < 70 → 保留
[*] 80 > 70 → 跳过
[*] 30 < 70 → 与80互换 →
[*] 90 > 70 → 跳过
[*] 40 < 70 → 与80互换 →
[*] 50 < 70 → 与90互换 →
[*] 最终互换基准值 →
[*] 递归处理左右子数组
示例2：三数取中法优化
输入数组：（已排序数组）
优化步调：
[*] 选择low=1, mid=4, high=7
[*] 三数排序后取中值：4
[*] 分区后得到平衡划分，避免O(n²)最坏环境
示例3：三路快排处理重复元素
输入数组：
分区过程：
初始：lt=0, gt=6, i=1, pivot=3
步骤1：arr=1 < 3 → 交换lt(0)和i(1)
(lt=1, i=2)
步骤2：arr=3 == 3 → i++
(lt=1, i=3)
步骤3：arr=2 < 3 → 交换lt(1)和i(3)
(lt=2, i=4)
...最终得到：
<3的部分：
=3的部分：
>3的部分： 七.归并排序
（1）基本头脑
归并排序（Merge Sort）是一种经典的分治算法，由约翰・冯・诺伊曼在 1945 年提出。它的基本头脑是将一个大题目分解为多个小题目，分别办理这些小题目，末了将小题目的解合并起来得到大题目的解。
归并排序接纳分治计谋，具体分为两个阶段：
[*]分解（Divide）：将待排序的数组从中间分成两个子数组，然后递归地对这两个子数组继承举行分解，直到每个子数组只有一个元素（因为单个元素的数组本身就是有序的）。
[*]合并（Merge）：将两个有序的子数组合并成一个有序的数组。合并过程中，比较两个子数组的元素，将较小的元素依次放入新的数组中，直到两个子数组的全部元素都被放入新数组。
（2）算法步调
[*]分解阶段：
[*]找到数组的中间位置，将数组分成左右两部分。
[*]递归地对左右两部分举行分解，直到每个子数组只有一个元素。
[*]合并阶段：
[*]创建一个暂时数组，用于存放合并后的结果。
[*]比较左右两个子数组的元素，将较小的元素依次放入暂时数组中。
[*]将暂时数组中的元素复制回原数组。
（3）代码实现
private static void mergechild(int[] array, int left, int right) {
if (left >= right) {
return;
}
int mid = (left + right) / 2;
mergechild(array, left, mid);
mergechild(array, mid + 1, right);
merge(array,left,mid,right);
}
//定义方法:合并两个子数组
private static void merge(int[] array, int left, int mid, int right) {
int[] tempArray = new int;
int k = 0;//临时数组tempArray的下标
int start1 = left;
int start2 = mid + 1;
int end1 = mid;
int end2 = right;
//两个子数组中都有数据
while (start1 <= end1 && start2 <= end2) {
if (array > array) {
tempArray = array;
k++;
start2++;
} else if (array <= array) {
tempArray = array;
k++;
start1++;
}
}
//1个子数组中没有数据了,跳出while循环
while (start1 <= end1) {
tempArray = array;
k++;
start1++;
}
while (start2 <= end2) {
tempArray = array;
k++;
start2++;
}
//将tempArray中的元素复制回原数组
for (int i = 0; i < tempArray.length; i++) {
array=tempArray;
}
} （4）算法特性
特性说明平均时间复杂度 O(nlogn)空间复杂度 O(n)稳定性稳定最佳适用场景处理大规模数据长处
[*]稳定性：归并排序是一种稳定的排序算法，即相等元素的相对次序在排序前后不会改变。
[*]时间复杂度稳定：无论输入数据的分布如何，归并排序的时间复杂度都是 O(nlogn)。
缺点
[*]空间复杂度较高：需要额外的 O(n) 空间来存储暂时数组。
[*]常数因子较大：由于需要频繁地举行数组的复制和合并利用，归并排序的常数因子相对较大，在处理小规模数据时服从不如一些简朴的排序算法（如插入排序）。
（5）算法优化
1. 小规模数据利用插入排序
对于小规模的数据，插入排序的常数时间开销相对较小，性能大概比归并排序更好。因此当子数组规模较小时，可以接纳插入排序来处理，淘汰递归调用带来的开销。
2. 淘汰不必要的数组复制
在归并过程中，频繁地创建和复制暂时数组会带来肯定的性能开销。可以通过瓜代利用原数组和暂时数组来淘汰这种开销。
3. 提前终止合并过程
在合并两个有序子数组时，如果发现其中一个子数组的全部元素都已经小于另一个子数组的全部元素，就可以提前终止合并过程。
（6）实例演示
假设我们有一个待排序的数组
分解阶段
[*]起首将原数组从中间分成两部分： 和 。
[*]对这两个子数组继承分解， 分成 和 ； 分成 和 。
[*]继承分解， 分成 和 ； 分成 和 ； 分成 和 。此时全部子数组都只有一个元素，分解竣事。
合并阶段
[*]合并 和 得到 ；合并 和 得到 ；合并 和 得到 。
[*]合并 和 得到 ； 和 合并得到 。
[*]末了合并 和 得到最终的有序数组 。
八.常见排序表
排序算法时间复杂度（最好）时间复杂度（平均）时间复杂度（最坏）空间复杂度稳定性备注冒泡排序O(n)O(n²)O(n²)O(1)稳定简朴但服从低选择排序O(n²)O(n²)O(n²)O(1)不稳定互换次数最少插入排序O(n)O(n²)O(n²)O(1)稳定对小规模数据高效快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定实际应用中最快（优化后）归并排序O(n log n)O(n log n)O(n log n)O(n)稳定稳定且适合外部排序堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定适合大规模数据希尔排序O(n log n)O(n log² n)O(n²)O(1)不稳定插入排序的改进版
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]