数据结构八大排序Java源码

文章目录 [1]. 堆排序[2]. 冒泡排序[3]. 选择排序[4]. （直接）插入排序[5]. 希尔排序（属于插入算法）[6]. 快速排序[7]. 归并排序[8]. 基数排序 王道数据结构排序讲解

排序算法最佳时间复杂度最坏时间复杂度平均时间复杂度空间复杂度适用性稳定性堆排序O(nlogn)O(nlogn)O(nlogn)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^2)O(n^2)O(1)适用于小数据量或基本有序稳定希尔排序O(nlogn)O(n^2)取决于步长序列O(1)适用于中等规模数据不稳定快速排序O(nlogn)O(n^2)O(nlogn)O(logn)适用于大数据量不稳定归并排序O(nlogn)O(nlogn)O(nlogn)O(n)适用于大数据量稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)适用于非负整数稳定 “最佳时间复杂度”指的是在最理想的情况下，而“最坏时间复杂度”则是在最差的情况下。对于每种排序算法，空间复杂度表示额外的存储空间需求。适用性方面，可以根据数据量的大小和特定的需求来选择合适的排序算法。稳定性指的是相等元素的相对顺序是否在排序后保持不变。 [1]. 堆排序

堆排序是一种高效的选择排序算法。它通过构建一个二叉堆（大顶堆或小顶堆），并反复从堆顶取出最大（或最小）元素，然后调整堆使其保持性质，从而实现排序。具体来说，堆排序首先将待排序的元素构建成一个堆，然后将堆顶元素与最后一个元素交换位置，并将堆的大小减一。接着对根节点进行堆化操作，使得剩余元素重新构成一个堆。重复以上步骤，直到堆为空，最后得到排序完毕的数组。

