一篇文章让你彻底了解Java算法「十大经典排序算法」

✍️作者简介:码农小北(专注于Android、Web、TCP/IP等技术方向)
🐳博客主页: 开源中国、稀土掘金、51cto博客、博客园、知乎、简书、慕课网、CSDN
🔔如果文章对您有一定的帮助请👉关注✨、点赞👍、收藏📂、评论💬。
🔥如需转载请参考【转载须知】

文章目录

  • 简介
    • 算法分类
    • 十四种算法简介
    • 算法复杂度
  • 算法演示
    • 冒泡排序 (Bubble Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 选择排序 (Selection Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 插入排序 (Insertion Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 希尔排序 (Shell Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 归并排序 (Merge Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 快速排序 (Quick Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 堆排序 (Heap Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 计数排序 (Counting Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 桶排序 (Bucket Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析
    • 基数排序 (Radix Sort)
      • 简介
      • 算法步骤
      • 图解算法
      • 代码示例
      • 算法分析

简介

排序算法是计算机科学中至关重要的一部分,它通过一系列操作将一组记录按照某个或某些关键字的大小进行递增或递减排列。在数据处理领域,排序算法的选择直接影响着程序的效率和性能。为了得到符合实际需求的优秀算法,我们需要经过深入的推理和分析,考虑到数据的各种限制和规范。因此,深入探讨十大经典排序算法的原理及实现。通过这个过程,我希望为大家提供更加准确和全面的排序算法知识,助力在实际编程中更灵活地选择适合场景的排序方法,提升程序的效率和性能。

排序算法根据其基本思想可以分为比较类排序和非比较类排序。比较类排序通过比较元素的大小来决定排序顺序,而非比较类排序则不依赖元素间的比较。不同排序算法在处理不同规模和类型的数据时表现出不同的优势。接下来,我们将详细介绍这十大经典排序算法。

算法分类

比较类排序

在比较类排序中,算法通过比较元素之间的大小关系来确定它们的相对次序。这类算法主要关注元素之间的比较操作,以决定它们在排序后的顺序。

非比较类排序

非比较类排序则不直接通过比较元素的大小关系来确定它们的顺序,而是利用其他方法完成排序。

区别和应用场景

  • 比较类排序更适用于元素之间有大小关系的情况,主要通过比较操作来实现排序,适用于各种数据类型。

  • 非比较类排序更适用于特定范围或结构的数据,利用其他方法实现排序,适用于整数、字符串等类型。
    在这里插入图片描述

十四种算法简介

序号简称英文简介
1二分查找法Binary Search二分查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
2冒泡排序算法Bubble Sort重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把它们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
3插入排序算法Insertion Sort通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入。
4快速排序算法Quick Sort对冒泡算法的一种改进。是指通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行,以此达到整个数据变成有序序列。
5希尔排序算法Shell’s Sort希尔排序是插入排序的一种又称“缩小增量排序”,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法
6归并排序算法Merge Sort归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
7桶排序算法Bucket Sort桶排序也叫箱排序,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是比较排序,他不受到 O(n log n) 下限的影响。
8基数排序算法Radix Sort基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog®m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
9剪枝算法Pruning Algorithms在搜索算法中优化中,剪枝,就是通过某种判断,避免一些不必要的遍历过程,形象的说,就是剪去了搜索树中的某些“枝条”,故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法,即确定哪些枝条应当舍弃,哪些枝条应当保留的方法。
10回溯算法Backtracking回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。
11最短路径算法Shortest Path从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法,Dijkstra 算法,Bellman-Ford 算法,Floyd 算法和 SPFA算法等。
12最大子数组算法Maximum Subarray最大子数组问题是要在一个数组中找到一个连续的子数组,使得该子数组的元素之和最大。该问题有多种解法,其中一种常见的解法是使用分治法。
13最长公共子序算法Longest Common Subsequence最长公共子序列是指在两个序列中均存在的、且相对顺序相同的元素组成的子序列。解决最长公共子序列的问题通常使用动态
14最小生成树算法Minimum Spanning Tree最小生成树是一个无向连通图中生成树中边权值之和最小的生成树。解决最小生成树的问题有多种算法,其中常见的包括 Prim 算法和 Kruskal 算法,它们通过选择图中的边来构建最小生成树。这些算法在网络设计、城市规划等领域有广泛应用。

算法复杂度

在实际应用中,不同排序算法的性能表现受到数据规模、数据分布等多方面因素的影响。我们将通过具体的示例和图表,展示这些排序算法在时间复杂度和空间复杂度上的对比,以便读者更好地选择适合自己场景的排序算法。

算法复杂度通常通过时间复杂度和空间复杂度来表示。以下是常见排序算法的时间复杂度和空间复杂度的表格:

排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性
冒泡排序 (Bubble Sort)O(n^2)O(n^2)O(n)O(1)稳定
选择排序 (Selection Sort)O(n^2)O(n^2)O(n^2)O(1)不稳定
插入排序 (Insertion Sort)O(n^2)O(n^2)O(n)O(1)稳定
希尔排序 (Shell Sort)O(n log^2 n)O(n log^2 n)O(n log n)O(1)不稳定
快速排序 (Quick Sort)O(n log n)O(n^2)O(n log n)O(log n)不稳定
归并排序 (Merge Sort)O(n log n)O(n log n)O(n log n)O(n)稳定
堆排序 (Heap Sort)O(n log n)O(n log n)O(n log n)O(1)不稳定
计数排序 (Counting Sort)O(n + k)O(n + k)O(n + k)O(k)稳定
桶排序 (Bucket Sort)O(n^2)O(n^2)O(n + k)O(n + k)稳定
基数排序 (Radix Sort)O(nk)O(nk)O(nk)O(n + k)稳定

注解:

  • 时间复杂度通常用大O表示法表示,表示算法运行时间相对于输入大小的增长率。
  • 空间复杂度表示算法在运行过程中相对于输入大小所需的额外空间。
  • "稳定"表示如果有两个相等的元素在排序前后的相对顺序保持不变。
  • "不稳定"表示相等的元素在排序前后的相对顺序可能改变。

以上表格中的复杂度是对于典型情况而言的。实际应用中,算法性能还可能受到具体实现、硬件条件等因素的影响。

算法演示

冒泡排序 (Bubble Sort)

简介

冒泡排序是一种简单直观的排序算法,它多次遍历待排序的序列,每次遍历都比较相邻的两个元素,如果顺序不正确就交换它们。通过多次遍历,使得最大的元素逐渐移动到最后,实现整个序列的排序。冒泡排序是一种简单但效率较低的排序算法,通常不适用于大规模数据集。

算法步骤

  1. 从序列的第一个元素开始,对相邻的两个元素进行比较。
  2. 如果顺序不正确,交换这两个元素的位置。
  3. 遍历完整个序列后,最大的元素会沉到序列的末尾。
  4. 重复步骤1-3,每次遍历都将未排序部分的最大元素沉到序列的末尾。
  5. 重复以上步骤,直到整个序列有序。

图解算法

在这里插入图片描述

代码示例

    /*** 冒泡排序** @param arr 待排序数组*/public static void bubbleSort(int[] arr) {int n = arr.length;// 外层循环控制比较的轮数for (int i = 0; i < n - 1; i++) {// 内层循环控制每一轮比较的次数for (int j = 0; j < n - i - 1; j++) {// 如果当前元素大于下一个元素,则交换它们的位置if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}

算法分析

  • 稳定性: 冒泡排序是一种稳定的排序算法,相等元素的相对位置在排序前后不会改变。
  • 时间复杂度: 最佳:O(n), 最差:O(n^2), 平均:O(n^2)
  • 空间复杂度: O(1)
  • 排序方式: 冒泡排序是一种原地排序算法。

选择排序 (Selection Sort)

简介

选择排序是一种简单直观的排序算法,它将待排序的序列分为已排序部分和未排序部分,每次从未排序部分选择最小(或最大)的元素,放到已排序部分的末尾。通过多次选择最小(或最大)元素,完成整个序列的排序。虽然选择排序不如一些高级排序算法的性能优越,但由于其简单性,在某些场景下仍然是一个有效的选择。

算法步骤

  1. 从未排序部分选择最小(或最大)的元素。
  2. 将选中的元素与未排序部分的第一个元素交换位置,使其成为已排序部分的末尾。
  3. 更新分界线,将已排序部分扩大一个元素,未排序部分缩小一个元素。
  4. 重复步骤1-3,直到未排序部分为空。
  5. 完成排序。

图解算法

在这里插入图片描述

代码示例

/*** 选择排序** @param arr 待排序数组*/public static void selectionSort(int[] arr) {int n = arr.length;// 外层循环控制当前需要放置的位置for (int i = 0; i < n - 1; i++) {// 假设当前位置的元素是最小的int minIndex = i;// 内层循环找到未排序部分的最小元素的索引for (int j = i + 1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}// 将找到的最小元素与当前位置元素交换int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}}

算法分析

  • 稳定性: 选择排序是一种不稳定的排序算法,因为相等元素可能在排序过程中改变相对位置。
  • 时间复杂度: 最佳:O(n^2), 最差:O(n^2), 平均:O(n^2)
  • 空间复杂度: O(1)
  • 排序方式: 选择排序是一种原地排序算法。

插入排序 (Insertion Sort)

简介

插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应的位置并插入。插入排序是稳定的排序算法,适用于小型数据集。

算法步骤

  1. 从第一个元素开始,该元素可以认为已经被排序。
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描。
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置。
  4. 重复步骤3,直到找到已排序的元素小于或等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5,直到整个数组排序完成。

图解算法

在这里插入图片描述

代码示例

public class InsertionSort {public static void main(String[] args) {int[] array = {12, 11, 13, 5, 6};System.out.println("原始数组:");printArray(array);// 应用插入排序insertionSort(array);System.out.println("\n排序后的数组:");printArray(array);}/*** 插入排序** @param arr 待排序数组*/public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; ++i) {int key = arr[i];int j = i - 1;// 将大于 key 的元素都向后移动while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j = j - 1;}// 插入 key 到正确的位置arr[j + 1] = key;}}/*** 打印数组元素** @param arr 待打印数组*/public static void printArray(int[] arr) {for (int value : arr) {System.out.print(value + " ");}System.out.println();}
}

算法分析

  • 稳定性: 稳定
  • 时间复杂度: 最佳:O(n),最差:O(n2),平均:O(n2)
  • 空间复杂度: O(1)

希尔排序 (Shell Sort)

简介

希尔排序是一种插入排序的改进版本,它通过比较一定间隔(增量)内的元素,并逐步减小这个间隔,最终完成整个序列的排序。希尔排序的核心思想是将相隔较远的元素进行比较和交换,以得到局部较为有序的序列,最后再进行插入排序。希尔排序在大规模数据集上比插入排序更加高效。

算法步骤

  1. 选择一个增量序列(一般是按照 Knuth 提出的序列:1, 4, 13, 40, …)。
  2. 根据增量序列,将序列分割成若干子序列,对每个子序列进行插入排序。
  3. 逐步减小增量,重复步骤2,直到增量为1,此时进行最后一次插入排序。
  4. 完成排序。

图解算法

在这里插入图片描述

代码示例

/*** 希尔排序** @param arr 待排序数组*/public static void shellSort(int[] arr) {int n = arr.length;// 初始步长设置为数组长度的一半for (int gap = n / 2; gap > 0; gap /= 2) {// 从步长位置开始进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i];int j;// 在当前步长范围内,进行插入排序for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap];}arr[j] = temp;}}}

算法分析

  • 稳定性: 希尔排序是一种不稳定的排序算法,相等元素可能在排序过程中改变相对位置。
  • 时间复杂度: 最佳:O(n log n), 最差:O(n^2), 平均:取决于增量序列的选择
  • 空间复杂度: O(1)
  • 排序方式: 希尔排序是一种原地排序算法。

归并排序 (Merge Sort)

简介

归并排序是一种基于分治思想的排序算法,它将待排序的序列分成两个子序列,对每个子序列进行递归排序,然后将已排序的子序列合并成一个有序序列。归并排序的关键在于合并操作,它保证了每个子序列在合并时都是有序的。归并排序具有稳定性和高效性,在大规模数据集上表现出色。

算法步骤

  1. 将待排序序列分成两个子序列,分别进行递归排序。
  2. 合并已排序的子序列,得到新的有序序列。
  3. 重复步骤1-2,直到整个序列有序。

图解算法

在这里插入图片描述

代码示例

/*** 归并排序** @param arr   待排序数组* @param left  左边界索引* @param right 右边界索引*/public static void mergeSort(int[] arr, int left, int right) {if (left < right) {// 找到中间索引int mid = left + (right - left) / 2;// 对左半部分进行归并排序mergeSort(arr, left, mid);// 对右半部分进行归并排序mergeSort(arr, mid + 1, right);// 合并左右两部分merge(arr, left, mid, right);}}/*** 合并两个有序数组** @param arr   待合并数组* @param left  左边界索引* @param mid   中间索引* @param right 右边界索引*/public static void merge(int[] arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int[] leftArray = new int[n1];int[] rightArray = new int[n2];// 将数据复制到临时数组System.arraycopy(arr, left, leftArray, 0, n1);System.arraycopy(arr, mid + 1, rightArray, 0, n2);// 合并临时数组int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArray[i] <= rightArray[j]) {arr[k++] = leftArray[i++];} else {arr[k++] = rightArray[j++];}}// 将左半部分剩余元素复制到原数组while (i < n1) {arr[k++] = leftArray[i++];}// 将右半部分剩余元素复制到原数组while (j < n2) {arr[k++] = rightArray[j++];}}

算法分析

  • 稳定性: 归并排序是一种稳定的排序算法,相等元素的相对位置在排序前后不会改变。
  • 时间复杂度: 最佳:O(n log n), 最差:O(n log n), 平均:O(n log n)
  • 空间复杂度: O(n)
  • 排序方式: 归并排序是一种非原地排序算法。

快速排序 (Quick Sort)

简介

快速排序是一种基于分治思想的排序算法,它选择一个元素作为基准值,将序列分为两个子序列,小于基准值的元素放在基准值的左边,大于基准值的元素放在右边。然后对左右子序列分别进行递归排序。快速排序是一种高效的排序算法,在大规模数据集上表现出色。

算法步骤

  1. 选择一个基准值。
  2. 将序列分为两个子序列,小于基准值的元素放在左边,大于基准值的元素放在右边。
  3. 对左右子序列分别进行递归排序。
  4. 完成排序。

图解算法

在这里插入图片描述

代码示例

/*** 快速排序* @param arr 待排序数组* @param low 左边界* @param high 右边界*/
public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 划分数组,获取基准值的位置int pivotIndex = partition(arr, low, high);// 对左子数组进行递归排序quickSort(arr, low, pivotIndex - 1);// 对右子数组进行递归排序quickSort(arr, pivotIndex + 1, high);}
}/*** 划分数组,获取基准值的位置* @param arr 待排序数组* @param low 左边界* @param high 右边界* @return 基准值的位置*/
public static int partition(int[] arr, int low, int high) {// 选择最右边的元素作为基准值int pivot = arr[high];// i 表示小于基准值的元素的最右位置int i = low - 1;// 从左到右遍历数组for (int j = low; j < high; j++) {// 如果当前元素小于基准值,交换位置if (arr[j] < pivot) {i++;swap(arr, i, j);}}// 将基准值放在正确的位置swap(arr, i + 1, high);// 返回基准值的位置return i + 1;
}/*** 交换数组中两个元素的位置* @param arr 待排序数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/
public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

算法分析

  • 稳定性: 快速排序是一种不稳定的排序算法,相等元素可能在排序过程中改变相对位置。
  • 时间复杂度: 最佳:O(n log n), 最差:O(n^2), 平均:O(n log n)
  • 空间复杂度: 最佳:O(log n), 最差:O(n)
  • 排序方式: 快速排序是一种原地排序算法。

堆排序 (Heap Sort)

简介

堆排序是一种基于二叉堆数据结构的排序算法。它将待排序的序列构建成一个二叉堆,然后反复将堆顶元素与堆尾元素交换,将最大(或最小)元素放在已排序部分的末尾。通过反复调整堆,直到整个序列有序。堆排序具有高效的性能,并且是一种原地排序算法。

算法步骤

  1. 构建一个最大堆(对于升序排序)或最小堆(对于降序排序)。
  2. 将堆顶元素与堆尾元素交换,将最大(或最小)元素放在已排序部分的末尾。
  3. 调整堆,使得剩余元素仍然构成一个最大堆(或最小堆)。
  4. 重复步骤2-3,直到整个序列有序。

图解算法

在这里插入图片描述

代码示例

 /*** 堆排序** @param arr 待排序数组*/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--) {// 将堆顶元素与当前未排序部分的最后一个元素交换swap(arr, 0, i);// 调整堆,重新构建最大堆heapify(arr, i, 0);}}/*** 调整堆,使其成为最大堆** @param arr 待调整数组* @param n   堆的大小* @param i   当前节点索引*/public 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) {swap(arr, i, largest);heapify(arr, n, largest);}}/*** 交换数组中两个元素的位置** @param arr 待交换数组* @param i   第一个元素的索引* @param j   第二个元素的索引*/public static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

算法分析

  • 稳定性: 堆排序是一种不稳定的排序算法,相等元素可能在排序过程中改变相对位置。
  • 时间复杂度: 最佳:O(n log n), 最差:O(n log n), 平均:O(n log n)
  • 空间复杂度: O(1)
  • 排序方式: 堆排序是一种原地排序算法。

计数排序 (Counting Sort)

简介

计数排序是一种非比较性的排序算法,适用于具有一定范围的整数元素。它通过统计每个元素的出现次数,然后根据统计信息将元素排列成有序序列。计数排序的核心思想是将每个元素的出现次数记录在额外的数组中,然后根据统计信息构建有序序列。

算法步骤

  1. 统计每个元素的出现次数,得到计数数组。
  2. 根据计数数组,构建有序序列。

图解算法

在这里插入图片描述

代码示例

 /*** 计数排序** @param arr 待排序数组*/public static void countingSort(int[] arr) {int n = arr.length;// 找到数组中的最大值,确定计数数组的大小int max = arr[0];for (int value : arr) {if (value > max) {max = value;}}// 创建计数数组,并初始化为0int[] count = new int[max + 1];for (int i = 0; i <= max; i++) {count[i] = 0;}// 统计每个元素的出现次数for (int value : arr) {count[value]++;}// 根据计数数组,重构原数组int index = 0;for (int i = 0; i <= max; i++) {while (count[i] > 0) {arr[index++] = i;count[i]--;}}}

算法分析

  • 稳定性: 计数排序是一种稳定的排序算法,相等元素的相对位置在排序前后不会改变。
  • 时间复杂度: 最佳:O(n + k), 最差:O(n + k), 平均:O(n + k)
  • 空间复杂度: O(k),其中 k 为计数数组的大小。
  • 排序方式: 计数排序是一种非原地排序算法。

桶排序 (Bucket Sort)

简介

桶排序是一种非比较性的排序算法,它将待排序元素分散到不同的桶中,然后分别对每个桶中的元素进行排序,最后将各个桶中的元素合并得到有序序列。桶排序适用于元素分布均匀的情况,可以有效提高排序的速度。

算法步骤

  1. 将待排序元素分散到不同的桶中。
  2. 对每个桶中的元素进行排序(可以使用其他排序算法或递归桶排序)。
  3. 将各个桶中的元素合并得到有序序列。

图解算法

在这里插入图片描述

代码示例

/*** 桶排序** @param arr 待排序数组*/public static void bucketSort(double[] arr) {int n = arr.length;// 创建桶ArrayList<Double>[] buckets = new ArrayList[n];for (int i = 0; i < n; i++) {buckets[i] = new ArrayList<>();}// 将元素分配到对应的桶中for (double value : arr) {int bucketIndex = (int) (value * n);buckets[bucketIndex].add(value);}// 对每个桶内的元素进行排序for (ArrayList<Double> bucket : buckets) {Collections.sort(bucket);}// 将桶中的元素合并到原数组int index = 0;for (ArrayList<Double> bucket : buckets) {for (double value : bucket) {arr[index++] = value;}}}

算法分析

  • 稳定性: 桶排序是一种稳定的排序算法,相等元素的相对位置在排序前后不会改变。
  • 时间复杂度: 最佳:O(n + k), 最差:O(n^2), 平均:O(n + n^2/k + k),其中 k 为桶的数量。
  • 空间复杂度: O(n + k),其中 n 为待排序元素的数量,k 为桶的数量。
  • 排序方式: 桶排序是一种非原地排序算法。

基数排序 (Radix Sort)

简介

基数排序是一种非比较性的排序算法,它根据元素的位数进行排序。基数排序的核心思想是将待排序元素按照低位到高位的顺序依次进行排序,每次排序使用稳定的排序算法。基数排序适用于元素的位数相同的情况,例如整数或字符串。

算法步骤

  1. 将待排序元素按照最低位开始,依次排序。
  2. 重复步骤1,直到排序到最高位。
  3. 合并得到有序序列。

图解算法

在这里插入图片描述

代码示例

import java.util.ArrayList;/*** 基数排序* @param arr 待排序数组* @return 排序后的数组*/
public static int[] radixSort(int[] arr) {// 找到数组中的最大值,确定位数int max = getMax(arr);// 进行位数的排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}return arr;
}/*** 获取数组中的最大值* @param arr 待排序数组* @return 数组中的最大值*/
private static int getMax(int[] arr) {int max = arr[0];for (int num : arr) {if (num > max) {max = num;}}return max;
}/*** 根据位数进行计数排序* @param arr 待排序数组* @param exp 当前位数,例如个位、十位、百位...*/
private static void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];int[] count = new int[10];// 统计每个数字的出现次数for (int i = 0; i < n; i++) {count[(arr[i] / exp) % 10]++;}// 计算累加次数for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 构建输出数组for (int i = n - 1; i >= 0; i--) {output[count[(arr[i] / exp) % 10] - 1] = arr[i];count[(arr[i] / exp) % 10]--;}// 将输出数组拷贝回原数组System.arraycopy(output, 0, arr, 0, n);
}

算法分析

  • 稳定性: 基数排序是一种稳定的排序算法,相等元素的相对位置在排序前后不会改变。
  • 时间复杂度: 最佳:O(d * (n + k)), 最差:O(d * (n + k)), 平均:O(d * (n + k)),其中 d 为元素的位数,k 为基数。
  • 空间复杂度: O(n + k),其中 n 为待排序元素的数量,k 为基数。
  • 排序方式: 基数排序是一种非原地排序算法。

♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠ ⊕ ♠

分享不易,原创不易!如果以上链接对您有用,可以请作者喝杯水!您的支持是我持续分享的动力,感谢!!!

在这里插入图片描述
无论是哪个阶段,坚持努力都是成功的关键。不要停下脚步,继续前行,即使前路崎岖,也请保持乐观和勇气。相信自己的能力,你所追求的目标定会在不久的将来实现。加油!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/199759.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

5款免费BI数据可视化工具,2023年最新精选推荐!

BI可视化工具顾名思义是进行数据分析和可视化的软件&#xff0c;旨在将数据以表格、图表、仪表盘等形式展示出来&#xff0c;让用户能够更加直观了解其业务状况、发现问题&#xff0c;并在必要时进行决策。   市面上BI数据可视化工具很多&#xff0c;目前比较火的像国外的Tabl…

文本转语音

免费工具 音视频转译 通义听悟 | https://tingwu.aliyun.com/u/wg57n33kml5nkr3p 音色迁移 speechify | https://speechify.com/voice-cloning/ 视频生成 lalamu | http://lalamu.studio/demo/ 画质增强 topazlabs video AI | https://www.topazlabs.com 付费工具 rask | htt…

亚马逊出口电热毯日本PSE认证需要什么资料解析

电热毯出口日本需要办理PSE认证&#xff0c;电热毯&#xff0c;又名电褥&#xff0c;是一种接触式电暖器具。 PSE认证介绍是日本强制性认证&#xff0c;包含安全及EMI&#xff0c;用以证明电子电气等产品符合日期电气用品安全法或国际IEC标准的要求。日本电气用品安全法规定&am…

做外贸要学会分析客户情况

最近在某产品的专业群里询问一款产品&#xff0c;看谁可以做&#xff0c;然后很快就有一个自称是工厂的人加上了我。因为自己本身并不懂这个产品&#xff0c;很多他们发的问题自己都答不上来。我就如实告诉他自己是个新手&#xff0c;可以把你们现在能做的&#xff0c;或者已经…

openfeign整合sentinel出现异常

版本兼容的解决办法&#xff1a;在为userClient注入feign的接口类型时&#xff0c;添加Lazy注解。 Lazy注解是Spring Framework中的一个注解&#xff0c;它通常用于标记Bean的延迟初始化。当一个Bean被标记为Lazy时&#xff0c;Spring容器在启动时不会立即初始化这个Bean&…

什么是多域名证书?

多域名证书是指同一个证书中包含多个域名&#xff0c;能够在多个站点之间共享一份证书&#xff0c;实现一个站点对应多个域名的情况。多域名证书非常适合需要跨多个站点部署的应用&#xff0c;例如企业的子站点、博客等。 特点 多域名证书的优点包括以下几个方面&#xff1a;…

如何通过cpolar内网穿透工具实现远程访问本地postgreSQL

文章目录 前言1. 安装postgreSQL2. 本地连接postgreSQL3. Windows 安装 cpolar4. 配置postgreSQL公网地址5. 公网postgreSQL访问6. 固定连接公网地址7. postgreSQL固定地址连接测试 前言 PostgreSQL是一个功能非常强大的关系型数据库管理系统&#xff08;RDBMS&#xff09;,下…

十二、Docker的简介

目录 一、介绍 Docker 主要由以下三个部分组成&#xff1a; Docker 有许多优点&#xff0c;包括&#xff1a; 二、Docker和虚拟机的差异 三、镜像和容器 四、Docker Hub 五、Docker架构 六、总结 一、介绍 Docker 是一种开源的应用容器平台&#xff0c;可以在容器内部…

Java编程技巧:将图片导出成pdf文件

目录 一、pom依赖二、代码三、测试链接四、结果展示 一、pom依赖 <!-- pdf插件 start --> <dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId><version>5.5.3</version> </dependency> &l…

SpringDoc基础配置和集成OAuth2登录认证教程

本期内容 学会通过注解和Java代码的方式添加SpringDoc配置。在swagger-ui提供的页面上提供OAuth2登录认证&#xff0c;在集成Security的情况下便捷获取access_token并在请求时按照OAuth2规范携带。 为什么集成OAuth2登录认证&#xff1f; 现在大部分教程是在swagger-ui页面添…

Linux操作系统使用及C高级编程-D6-D8Linux shell脚本

利用shell命令写的脚本文件&#xff0c;后缀是.sh shell脚本是一个解释型语言&#xff0c;不需要编译&#xff0c;可直接执行 书写&#xff1a;vi test.sh #!/bin/bash&#xff1a;说明使用的是/bin目录下的bash 说明完后即可编写脚本文件 bash test.sh&#xff1a;运行文…

LDAP概念和原理介绍

相信对于许多的朋友来说&#xff0c;可能听说过LDAP&#xff0c;但是实际中对LDAP的了解和具体的原理可能还比较模糊&#xff0c;今天就从“什么是LDAP”、“LDAP的主要产品”、“LDAP的基本模型”、“LDAP的使用案例”四个方面来做一个介绍。 我们在开始介绍之前先来看几个问…

卷积神经网络(CNN)天气识别

文章目录 前期工作1. 设置GPU&#xff08;如果使用的是CPU可以忽略这步&#xff09;我的环境&#xff1a; 2. 导入数据3. 查看数据 二、数据预处理1. 加载数据2. 可视化数据3. 再次检查数据4. 配置数据集 三、构建CNN网络四、编译五、训练模型六、模型评估 前期工作 1. 设置GP…

【深度学习实验】网络优化与正则化(七):超参数优化方法——网格搜索、随机搜索、贝叶斯优化、动态资源分配、神经架构搜索

文章目录 一、实验介绍二、实验环境1. 配置虚拟环境2. 库版本介绍 三、优化算法0. 导入必要的库1. 随机梯度下降SGD算法a. PyTorch中的SGD优化器b. 使用SGD优化器的前馈神经网络 2.随机梯度下降的改进方法a. 学习率调整b. 梯度估计修正 3. 梯度估计修正&#xff1a;动量法Momen…

【JavaEE初阶】 CSS相关属性,元素显示模式,盒模型,弹性布局,Chrome 调试工具||相关讲解

文章目录 &#x1f38b;字体属性&#x1f6a9;设置字体&#x1f6a9;字体大小&#x1f6a9;字体粗细&#x1f6a9;文字样式 &#x1f38d;文本属性&#x1f6a9;文本颜色&#x1f388;认识 RGB&#x1f388;设置文本颜色 &#x1f6a9;文本对齐&#x1f6a9;文本装饰&#x1f6…

销售团队可以借助CRM系统做什么?

销售主管都想有一支效率高、质量高的销售团队&#xff0c;无论对于初创企业还是大型企业销售团队都是企业盈利的主力部门&#xff0c;直接为企业带了业绩。如何提升销售团队水平&#xff1f;离不开CRM系统的辅助&#xff0c;CRM软件能为销售团队提供哪些支持&#xff1f;下面我…

MISRA 2012学习笔记(5)-Rules 8.10

文章目录 Rules8.10 基本类型模型(The essential type model)8.10.1 原理8.10.2 基本类型(Essential type)Rule 10.1 操作数不得具有不适当的基本类型Rule 10.2 在加减法运算中&#xff0c;不得不当使用本质为字符类型的表达式Rule 10.3 表达式的值不得赋值给具有较窄基本类型或…

系列一、介绍

一、概述 官网&#xff1a; ThreadLocal用于提供线程内的局部变量&#xff0c;不同线程之间不会互相干扰&#xff0c;这种变量在线程的生命周期内起作用&#xff0c;减少同一个线程内多个函数或者组件之间一些公共变量传递的复杂度。 大白话&#xff1a; 线程并发&#xff1a;T…

编程怎么学习视频教程,编程实例入门教程,中文编程开发语言工具下载

编程怎么学习视频教程&#xff0c;编程实例入门教程&#xff0c;中文编程开发语言工具下载。 给大家分享一款中文编程工具&#xff0c;零基础轻松学编程&#xff0c;不需英语基础&#xff0c;编程工具可下载。 这款工具不但可以连接部分硬件&#xff0c;而且可以开发大型的软件…

Linux本地docker一键部署traefik+内网穿透工具实现远程访问Web UI管理界面

文章目录 前言1. Docker 部署 Trfɪk2. 本地访问traefik测试3. Linux 安装cpolar4. 配置Traefik公网访问地址5. 公网远程访问Traefik6. 固定Traefik公网地址 前言 Trfɪk 是一个云原生的新型的 HTTP 反向代理、负载均衡软件&#xff0c;能轻易的部署微服务。它支持多种后端 (D…