前言：
算法是计算机科学的基础，它们使计算机能够执行各种任务，从简单的计算到复杂的问题解决。通过设计和分析高效的算法，我们可以创建更快速、更高效的计算机程序。以下是常见的计算机八大排序算法
目录
排序：
排序是一种将数据元素按特定顺序排列的过程。它是一种基本的数据处理操作，在计算机科学和许多其他领域都有广泛的应用。
排序算法根据给定的比较函数将元素排列成升序或降序。比较函数定义了如何比较两个元素并确定它们的顺序
| 排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9)， R是基数(个十百) |
| Shell | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
插入排序：
顾名思义是将每个元素插入到前面已排序的子列表中来对列表进行排序。
示例：
初始状态 3，1，5，7，2，4，9，6（共8个数）
有序表：3；无序表：1，5，7，2，4，9，6
1.第一次循环，从无序表中取出第一个数 1，把它插入到有序表中，使新的数列依旧有序
有序表：1，3；无序表：5，7，2，4，9，6
2.第二次循环，从无序表中取出第一个数 5，把它插入到有序表中，使新的数列依旧有序
有序表：1，3，5；无序表：7，2，4，9，6
3.第三次循环，从无序表中取出第一个数 7，把它插入到有序表中，使新的数列依旧有序
有序表：1，3，5，7；无序表：2，4，9，6
4.第四次循环，从无序表中取出第一个数 2，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，5，7；无序表：4，9，6
5.第五次循环，从无序表中取出第一个数 4，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，7；无序表：9，6
6.第六次循环，从无序表中取出第一个数 9，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，7，9；无序表：6
7.第七次循环，从无序表中取出第一个数 6，把它插入到有序表中，使新的数列依旧有序
有序表：1，2，3，4，5，6，7，9；无序表：（空）
代码：
public class InsertSort {
public static void insertSort(int[] arr){
int j = 0;
int temp = 0;//临时变量
for(int i = 1;i < arr.length;i++){//从第二个数开始比较
temp = arr[i]; //将当前数插入到已经有序的数组中
for(j = i - 1;j >= 0;j--){
if(arr[j] > temp){//如果前面的数大于当前数，将他后移
arr[j+1] = arr[j];
}else{
break;
}
}
arr[j+1] = temp;//将当前轮数的数放到应该在的位置
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
int[] arr = {1,32,2,12,33};
insertSort(arr);
}
}
希尔排序：
希尔排序是一种插入排序的改进版本，它通过将数组分成较小的子数组并对每个子数组进行插入排序来工作。
思想：
希尔排序基于这样一个事实：如果一个数组已经部分有序，那么对它进行插入排序会更有效率。因此，希尔排序首先将数组分成较小的子数组，对每个子数组进行插入排序，然后逐渐减小子数组的大小，直到整个数组被排序。
算法步骤：
- 选择一个增量序列 h1, h2, ..., hk，其中 hk = 1。常见的增量序列是 h = n/2, n/4, n/8, ..., 1。
- 对于每个增量 hi，对数组进行以下操作：
- 将数组分成大小为 hi 的子数组。
- 对每个子数组进行插入排序。
- 重复步骤 2，直到增量序列中只剩下 hk = 1。
代码：
public class ShellSort {
public static void shellSort(int[] arr) {
int n = arr.length;
// 创建增量序列
int[] increments = { n/2, n/4, n/8, 1 };
for (int increment : increments) {
// 对每个增量进行插入排序
for (int i = increment; i < n; i++) {
int key = arr[i];
int j = i - increment;
while (j >= 0 && arr[j] > key) {
arr[j + increment] = arr[j];
j -= increment;
}
arr[j + increment] = key;
}
}
}
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 3, 1, 9, 4, 7, 6 };
shellSort(arr);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
时间复杂度：
希尔排序的时间复杂度很难准确分析，因为它取决于增量序列。对于某些增量序列，希尔排序的时间复杂度可以接近 O(n)，而对于其他增量序列，其时间复杂度可以接近 O(n^2)。
空间复杂度：
希尔排序的空间复杂度为 O(1)，因为它不需要任何额外的空间。
冒泡排序：
思想：
冒泡排序基于这样一个事实：如果两个相邻的元素处于错误的顺序，则可以交换它们的位置以使它们处于正确的顺序。因此，冒泡排序重复遍历列表，比较相邻元素并交换它们的位置，直到列表被排序。
算法步骤
- 从列表的开始遍历到列表的结尾。
- 对于列表中的每个元素，将其与后面的元素进行比较。
- 如果当前元素大于后面的元素，则交换这两个元素的位置。
- 重复步骤 1-3，直到列表中没有更多需要交换的元素。
可以理解为，第一个数和第二个数对比，如果第一个数比第二个数大，就交换位置（具体看你是升序还是降序，这里讲的是升序）第二个数比第三个数大以此类推...............
代码：
public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
boolean swapped;
do {
swapped = false;
for (int i = 1; i < n; i++) {
if (arr[i - 1] > arr[i]) {
int temp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = temp;
swapped = true;
}
}
n--;
} while (swapped);
}
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 3, 1, 9, 4, 7, 6 };
bubbleSort(arr);
System.out.println("Sorted array:");
for (int i : arr) {
System.out.print(i + " ");
}
}
}
运行结果：1 2 3 4 5 6 7 8 9
初始数组
[5, 2, 8, 3, 1, 9, 4, 7, 6]
第一次遍历
[2, 5, 8, 3, 1, 9, 4, 7, 6]
[2, 5, 3, 8, 1, 9, 4, 7, 6]
[2, 3, 5, 8, 1, 9, 4, 7, 6]
[2, 3, 5, 1, 8, 9, 4, 7, 6]
[2, 3, 1, 5, 8, 9, 4, 7, 6]
第二次遍历
[2, 1, 3, 5, 8, 9, 4, 7, 6]
[1, 2, 3, 5, 8, 9, 4, 7, 6]
[1, 2, 3, 5, 4, 8, 9, 7, 6]
[1, 2, 3, 4, 5, 8, 9, 7, 6]
[1, 2, 3, 4, 5, 6, 8, 9, 7]
第三次遍历
[1, 2, 3, 4, 5, 6, 7, 8, 9]快速排序：
思想：
快速排序是一种分治排序算法，它通过递归地将数组分成较小的子数组并对这些子数组进行排序来工作。
算法步骤
- 选择一个枢纽元素。
- 将数组分成两个子数组：
- 左子数组包含小于枢纽元素的元素。
- 右子数组包含大于枢纽元素的元素。
- 对左子数组和右子数组递归地应用快速排序。
示例：
考虑数组 [10, 7, 8, 9, 1, 5]。
- 选择枢纽元素为 5（数组中的最后一个元素）。
- 将数组分成两个子数组：
- 左子数组：[10, 7, 8, 9]
- 右子数组：[1]
- 对左子数组递归应用快速排序。
- 对右子数组递归应用快速排序。
- 合并排序后的子数组得到最终的排序数组：[1, 5, 7, 8, 9, 10]。
代码：
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return (i + 1);
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
quickSort(arr, 0, arr.length - 1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
直接选择排序：
思想：直接选择排序是一种简单有效的排序算法，它通过不断找到数组中剩余元素中的最小（或最大）元素，并将其与数组中的第一个元素交换，来对数组进行排序。
算法步骤
- 从数组的第一个元素开始，找到剩余元素中的最小（或最大）元素。
- 将找到的最小（或最大）元素与数组中的第一个元素交换。
- 将已排序的元素移到数组的末尾。
- 对剩余的元素重复步骤 1-3，直到数组完全排序。
代码：
public class SelectionSort {
public static void selectionSort(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;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
selectionSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
示例：
考虑数组 [10, 7, 8, 9, 1, 5]。
- 第一趟：
- 找到剩余元素中的最小元素（1）。
- 将最小元素与数组中的第一个元素（10）交换。
- 数组变为：[1, 10, 8, 9, 7, 5]。
- 第二趟：
- 找到剩余元素中的最小元素（5）。
- 将最小元素与数组中的第二个元素（10）交换。
- 数组变为：[1, 5, 10, 9, 7, 8]。
- 以此类推，继续进行排序，直到数组完全排序。
堆排序：
思想：堆排序是一种基于堆数据结构的排序算法。堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。堆排序通过将输入数组构建成一个最大堆（或最小堆），然后通过交换堆顶元素和最后一个元素并重新堆化堆来对数组进行排序。
算法步骤
- 将输入数组构建成一个最大堆（或最小堆）。
- 交换堆顶元素和最后一个元素。
- 重新堆化堆，排除最后一个元素。
代码：
public class HeapSort {
public 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--) {
// 交换堆顶元素和最后一个元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新堆化堆，排除最后一个元素
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) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
heapSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
遍历过程
考虑数组 [10, 7, 8, 9, 1, 5]。
构建最大堆
10
/ \
/ \
7 8
/ \ / \
9 1 5 ?
排序过程
交换堆顶元素（10）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
?
/ \
/ \
7 8
/ \ /
9 1 5
交换堆顶元素（8）和最后一个元素（5）。
重新堆化堆，排除最后一个元素。
5
/ \
/ \
7 8
/ \ /
9 1 ?
交换堆顶元素（9）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
?
/ \
/ \
7 8
/ \ /
9 1 5
交换堆顶元素（8）和最后一个元素（5）。
重新堆化堆，排除最后一个元素。
5
/ \
/ \
7 8
/ \ /
9 1 ?
交换堆顶元素（9）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
?
/ \
/ \
7 8
/ \ /
9 1 5
交换堆顶元素（8）和最后一个元素（5）。
重新堆化堆，排除最后一个元素。
5
/ \
/ \
7 8
/ \ /
9 1 ?
交换堆顶元素（9）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
?
/ \
/ \
7 8
/ \ /
9 1 5
交换堆顶元素（8）和最后一个元素（5）。
重新堆化堆，排除最后一个元素。
5
/ \
/ \
7 8
/ \ /
9 1 ?
交换堆顶元素（9）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
?
/ \
/ \
7 8
/ \ /
9 1 5
交换堆顶元素（8）和最后一个元素（5）。
重新堆化堆，排除最后一个元素。
5
/ \
/ \
7 8
/ \ /
9 1 ?
交换堆顶元素（9）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
?
/ \
/ \
7 8
/ \ /
9 1 5
交换堆顶元素（8）和最后一个元素（5）。
重新堆化堆，排除最后一个元素。
5
/ \
/ \
7 8
/ \ /
9 1 ?
交换堆顶元素（9）和最后一个元素（?）。
重新堆化堆，排除最后一个元素。
堆排序完成，数组已排序为 [1, 5, 7, 8, 9, 10]。
并归排序：
思想：
归并排序是一种分治排序算法，它通过将数组分成较小的子数组，对这些子数组进行排序，然后将排序后的子数组合并成一个排序后的数组来工作
- 如果数组只有一个元素，则返回。
- 将数组分成大约相等大小的两半。
- 对两个子数组分别应用归并排序。
- 将排序后的子数组合并成一个排序后的数组。
代码：
public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length <= 1) {
return;
}
int mid = arr.length / 2;
int[] leftHalf = new int[mid];
int[] rightHalf = new int[arr.length - mid];
for (int i = 0; i < mid; i++) {
leftHalf[i] = arr[i];
}
for (int i = mid; i < arr.length; i++) {
rightHalf[i - mid] = arr[i];
}
mergeSort(leftHalf);
mergeSort(rightHalf);
merge(arr, leftHalf, rightHalf);
}
private static void merge(int[] arr, int[] leftHalf, int[] rightHalf) {
int i = 0;
int j = 0;
int k = 0;
while (i < leftHalf.length && j < rightHalf.length) {
if (leftHalf[i] <= rightHalf[j]) {
arr[k] = leftHalf[i];
i++;
} else {
arr[k] = rightHalf[j];
j++;
}
k++;
}
while (i < leftHalf.length) {
arr[k] = leftHalf[i];
i++;
k++;
}
while (j < rightHalf.length) {
arr[k] = rightHalf[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
mergeSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
遍历过程
考虑数组 [10, 7, 8, 9, 1, 5]。
分解
[10, 7, 8, 9, 1, 5]
分成两半：
[10, 7, 8] [9, 1, 5]
递归排序
对两个子数组递归应用归并排序：
复制代码
[7, 8, 10] [1, 5, 9]
将排序后的子数组合并成一个排序后的数组：
[1, 5, 7, 8, 9, 10]
归并排序完成。
基数排序：
思想：
基数排序是一种非比较排序算法，它通过将元素按其各个位上的数字进行排序来工作。它特别适用于需要对大量整数进行排序的情况
算法步骤
- 确定数组中元素的最大值。
- 根据最大值的位数，对数组进行多次排序，每次按一个位上的数字排序。
- 从最低位开始，使用计数排序或桶排序等算法对数组进行排序。
- 对数组进行下一次排序，按下一位上的数字排序。
- 重复步骤 3-4，直到按所有位上的数字对数组进行排序。
代码：
public class RadixSort {
public static void radixSort(int[] arr) {
int max = getMax(arr);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, exp);
}
}
private static int getMax(int[] arr) {
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
private static void countingSort(int[] arr, int exp) {
int[] count = new int[10];
int[] output = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = arr.length - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < arr.length; i++) {
arr[i] = output[i];
}
}
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
遍历过程
考虑数组 [170, 45, 75, 90, 802, 24, 2, 66]。
确定最大值
最大值是 802。
按最低位排序
[170, 45, 75, 90, 802, 24, 2, 66]
对最低位上的数字进行计数排序：
[2, 24, 45, 66, 75, 90, 170, 802]
按下一位排序
[2, 24, 45, 66, 75, 90, 170, 802]
对下一位上的数字进行计数排序：
[2, 24, 45, 66, 75, 90, 170, 802]
按最高位排序
[2, 24, 45, 66, 75, 90, 170, 802]
对最高位上的数字进行计数排序：
[2, 24, 45, 66, 75, 90, 170, 802]
基数排序完成，数组已排序。