荐 详解8大排序算法——Java实现
程序员文章站
2022-12-20 23:37:45
一、分类二、实现2.1 冒泡排序2.1.1 介绍冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。2.2.2 优化因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)...
一、分类
二、实现
2.1 冒泡排序
2.1.1 介绍
冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。
2.2.2 优化
因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排
序写好后，在进行)
2.2.3 代码实现
package com.czn.sort;
import java.util.Arrays;
public class Sort1BubbleSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1 };
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void bubbleSort(int[] arr) {
// 打标记进行优化，如果arr本来就是有序的，那么在进行一次比较之后flag没有改变
// 通过判断flag的状态可以选择因为arr有序而直接退出或者arr无序继续进行比较
boolean flag = false;
// 控制外部循环的次数，每循环一次就确定一个有序数
for (int i = 0; i < arr.length - 1; i++) {
// 控制每趟循环内部的比较次数
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
// 通过判断flag的状态决定退出还是继续
if (!flag) {
break;
} else {
flag = false;
}
}
}
}
2.2简单选择排序
2.2.1 基本介绍
选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。
2.2.2 基本思想
选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0] ~ arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1] ~ arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i 次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1 次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1 次，得到一个按排序码从小到大排列的有序序列。
2.2.3 思路分析图
2.2.4 代码实现
package com.czn.sort;
import java.util.Arrays;
public class Sort2SelectSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, };
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void selectSort(int[] arr) {
// 控制外部循环的次数，每循环一次就确定一个有序数
for (int i = 0; i < arr.length - 1; i++) {
// 假设最小值是arr[i]
int min = arr[i];
// 最小值的索引
int minIndex = i;
// 遍历i之后的每个索引，找到arr的最小值及其索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < min) {
min = arr[j];
minIndex = j;
}
}
// 交换，实现从前向后依次有序
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
2.3 直接插入排序
2.3.1 基本介绍
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
2.3.2 基本思想
插入排序（Insertion Sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
2.3.3 思路分析图
2.3.4 代码实现
package com.czn.sort;
import java.util.Arrays;
public class Sort3InsertionSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertionSort(int[] arr) {
// 控制外部循环的次数，假设arr[0]已是有序，所以从i=1开始
for (int i = 1; i < arr.length; i++) {
// 记录当前值
int temp = arr[i];
// 当前索引的前一个索引
int preIndex = i - 1;
// preIndex>=0的目的是保证不会发生数组越界异常
// while循环的目的是为当前值找到一个适合自己插入的位置
while (preIndex >= 0 && temp < arr[preIndex]) {
// 向后挪一个位置
arr[preIndex + 1] = arr[preIndex];
// preIndex索引前移一个位置，以便继续判断插入的位置是否还要在前面一点
preIndex--;
}
// 退出while循环，说明找到了属于自己的位置
arr[preIndex + 1] = temp;
}
}
}
2.4 希尔排序
2.4.1 简单排序存在的问题
我们看简单的插入排序可能存在的问题.
数组arr = {2,3,4,5,6,1} 这时需要插入的数1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。
2.4.2 基本介绍
希尔排序是希尔（Donald Shell）于1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
2.4.3基本思想
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1 时，整个文件恰被分成一组，算法便终止
2.4.4 示意图
2.4.5 代码实现
package com.czn.sort;
import java.util.Arrays;
public class Sort3InsertionSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void insertionSort(int[] arr) {
// 控制外部循环的次数，假设arr[0]已是有序，所以从i=1开始
for (int i = 1; i < arr.length; i++) {
// 记录当前值
int temp = arr[i];
// 当前索引的前一个索引
int preIndex = i - 1;
// preIndex>=0的目的是保证不会发生数组越界异常
// while循环的目的是为当前值找到一个适合自己插入的位置
while (preIndex >= 0 && temp < arr[preIndex]) {
// 向后挪一个位置
arr[preIndex + 1] = arr[preIndex];
// preIndex索引前移一个位置，以便继续判断插入的位置是否还要在前面一点
preIndex--;
}
// 退出while循环，说明找到了属于自己的位置
arr[preIndex + 1] = temp;
}
}
}
2.5 快速排序
2.5.1 基本介绍:
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排
序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
2.5.2 基本思想:
将待排序数组分为两部分，比如分为左半部分和右半部分，在左半部分找比基准值（比如中间索引mid对应的值）大的数，在右半部分找比基准值小的数，再把找到的两个值进行交换，直到两个索引的标记重合，退出循环，得到一个数组具有以下特征：
- 基准值的左子数组都比基准值小
- 基准值的右子数组都比基准值大
再分别对左子数组和右子数组进行递归
2.5.3 代码实现:
package com.czn.sort;
import java.util.Arrays;
public class Sort5QuickSort {
public static void main(String[] args) {
int[] arr = { -9, 78, 0, 23, -567, 70 };
quickSort(arr, 0, 5);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int left, int right) {
// start是数组的左索引
int start = left;
// end是数组的右索引
int end = right;
// mid是中间索引
int mid = (left + right) / 2;
while (start < end) {
// 从[start,mid]之间找比mid大的数的索引
while (arr[start] < arr[mid]) {
start++;
}
// 从[mid,end]之间找比mid小的数的索引
while (arr[end] > arr[mid]) {
end--;
}
// 退出while循环的条件：start和end重合
if (start == end) {
break;
}
// 如果不退出，那么就进行交换
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
// 当数组是[0,1,2,0,1,2]的情况，arr[start]=2和arr[end]=2
// 进行交换的话还是[0,1,2,0,1,2]，所以下面的代码是防止进入死循环
if (arr[start] == arr[mid]) {
end--;
}
if (arr[end] == arr[mid]) {
start++;
}
}
// 退出while循环说明start和end重合了
// 以重合点分为左半部分和右半部分，准备进行递归
start++;
end--;
// 向右半部分递归
if (start < right) {
quickSort(arr, start, right);
}
// 向左半部分递归
if (end > left) {
quickSort(arr, left, end);
}
}
}
2.6 归并排序
2.6.1 介绍:
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修
补"在一起，即分而治之)。
2.6.2 示意图:
-
基本思想示意图
-
合并相邻有序子序列示意图：
2.6.3 代码实现:
package com.czn.sort;
import java.util.Arrays;
public class Sort6MergeSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
int[] temp = new int[arr.length];
mergeSort(arr, 0, 8, temp);
System.out.println(Arrays.toString(temp));
}
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
// 只要left<right的情况下，就继续分下去
if (left < right) {
// 中间的索引
int mid = (left + right) / 2;
// 向左半部分分
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) {
// 左半部分从left开始，用i做标记
int i = left;
// 右半部分从mid+1开始，用j做标记
int j = mid + 1;
// 临时数组的索引值
int index = 0;
// 将左半部分和右半部分的元素按照由小到大的顺序添加到temp数组
// 直到有一边的数据被添加完
while (i <= mid && j <= right) {
// 将两部分小的元素添加到temp数组
if (arr[i] < arr[j]) {
temp[index++] = arr[i++];
} else {
temp[index++] = arr[j++];
}
}
// 上面只是一边的元素被添加完，还有另一边的元素没有添加完
while (i <= mid) {
temp[index++] = arr[i++];
}
// 与上面同理
while (j <= right) {
temp[index++] = arr[j++];
}
// 给left边界做标记
int start = left;
// temp索引值置为0
index = 0;
// 将temp中的left到right的值复制到arr数组中
while (start <= right) {
arr[start++] = temp[index++];
}
}
}
2.7 基数排序
2.7.1 基本介绍：
- 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
- 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
- 基数排序(Radix Sort)是桶排序的扩展
- 基数排序是1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。
2.7.2 基本思想：
将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
2.7.3 代码实现：
package com.czn.sort;
import java.util.Arrays;
public class Sort7RadixSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
// 假定数组的第一个数是最大值
int max = arr[0];
// 遍历数组，找到最大值
for (int n = 1; n < arr.length; n++) {
if (max < arr[n]) {
max = arr[n];
}
}
// 获取数组中最大数的长度
int maxLength = (max + "").length();
// System.out.println("maxLength =" + maxLength);
// 最大数有几位就需要遍历多少次
for (int m = 0; m < maxLength; m++) {
// 创建一个二维数组，行表示桶，列表示桶的大小
int[][] bucket = new int[10][arr.length];
// 创建一个一维数组，用来代表每个桶有效数据的个数
int[] bucketElementsCounts = new int[10];
// 对原始数组进行处理
for (int i = 0; i < arr.length; i++) {
// 获取个位数的值，放到对应的桶中去
int digit = (int) (arr[i] / Math.pow(10, m)) % 10;
bucket[digit][bucketElementsCounts[digit]] = arr[i];
bucketElementsCounts[digit]++;
}
int index = 0;
// 对每个桶进行遍历
for (int j = 0; j < bucket.length; j++) {
// 说明桶里面有有效数据
if (bucketElementsCounts[j] != 0) {
// 对桶里面的数据进行遍历
for (int k = 0; k < bucketElementsCounts[j]; k++) {
arr[index] = bucket[j][k];
index++;
}
}
// 注意最后要把bucketElementsCounts数组的记录清空，不然里面的值会影响下一轮循环
bucketElementsCounts[j] = 0;
}
}
}
}
2.8 堆排序
2.8.1 基本介绍：
- 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
- 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意: 没有要求结点的左孩子的值和右孩子的值的大小关系。
- 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
- 大顶堆举例说明
- 小顶堆举例说明
- 一般升序采用大顶堆，降序采用小顶堆
2.8.2 基本思想：
将待排序序列构造成一个大顶堆
2) 此时，整个序列的最大值就是堆顶的根节点。
3) 将其与末尾元素进行交换，此时末尾就为最大值。
4) 然后将剩余n-1 个元素重新构造成一个堆，这样会得到n 个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.
2.8.3 示意图：
2.8.4 代码实现：
package com.czn.sort;
import java.util.Arrays;
public class Sort8HeapSort {
public static void main(String[] args) {
int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr) {
// 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
/*
* 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
* 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
*/
for (int j = arr.length - 1; j > 0; j--) {
// 交换
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
}
// 将一个数组(二叉树), 调整成一个大顶堆
/**
* 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 =>
* adjustHeap => 得到 {4, 9, 8, 5, 6} 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9,
* 8, 5, 6} => {9,6,8,5, 4}
*
* @param arr 待调整的数组
* @param i 表示非叶子结点在数组中索引
* @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
*/
public static void adjustHeap(int arr[], int i, int lenght) {
int temp = arr[i];// 先取出当前元素的值，保存在临时变量
// 开始调整
// 说明
// 1. k = i * 2 + 1 k 是 i结点的左子结点
for (int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
if (k + 1 < lenght && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值
k++; // k 指向右子结点
}
if (arr[k] > temp) { // 如果子结点大于父结点
arr[i] = arr[k]; // 把较大的值赋给当前结点
i = k; // !!! i 指向 k,继续循环比较
} else {
break;// !
}
}
// 当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
arr[i] = temp;// 将temp值放到调整后的位置
}
}
2.8.5 堆排序小总结：
1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
三、总结
3.1 排序算法的比较图
3.2 相关术语解释
- 稳定：如果a 原本在b 前面，而a=b，排序之后a 仍然在b 的前面；
- 不稳定：如果a 原本在b 的前面，而a=b，排序之后a 可能会出现在b 的后面；
- 内排序：所有排序操作都在内存中完成；
- 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
- 时间复杂度： 一个算法执行所耗费的时间。
- 空间复杂度：运行完一个程序所需内存的大小。
- n: 数据规模
- k: “桶”的个数
- In-place: 不占用额外内存
- Out-place: 占用额外内存
参考资料：尚硅谷_韩顺平_图解Java数据结构和算法 视频地址
本文地址：https://blog.csdn.net/Beyondczn/article/details/107356181