* 使用Java编写，对一组乱序数组进行 堆排序 升序使用大根堆 */ public class HeapSort { // 堆排序函数 public void heapSort(int[] arr) { int n = arr.length; // 构建堆 for (int i = n / 2 - 1; i >= 0; i--) { //因为从下标 0 到（n/2 -1）的结点都为分叉结点 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);//因为最上面的根元素被弹出堆，换成了原堆中的最后那个元素，所以重新从最上面开始调整，（堆结点的个数-1）=i } } // 调整堆函数 public 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 swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; heapify(arr, n, largest);//继续递归调整被交换过的子树 } } // 测试函数 public static void main(String[] args) { int[] arr = {4, 10, 3, 5, 1}; HeapSort heapSort = new HeapSort(); System.out.println("排序前："); for (int i : arr) { System.out.print(i + " "); } heapSort.heapSort(arr); System.out.println("\n排序后："); for (int i : arr) { System.out.print(i + " "); } } } /* * 输出结果: * 排序前： * 4 10 3 5 1 * 排序后： * 1 3 4 5 10 */ [2]. 冒泡排序

冒泡排序是一种简单但效率较低的排序算法。它通过不断地比较相邻的元素，并将较大（或较小）的元素逐渐移动到数组的一端，从而实现排序。具体来说，它会多次遍历数组，每次遍历时比较相邻元素并交换位置，直到整个数组排序完毕。因为较大（或较小）的元素像气泡一样逐渐浮出，所以称之为冒泡排序。

//冒泡排序 public class BubbleSort { public static void main(String[] args) { int[] ints = new int[]{23,24,54,-324,2,1,1,1,98}; bubbleSort(ints); for (int anInt : ints) { System.out.print(anInt + " "); } } public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length; i++) { boolean flag = true; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { flag = false; int temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } //优化：如果发现某一层完全没有交换次序，即：flag没有变为false，则，该序列已经为有序排列，结束循环 if (flag) { break; } } } } [3]. 选择排序

选择排序也是一种简单但效率较低的排序算法。它通过每次选择未排序部分的最小（或最大）元素，然后将其与未排序部分的第一个元素进行交换，从而逐渐将最小（或最大）元素放到已排序部分的末尾。具体来说，选择排序会遍历数组，每次遍历时找到未排序部分的最小（或最大）元素并交换位置，直到整个数组排序完毕。

//选择排序 public class SelectSort { public static void main(String[] args) { int[] ints = new int[]{23,24,54,-324,2,1,1,1,98}; selectSort(ints); for (int anInt : ints) { System.out.print(anInt + " "); } } //min ：最小值 //mindex ：最小值的下标 public static void selectSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int min = arr[i]; int minindex = i; for (int j = i + 1; j < arr.length; j++) { if (min > arr[j]) { min = arr[j]; minindex = j; } } //该排序没有分配多余的数组空间，经过一轮比较后，mindex是最终最小值min的下标 //如果mindex变化，因为没有申请额外空间存储，所以这里交换arr[i]和arr[mindex]的位置 if (i != minindex) { arr[minindex] = arr[i]; arr[i] = min; } } } } [4]. （直接）插入排序

插入排序是一种简单但高效的排序算法。它将数组分为已排序部分和未排序部分，然后逐个将未排序部分的元素插入到已排序部分的正确位置，从而实现排序。具体来说，插入排序从第二个元素开始，将其与前面的元素比较并插入正确的位置，然后继续对后面的元素进行插入操作，直到整个数组排序完毕。

//插入排序 public class InsertSort { public static void main(String[] args) { int[] ints = new int[]{23,24,54,-324,2,1,1,1,98}; insertSort(ints); for (int anInt : ints) { System.out.print(anInt + " "); } } //insertIndex: 待插入元素的下标 //insertValue: 带插入元素的值 //排序思想：从数组第二个元素开始遍历，该排序就是要将此时遍历到的元素插入前面的序列中，保证前面的序列从小到大 public static void insertSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int insertIndex = i; int insertValue = arr[i]; //while循环的目的：将arr[i]与前面的元素比较，找到第一个比它大的元素，然后插到该元素前面 while (insertIndex > 0 && insertValue < arr[insertIndex - 1]) { arr[insertIndex] = arr[insertIndex - 1]; insertIndex--; } arr[insertIndex] = insertValue; } } } [5]. 希尔排序（属于插入算法）

希尔排序是一种高效的排序算法，它通过将待排序的元素划分为若干组来进行排序，然后逐步减小组的大小，最终完成排序。

具体步骤如下：

首先，选择一个增量序列，通常为数组长度的一半，并将数组分为若干组。对每一组进行插入排序，即从第二个元素开始，逐个与前面的元素比较并插入正确的位置。逐步缩小增量序列，重新分组并进行插入排序，直到增量序列为1。最后，进行一次增量为1的插入排序，完成排序。

希尔排序与插入排序的关系和区别如下：

希尔排序是插入排序的改进版本，通过分组的方式，使得插入排序可以先比较距离较远的元素，从而更高效地移动元素。相比于插入排序，希尔排序的时间复杂度更优，可以达到O(n log n)级别，尤其在大规模数据的排序中表现良好。希尔排序是不稳定的排序算法，即同值的元素在排序后可能会改变相对顺序。相比于其他高效的排序算法，希尔排序的实现较为简单，且对于中小规模的数据集也有较好的性能表现。 //希尔排序 public class ShellSort { public static void main(String[] args) { int[] ints = new int[]{23,24,54,-324,2,1,1,1,98}; shellSort(ints); for (int anInt : ints) { System.out.print(anInt + " "); } } public static void shellSort(int[] arr) { //gap步长 for (int gap = arr.length / 2; gap > 0; gap /= 2) { for (int i = gap; i < arr.length; i++) { //插入式 间隔为gap的插入排序 int insertIndex = i; int insertValue = arr[i]; while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) { arr[insertIndex] = arr[insertIndex - gap]; insertIndex -= gap; } arr[insertIndex] = insertValue; } } } } [6]. 快速排序

快速排序是一种高效的分治排序算法。它选择一个基准元素，将数组分为两个子数组，一个子数组中的元素都小于基准元素，另一个子数组中的元素都大于基准元素，然后递归地对子数组进行排序，最后通过合并子数组得到排序完毕的数组。具体来说，快速排序选择一个基准元素，通过比较将其他元素分别放到基准元素的左边或右边，然后对左右子数组递归地进行快速排序，最后合并子数组得到排序完毕的数组。

import java.util.Arrays; public class QuickSort { public static void main(String[] args) { int[] ints = new int[]{23, -9, 78, 3, 34,3, 0, 34,23}; quickSort(ints, 0, ints.length - 1); System.out.println(Arrays.toString(ints)); } public static void quickSort(int[] arr, int left, int right) { if (left >= right) { //递归调用函数结束 return; } int l = left; int r = right; while (l < r) { //每次都以arr[left]为标准进行对比 while (l < r && arr[r] >= arr[left]) r--; while (l < r && arr[l] <= arr[left]) l++; //两次循环后，最终是l==r 此时arr[r]一定小于等于arr[left] if (r == l) { //此时该循环就结束了 int temp = arr[r]; arr[r] = arr[left]; arr[left] = temp; } else { int temp = arr[r]; arr[r] = arr[l]; arr[l] = temp; } } //此时r == l 索引r左边的元素小于arr[r] 索引r右边的元素大于arr[r]; //在分别对左右部分进行快排 quickSort(arr, left, l - 1); quickSort(arr, r + 1, right); } } [7]. 归并排序

归并排序是一种高效的分治排序算法。它的思想是将数组不断地二分分解，直到每个子数组只有一个元素，然后将相邻的子数组进行合并，直到最终得到排序完毕的数组。具体来说，归并排序会递归地将数组二分，然后对每个子数组进行归并操作，通过比较两个子数组的元素，按顺序合并成一个有序的子数组，最后不断合并子数组，直到整个数组排序完毕。

import java.util.Arrays; public class MergeSort { public static void main(String[] args) { int[] ints = new int[]{23, -9, 78, 3, 34,3, 0, 34,23}; //临时存储合并之后的数组 int[] temp = new int[ints.length]; mergeSort(ints, 0, ints.length - 1, temp); System.out.println(Arrays.toString(ints)); } public static void mergeSort(int[] arr, int left, int right, int[] temp) { //递归的结束条件 如果left<right,说明可以继续分，则继续可以调用该函数，否则就不能分，就直接return if (left < right) { //mid：被分的两个部分的中间索引 用于之后合并两个部分时用 int mid = (left + right) / 2; //将左边部分继续分 mergeSort(arr, 0, mid, temp); //将右边部分继续分 mergeSort(arr, mid + 1, right, temp); //代码运行到这里，递归已经调用完毕，开始回溯，从最开始的左右部分各一个元素开始回溯 merge(arr, left, mid, right, temp); } } public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; //左边部分的最左侧索引 int j = mid + 1; //右边部分的最左侧索引（当只有每个部分只有一个元素时，此时mid=left mid+1=right） int t = 0;//临时数组temp的索引，从0开始 //将分开的两部分合并 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[t] = arr[i]; t++;i++; } else { temp[t] = arr[j]; t++;j++; } } //如果左边部分有没有合并进去的，接着i继续合并 while (i <= mid) { temp[t] = arr[i]; t++;i++; } //如果右边部分有没有合并进去的，接着j继续合并 while (j <= right) { temp[t] = arr[j]; t++;j++; } //将临时数组temp的所存储的值，赋值给原数组arr t = 0; //原数组的索引需要从left开始，right结束 int tempLeft = left; while (tempLeft <= right) { arr[tempLeft] = temp[t]; t++;tempLeft++; } } } [8]. 基数排序

基数排序是一种非比较的排序算法，适用于有非负整数的数组。它按照个位、十位、百位等位数的大小进行排序，通过多次遍历数组，根据每个位数的值将数组元素进行分配和收集，最终得到排序完毕的数组。具体来说，基数排序首先选取一个最高位数，将数组按照该位数进行排序，然后再对下一位数进行排序，直到最低位数排序完成。基数排序利用了稳定排序的特性，在位数排序时保持相同位数值的元素相对顺序不变。

import java.util.Arrays; public class RedixSort { public static void main(String[] args) { int[] ints = new int[]{24,74, 3, 34,14, 4, 34,3434,24,3435,324,544,234,124}; //临时存储合并之后的数组 redixSort(ints); System.out.println(Arrays.toString(ints)); } public static void redixSort(int[] arr) { int[][] bucket = new int[10][arr.length]; int[] bucketElementCounts = new int[10]; //求出数组中高度最大值的位数（最大值拥有最大位数） int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (max < arr[i]) max = arr[i]; } int maxCount = (max + "").length(); //小技巧：将数转换成字符串，其长度即是其位数 for (int i = 0; i < maxCount; i++) { //将arr数组中的每个数存在bucket二维数组中 一维数组bucketElementCount用于记录每个桶所存的数的个数 for (int k = 0; k < arr.length; k++) { int value = arr[k] / (int)Math.pow(10, i) % 10; bucket[value][bucketElementCounts[value]] = arr[k]; bucketElementCounts[value]++; } int index = 0; //多次循环后，最终将bucket中最后存的所有数按顺序赋值给arr for (int k = 0; k < bucketElementCounts.length; k++) { if (bucketElementCounts[k] != 0) { for (int x = 0; x < bucketElementCounts[k]; x++) { arr[index] = bucket[k][x]; index++; } } //对k进行清0，用于下一循环 bucketElementCounts[k] = 0; } } } }