网站升级改版,html网页设计作品下载,网页制作软件html,网站建设教程 迅雷下载文章目录 十大排序算法⛅前言#x1f331;1、排序概述#x1f334;2、排序的实现#x1f335;2.1 插入排序#x1f433;2.1.1 直接插入排序算法介绍算法实现 #x1f433;2.1.2 希尔排序算法介绍算法实现 #x1f335;2.2 选择排序#x1f433;2.2.1 选择排序算法介绍算… 文章目录 十大排序算法⛅前言1、排序概述2、排序的实现2.1 插入排序2.1.1 直接插入排序算法介绍算法实现 2.1.2 希尔排序算法介绍算法实现 2.2 选择排序2.2.1 选择排序算法介绍算法实现 2.2.2 堆排序算法介绍算法实现 2.3 交换排序2.3.1 冒泡排序算法介绍算法实现 2.3.2 快速排序算法介绍算法实现 2.4 归并排序算法介绍算法实现 2.5 非比较排序2.5.1 计数排序算法介绍算法实现 .5.2 桶排序算法介绍算法实现 2.5.3 基数排序算法介绍算法实现 总结 十大排序算法
⛅前言 大家好我是知识汲取者今天要给大家带来一篇有关排序的文章相信大家一定在工作中或生活中接触过不少有关排序的问题吧比如生活中我们在课间做体操时的排队根据身高排序、考试的排名根据分数排序、报道后老师点名根据序号排序……工作中我们需要对某个表按照id进行排序、或者按照姓名的首字母进行排序这些都是很常见的当然这些都是可以直接手动调用一个函数就能一键完成并不需要我们去具体实现但是大家难道就不好奇为什么我点一下就能直接实现这个排序功能呢它是怎么实现的呢假如让我来制定一个排序规则我又该如何去实现它呢如果您有这样或那样的疑惑的话我相信您一定能有所收获的 本文适合人群想系统了解十大基础排序算法、还没有接触或对与排序算法不熟练的读者。本文将详细介绍十大经典排序算法①直接插入排序、②希尔排序、③直接选择排序、④堆排序、⑤冒泡排序、⑥快速排序、⑦归并排序、⑧计数排序、⑨桶排序、⑩基数排序。通过本文您不仅能学到十大排序的思想、具体实现同时还能了解它们各自的特点比如应用场景、排序算法的事件复杂度等。让我们一起冲冲冲(●ˇ∀ˇ●)备注本文所有代码实现均以升序为例 PS文中部分图片摘自菜鸟教程如有侵权还请及时告知笔者将立即删除 相关推荐 知识汲取者的主页欢迎参观希望能对你有所帮助算法与数据结构专栏包含博主所有对算法的学习笔记算法和数据结构导学很适合算法初学者算法题解专栏包含博主部分算法题解算法刷题站点LeetCode | 牛客代码仓库Gitee | Github 1、排序概述 什么是排序 排序是计算机内经常进行的一种操作其目的是将一组“无序”的记录序列按照某种规则调整为“有序”的记录序列 排序的目的是什么? 方便查找数据有利于观察数据的规律性 …… 什么是排序算法 所谓排序算法就是能够解决排序问题的算法而算法Algorithm是指解题方案的准确而完整的描述是一系列解决问题的清晰指令算法代表着用系统的方法描述解决问题的策略机制 什么是排序算法的稳定性 排序算法的稳定性是指一组数据经过排序后具有相同值的两个数在排序后仍然保持相同的次序。 比如在 [ a , b , c , d , e , f ] [a,b,c,d,e,f] [a,b,c,d,e,f] 这组数中 c c c和 e e e具有相同的值此时 c c c在 e e e的前面经过排序后变为 [ a , b , e , d , c , f ] [a,b,e,d,c,f] [a,b,e,d,c,f] 此时 c c c在 e e e的后面它们的次序发生了改变则称该排序算法具有不稳定性同理如果排序后变为 [ a , b , c , e , d , f ] [a,b,c,e,d,f] [a,b,c,e,d,f] 此时此时 c c c仍然在 e e e的前面则称该排序算法具有稳定性。 排序算法的分类 备注 内部排序被排序的数据都是存储在内存1中且排序过程也是发生在内存中的 适用于规模不是很大的数据 外部排序排需的数据一部分存储在内存中一部分存储在外存2中排序过程需要涉及内存外数据的交换 适用于规模很大、不能一次性装入内存中的数据 比较排序比较排序算法是通过比较元素之间的大小关系来确定它们的顺序。 非比较排序非比较排序算法是一类不基于元素之间比较的排序算法。
2、排序的实现 对于排序的实现这里我统一都采用对数组进行一个增序排序从小到大进行排序也就是数组的元素随着索引的递增而递增而对于排序的目标数组直接采用 arr[10][5, 3, 9, 1, 7, 2, 8, 4, 6, 0] public static void main(String[] args) {// 准备待排序的数组int[] arr {5, 3, 9, 1, 7, 2, 8, 4, 6, 0};// 进行排序// 输出排序后的数组System.out.println(Arrays.toString(arr));}2.1 插入排序 每次将一个待排序的记录按其大小插入已经排好序的子列表的适当位置直到记录插入完成也就说明排序已完成 插入排序的特点 稳定性插入排序是一种稳定的排序算法即相等元素的相对顺序在排序前后保持不变。原地排序插入排序是一种原地排序算法不需要额外的辅助空间只需使用少量的额外空间进行元素交换。时间复杂度在平均情况和最坏情况下插入排序的时间复杂度为O(n^2)其中n是待排序序列的长度。在最好情况下序列已经部分有序插入排序的时间复杂度可以达到O(n)。对小规模数据效果好相比其他复杂度更高的排序算法插入排序在处理小规模数据时的效果较好。当待排序序列的规模较小时插入排序的性能优于其他排序算法。
2.1.1 直接插入排序
算法介绍 直接插入排序Straight Insertion Sort是一种简单且常用的排序算法。它的基本思想是将待排序的元素依次插入已经排好序的部分使得插入后仍然保持有序。 实现步骤 Step1遍历待排序数组。从第二个元素开始依次将每个元素插入已排序序列中。Step2比较与插入操作。将当前待插入元素与已排序序列中的元素逐个比较并移动位置直至找到合适的插入位置或遍历完已排序序列。Step3插入元素。将待插入元素插入到合适的位置使得插入后的子序列仍然有序。Step4重复上述步骤。继续对下一个未排序元素进行插入操作直至所有元素都被插入到已排序序列中。 示意图
算法实现 /*** 直接插入排序* param arr 待排序的数组*/private static void directInsertionSort(int[] arr) {// 从第2个元素开始遍历for (int i 1; i arr.length; i) {// 待插入的元素int key arr[i];int j i - 1;// 将当前元素与前面已经排序好的元素进行比较直到没有发现比自己大的元素while (j 0 arr[j] key) {// 当发现后一个元素比前一个元素小时用前一个元素覆盖后一个元素的值arr[j 1] arr[j];j--;}// 将待插入的元素放到对应的位置arr[j 1] key;}}备注如果想要降序排序只需要修改为while (j 0 arr[j] key) 即可
2.1.2 希尔排序
算法介绍 希尔排序Shell Sort也称缩小增量排序是对直接插入排序的改进版本它通过引入步长的概念先将待排序序列分割成若干个子序列对每个子序列进行直接插入排序然后逐步缩小步长进行排序最终使整个序列有序。 实现步骤 Step1确定步长序列。选择一个步长序列一般可以使用希尔原始提出的序列n/2, n/4, …, 1也可以根据实际情况选择其他步长序列。Step2根据步长分组。根据选定的步长将待排序序列分成若干个子序列。Step3对各个子序列进行直接插入排序。对每个子序列应用直接插入排序算法将子序列转化为部分有序序列。Step4不断缩小步长并重复上述步骤。重复步骤2和步骤3逐步减小步长直至步长为1完成最后一次排序。 示意图
算法实现 /*** 希尔排序* param arr 待排序的数组*/private static void shellSort(int[] arr) {int n arr.length;// 确定步长序列int gap n / 2;while (gap 0) {for (int i gap; i n; i) {int temp arr[i];int j i;// 对每个子序列应用直接插入排序算法while (j gap arr[j - gap] temp) {arr[j] arr[j - gap];j - gap;}arr[j] temp;}// 缩小步长gap / 2;}}备注如果想要降序排序只需要修改为while (j gap arr[j - gap] temp) 即可
2.2 选择排序 每一趟从待排序的记录中选出最大或最小的记录让后按顺序放在已排序的子列表的最后直到所有记录排完 选择排序的特点 不稳定性选择排序是一种不稳定的排序算法即相等元素的相对顺序可能在排序过程中发生改变。原地排序选择排序是一种原地排序算法不需要额外的辅助空间只需使用少量的额外空间进行元素交换。时间复杂度选择排序的时间复杂度始终为O(n^2)其中n是待排序序列的长度。无论序列是否有序每次都需要遍历剩余未排序部分来找到最小或最大元素。大规模数据效果差由于选择排序每次都要从剩余未排序部分中选取最小或最大元素并将其放入已排序部分的末尾因此在处理大规模乱序数据时效率较低。
2.2.1 选择排序
算法介绍 选择排序Selection Sort是一种简单直观的排序算法它的基本思想是每次从未排序的部分中选取最小或最大的元素放置在已排序部分的末尾逐步构建有序序列。选择排序的时间复杂度为O(n^2)不稳定但是由于其操作简单对于小规模数据或部分有序的数据仍然具有一定的实用价值。 实现步骤 Step1遍历数组。从数组的第一个元素开始依次向后遍历所有元素。Step2寻找最小值。在当前遍历到的元素及其后面的元素中找到最小的元素。Step3交换位置。将最小值与当前遍历到的元素进行交换位置即将最小值放到当前遍历的位置上。Step4重复上述步骤。重复步骤2和步骤3直到遍历完整个数组 每次遍历都寻找出剩余元素中的最小值将最小值放到前面思路很简单 示意图
算法实现 /*** 选择排序* * param arr 待排序的数组*/private static void selectSort(int[] arr) {int n arr.length;// 遍历数组for (int i 0; i n - 1; i) {// 从前往后遍历寻找最小值的索引int minIdx i;for (int j i 1; j n; j) {if (arr[j] arr[minIdx]) {minIdx j;}}// 将最小值与当前元素交换位置swap(arr, i, minIdx);}}/*** 交换 arr 数组中索引为 i 和索引为 j 处的元素*/private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}备注如果想要降序排序只需要修改为if (arr[j] arr[minIdx]) 即可
2.2.2 堆排序
算法介绍 堆排序Heap Sort是一种基于二叉堆Binary Heap的排序算法。它通过构建最大堆Max Heap或最小堆Min Heap来进行排序。 如果你对堆这个数据结构不太了解到话这个排序可能一下很难看懂关于堆的详解可以参考这篇文章【数据结构篇】堆把堆搞懂了再来看这个堆排序可能会变得很简单 实现步骤 Step1构建最大堆。将待排序的序列构建成一个最大堆。Step2将堆顶元素与末尾元素交换。将堆顶元素最大值与末尾元素交换并将交换后的末尾元素排除在堆之外。Step3重新调整堆顶元素位置。通过下沉操作使交换后的新堆顶元素重新满足最大堆的性质。Step4重复步骤2和步骤3直到堆中只剩下一个元素为止。 示意图 初始状态[5, 3, 9, 1, 7, 2, 8, 4, 6, 11] 构建最大堆 定位最后一个非叶子节点计算公式n/2-1以最后一个非叶子节点为出发点从后往前遍历不断递归的下浮元素确保父节点永远是比子节点大的最终就可以得到一个最大堆 下方是构建最大堆的示意图红色部分是当前正在进行下浮的父节点 最核心的步骤就是构建最大堆最大堆已经实现了现在只需要按照下面的步骤即可得到一个升序数组 循环从 n-1 到 1每次循环表示将当前未排序的部分中最大的元素放到已排序的部分的末尾。在每一次循环中i就会减一也就是堆的最大索引会减一防止末尾节点参与下浮比较然后调用 swap 函数将堆的根节点与未排序部分的最后一个元素交换位置。经过交换后堆的根节点变成了当前未排序部分中的最大值。然后调用 heapifyDown 函数对剩余的元素进行堆调整。heapifyDown 函数会将交换后的根节点不断下沉直到满足堆的性质。经过循环操作每次将最大值放到已排序部分的末尾直到所有元素都被放置到已排序部分即完成了排序。 这里我就不画图了思路在这里大家可以自行画一个草图
算法实现 /*** 堆排序** param arr 待排序的数组*/public static void heapSort(int[] arr) {int n arr.length;// 构建最大堆从最后一个非叶子节点开始for (int i n / 2 - 1; i 0; i--) {heapifyDown(arr, n, i);}System.out.println(Arrays.toString(arr));// 排序从后往前遍历不断将极大值放到堆的末尾for (int i n - 1; i 0; i--) {// 将根节点与最后一个元素交换位置swap(arr, 0, i);// 对剩余的元素进行堆调整heapifyDown(arr, i, 0);}}/*** 下浮** param arr* param n 数组中的元素arr.length* param i 要下浮元素的索引*/private static void heapifyDown(int[] arr, int n, int i) {// 父节点索引int parent i;// 左节点索引int left 2 * i 1;// 右节点索引int right 2 * i 2;// 如果左子节点存在且大于父节点则更新最大值if (left n arr[left] arr[parent]) {parent left;}// 如果右子节点存在且大于父节点或左子节点则更新最大值if (right n arr[right] arr[parent]) {parent right;}// 如果最大值不是父节点则交换位置并递归调整子树if (parent ! i) {swap(arr, i, parent);heapifyDown(arr, n, parent);}}/*** 交换 arr 数组中索引为 i 和索引为 j 处的元素*/private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}备注如果想要降序排序需要改用最小堆只需要修改if (right n arr[right] arr[parent])和if (right n arr[right] arr[parent])两处即可
几个注意点
对于完全二叉树的最后一个非叶子节点我们需要通过n/2-1进行计算得到这个的由来也很简单画一个草图就能理解了关于数学证明推导可以参考文末的文章链接这里需要理解堆的下浮操作关于堆的下浮操作可以参考这篇文【数据结构篇】堆
2.3 交换排序 两两相互比较当发现两个记录的次序相反时就进行交换直到没有反序的记录为止 交换排序的特点 交换操作交换排序通过比较相邻元素的大小并根据需要进行交换操作来达到排序的目的。常见的交换排序算法有冒泡排序和快速排序。原地排序交换排序通常是原地排序算法不需要额外的辅助空间。时间复杂度冒泡排序的平均和最坏时间复杂度为O(n^2)而快速排序的平均时间复杂度为O(nlogn)。快速排序的性能通常优于冒泡排序。
2.3.1 冒泡排序
算法介绍 冒泡排序Bubble Sort是一种简单的排序算法。它重复地遍历待排序的元素列表比较相邻两个元素的大小并按照规定的顺序交换它们直到整个列表排序完成。 实现步骤 Step1比较。从列表的第一个元素开始依次比较每个元素和其相邻的下一个元素。Step2交换。如果当前元素大于相邻的下一个元素则交换这两个元素的位置。Step3继续向后遍历重复执行上述步骤直到最后一个元素。Step4重复以上步骤直到没有任何交换操作发生即列表已排序完成。 示意图 第1轮
[3, 5, 1, 7, 2, 8, 4, 6, 9, 11]第2轮
[3, 1, 5, 2, 7, 4, 6, 8, 9, 11]第3轮
[1, 3, 2, 5, 4, 6, 7, 8, 9, 11]第4轮
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11]第5轮
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11]....第9轮
[1, 2, 3, 4, 5, 6, 7, 8, 9, 11]每一轮都会将一个最大值放到末尾这一点类似于堆排序
算法实现 /*** 冒泡排序** 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]) {// 如果发现左侧元素比当前元素小则进行交换swap(arr, j , j1);}}}}备注如果想要降序排序只需要修改为while (j gap arr[j - gap] temp) 即可
2.3.2 快速排序
算法介绍 快速排序Quicksort是 C.R.A.Hoare 于1962年提出一种分区交换排序采用分治策略。快速排序的基本思想从序列中选取一个主元并以该主元为基准通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。 快速排序是目前已知的平均速度最快的一种排序方法是对冒泡排序的一种改进。 主要实现步骤 Step1选取主元。一般是选取数组的第0个元素或最后一个作为主元Step2划分数组。遍历数组根据主元将数组划分成两个子数组如果是增序排序则左侧的子数组恒大于右侧子数组如果是降序排序则左侧的子数组恒小于右侧的子数组Step3递归。Step1和Step2递归进行 快排是实现方式有很多种可以选取固定主元比如每次都选取区间第一个元素作为主元每次都选取区间最后一个元素作为主元或者每次随机化选取主元。后面的代码实现我都会讲解一下三种不同的实现 温馨提示可以通过随机化主元让快速排序的时间复杂度更加稳定这在一些算法题中是比较有用的 示意图 方式一两个指针都往后遍历每次主元选择区间最右侧元素 方式二两个指针相向遍历每次选取区间最右侧元素作为主元 方式三以方式一为基础随机化主元 图略……
算法实现
PS我个人比较喜欢方式一方式二可能更加简介但是方式二的注意点比较多比如边界问题、能否取等问题 方式一两个指针都往后遍历每次主元选择区间最右侧元素 /*** 快速排序** param arr 待排序的数组*/private static void quickSort(int[] arr) {if (arr null || arr.length 0) {return;}quickSort(arr, 0, arr.length - 1);}/*** 快速排序** param arr 待排序的数组* param left 待划分区间的左边界* param right 待划分区间的右边界*/private static void quickSort(int[] arr, int left, int right) {if (left right) {// 区间只剩一个元素停止划分return;}// 将数组划分为两部分获取划分点位置int pivotIndex partition(arr, left, right);// 对划分的两部分进行递归快排quickSort(arr, left, pivotIndex - 1);quickSort(arr, pivotIndex 1, right);}/*** 划分区间** param arr 待排序的数组* param left 待划分区间的左边界* param right 待划分区间的右边界* return*/private static int partition(int[] arr, int left, int right) {// 选择区间最右侧元素作为主元int pivot arr[right];// 双指针从前往后遍历划分区间左侧区间 主元右侧区间 主元int i left - 1;for (int j left; j right; j) {if (arr[j] pivot) {// 如果当前元素比主元小就放到 i1 的左侧swap(arr, i, j);}}// 将主元放到分界点然后返回主元索引swap(arr, i 1, right);return i 1;}/*** 交换 arr 数组中索引为 i 和索引为 j 处的元素*/private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}方式二两个指针相向遍历每次选取区间最右侧元素作为主元 /*** 快速排序** param arr 待排序的数组*/private static void quickSort(int[] arr) {if (arr null || arr.length 0) {return;}quickSort(arr, 0, arr.length - 1);}/*** 快速排序** param arr 待排序的数组* param left 待划分区间的左边界* param right 待划分区间的右边界*/private static void quickSort(int[] arr, int left, int right) {if (left right) {// 区间只剩一个元素停止划分return;}// 将数组划分为两部分获取划分点位置int demarcation partition(arr, left, right);// 对划分的两部分进行递归快排quickSort(arr, left, demarcation-1);quickSort(arr, demarcation, right);}/*** 划分区间** param arr 待排序的数组* param left 待划分区间的左边界* param right 待划分区间的右边界* return*/private static int partition(int[] arr, int left, int right) {// 选择区间最右侧元素作为主元int pivot arr[right];// 双指针相向遍历划分区间左侧区间 主元右侧区间 主元int i left - 1;int j right 1;while (i j) {// i从前往后遍历寻找大于等于主元的元素while (arr[i] pivot) ;// j从后往前遍历寻找小于主元的元素while (arr[--j] pivot) ;if (i j) {// 如果 ij说明区间中不止一个元素需要进行交换swap(arr, i, j);}}return i;}/*** 交换 arr 数组中索引为 i 和索引为 j 处的元素*/private static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}注意点 指针移动判断是否取等 while (arr[i] pivot) ;
while (arr[--j] pivot) ;看代码就知道肯定是不能取等的因为如果取等可能会出现所有的数都相等那么指针的移动就会出界从而报索引越界异常。所以得到的区间肯定是 左侧区间 主元右侧区间 主元 移动指针是否在判断之前 在1.中我们就已经知道了左侧和右侧区间都可能等于主元如果我们先判断后移动指针此时做右区间各有一个等于主元的值那么此时就陷入了死循环为了避免这种情况我们就采用先移动后判断 为什么返回的分界点 i必须放在右侧区间 这个其实看我画的那个示意图就能够明白了因为区间划分完成后 i 索引对应的元素可能是大于等于主元的我们如果将 i 放到左侧区间那么就不满足左侧区间中的元素全部小于等于主元这就导致最终快排是无法成功的可能会一直陷入死循环
以上3点是方式二的一些注意点也解释了为什么要这样写 方式三随机化选取主元方式二实现 随机化快速排序能够在一定程度上让排序的时间更加稳定不至于因为固定选取主元导致出现极端的情况。 具体实现可以基于前面两种方式只是将主元进行了随机化我们可以通过随机选取一个索引然后将随机的主元与最左侧元素进行交换这样就又变成了固定主元了。 以下是核心代码 // 随机选择主元元素并将其交换到区间右侧int randomIndex random.nextInt(right - left 1) left;swap(arr, randomIndex, right);int pivot arr[right];2.4 归并排序
算法介绍 归并排序法Merge Sort以下简称MS是分治法思想运用的一个典范。归并排序的基本思想先将一个序列按照划分成一个个的有序子序列每个子序列都只有一个元素然后两两进行合并前提是两个子列表都有序形成一个新的有序列表再重复进行两两合并直到所有子列表合并成一个有序列表也就说明排序完成了。通常采用二路归并排序实现所谓的二路归并排序是指将相邻两个有序子序列合并为一个有序列表。 归并排序的特点 分治思想归并排序采用分治思想将待排序序列不断拆分成更小的子序列然后将子序列排序并合并成一个有序序列。常见的归并排序算法有自顶向下的递归实现和自底向上的迭代实现。稳定性归并排序是一种稳定的排序算法相等元素的相对顺序在排序前后保持不变。非原地排序归并排序需要额外的辅助空间来存储临时的合并结果因此它不是原地排序算法。时间复杂度归并排序的平均和最坏时间复杂度都为O(nlogn)其中n是待排序序列的长度。它的性能稳定且较为优秀。 主要实现步骤 Step1划分。通常是使用递归将一个序列按照 n / 2 n/2 n/2划分成一个个的有序的子序列Step2合并。将相邻的子序列两两合并成一个新的有序子序列 常见归并排序的实现方式 自顶向下归并排序Top-down Merge Sort 也被称为递归归并排序。使用分治法的思想将数组不断地分割成较小的子数组直到每个子数组只包含一个元素。然后按照从底部到顶部的顺序逐步对已经分割的子数组进行合并形成有序的更大的子数组最终得到完全排序的数组。递归实现方式通过递归调用和合并操作来完成排序。 自底向上归并排序Bottom-up Merge Sort 直接使用迭代的方式从单个元素开始两两合并相邻的子数组。每一次合并都会形成一个更大的有序子数组直到最后合并成一个完全排序的数组。不需要递归调用而是通过循环迭代依次合并子数组。具体过程是先两个两个地合并相邻子数组然后四个四个地合并依次类推直到整个数组排序完成。 原地归并排序 首先将待排序数组分割为多个子数组直到每个子数组只有一个元素。然后从单个元素开始两两合并相邻的子数组并将结果原地存回到原始数组中。这里的关键是通过交换元素的位置实现原地合并。重复上述合并操作每次合并的子数组大小翻倍直到整个数组完全有序。 PS我平常用的最多的是自顶向下实现的归并排序 示意图 自顶向下的递归实现 初始数组5, 3, 9, 1, 7, 2, 8, 4, 6, 0 递归分解成子数组5, 3, 9, 1, 7 和 2, 8, 4, 6, 0继续分解子数组5, 3 和 9, 1, 7以及 2, 8 和 4, 6, 0继续分解子数组5 和 3以及 9 和 1, 7和 2 和 8以及 4 和 6以及 0 开始归并操作 归并 5 和 33, 5归并 9 和 1, 71, 7, 9归并 2 和 82, 8归并 4 和 64, 6归并 00 继续归并 归并 3, 5 和 1, 7, 91, 3, 5, 7, 9归并 2, 8 和 4, 62, 4, 6, 8 最终归并 归并 1, 3, 5, 7, 9 和 2, 4, 6, 81, 2, 3, 4, 5, 6, 7, 8, 9 可以看到自顶向下是先分解后合并 自底向上的迭代实现 初始数组5, 3, 9, 1, 7, 2, 8, 4, 6, 0第一轮迭代 归并 [5] 和 [3]3, 5归并 [9] 和 [1]1, 9归并 [7] 和 [2]2, 7归并 [8] 和 [4]4, 8归并 [6] 和 [0]0, 6 第二轮迭代 归并 [3, 5] 和 [1, 9]1, 3, 5, 9归并 [2, 7] 和 [4, 8]2, 4, 7, 8归并 [0, 6]0, 6 第三轮迭代 归并 [1, 3, 5, 9] 和 [2, 4, 7, 8]1, 2, 3, 4, 5, 7, 8, 9归并 [0, 6]0, 6 最终归并 归并 [1, 2, 3, 4, 5, 7, 8, 9] 和 [0, 6]0, 1, 2, 3, 4, 5, 6, 7, 8, 9 可以看到自底向上是两两合并没有进行分界 原地归并排序实现 第一次合并 归并 [5] 和 [3]3, 5归并 [9] 和 [1]1, 9归并 [7] 和 [2]2, 7归并 [8] 和 [4]4, 8归并 [6] 和 [0]0, 6 第二次合并 第二次合并归并 [3, 5] 和 [1, 9]1, 3, 5, 9归并 [2, 7] 和 [4, 8]2, 4, 7, 8归并 [0, 6]0, 6 第三次合并 归并 [1, 3, 5, 9] 和 [2, 4, 7, 8]1, 2, 3, 4, 5, 7, 8, 9归并 [0, 6]0, 6 最终合并 归并 [1, 2, 3, 4, 5, 7, 8, 9] 和 [0, 6]0, 1, 2, 3, 4, 5, 6, 7, 8, 9 原地和自底向上的过程类似通过元素交换来实现排序没有使用辅助数组
算法实现 方式一自顶向下的递归实现 /*** 归并排序** param arr 待排序的数组*/private static void mergeSort(int[] arr) {if (arr null || arr.length 0){return;}mergeSort(arr, 0, arr.length-1);}/*** 归并排序** param arr 待排序的数组* param left* param right*/private static void mergeSort(int[] arr, int left, int right) {if (left right){// 区间只剩一个元素无需分解return;}int mid (left right) / 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[] temp new int[right - left 1];// 左区间起始索引用于遍历区间int i left;// 右区间起始位置用于遍历右区间int j mid 1;// 临时数组的起始索引用于遍历临时数组int k 0;// 遍历左右子区间进行合并while (i mid j right) {// 将左右区间中的较小值放入临时数组中if (arr[i] arr[j]) {temp[k] arr[i];} else {temp[k] arr[j];}}// 将左区间剩余元素复制到临时数组while (i mid) {temp[k] arr[i];}// 将右区间剩余元素复制到临时数组while (j right) {temp[k] arr[j];}// 将临时数组中的元素复制回原数组for (int m 0; m k; m) {arr[left m] temp[m];}}备注关于数组的合并数组拷贝可以替换成System.arraycopy(temp, 0, arr, left, k)注意不能使用Arrays.copyof() 方式二自底向上的迭代实现 /*** 归并排序** param arr 待排序的数组*/private static void mergeSort(int[] arr) {if (arr null || arr.length 0){return;}int n arr.length;// 遍历不同大小的子数组进行两两合并for (int i 1; i n; i * 2) {for (int j 0; j n - i; j i * 2) {merge(arr, j, j i - 1, Math.min(j i * 2 - 1, n - 1));}}}/*** 合并** param arr* param left* param mid* param right*/public static void merge(int[] arr, int left, int mid, int right) {// 临时数组用于存储合并后的结果int[] temp new int[right - left 1];// 左区间起始索引用于遍历区间int i left;// 右区间起始位置用于遍历右区间int j mid 1;// 临时数组的起始索引用于遍历临时数组int k 0;// 遍历左右子区间进行合并while (i mid j right) {// 将左右区间中的较小值放入临时数组中if (arr[i] arr[j]) {temp[k] arr[i];} else {temp[k] arr[j];}}// 将左区间剩余元素复制到临时数组while (i mid) {temp[k] arr[i];}// 将右区间剩余元素复制到临时数组while (j right) {temp[k] arr[j];}// 将临时数组中的元素复制回原数组for (int m 0; m k; m) {arr[left m] temp[m];}}可以看到两者基本上是类似的特别是合并代码基本上是一模一样的只是对于区间的划分不同迭代对于区间的划分可能没有递归那么好理解迭代 for (int i 1; i n; i * 2) {for (int j 0; j n - i; j i * 2) {merge(arr, j, j i - 1, Math.min(j i * 2 - 1, n - 1));}}第一个循环是控制步长也就是区间的大小区间都是两两合并所以i*2第二个循环是遍历起始索引一个区间的元素是i*2那么下一个区间的起始元素就是ji*2但是对于最后一个区间元素的个数可能不足所以需要进行一个防止越界的判断也就是Math.min(j i * 2 - 1, n - 1) 方式三原地归并排序 /*** 归并排序** param arr 待排序的数组*/private static void mergeSort(int[] arr) {if (arr null || arr.length 0){return;}mergeSort(arr, 0, arr.length-1);}/*** 归并排序** param arr 待排序的数组* param left* param right*/private static void mergeSort(int[] arr, int left, int right) {if (left right){// 区间只剩一个元素无需分解return;}int mid (left right) / 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 i left;// 右区间起始位置用于遍历右区间int j mid 1;// 遍历左右子区间进行合并while (i mid j right) {if (arr[i] arr[j]) {// 将右半部分的元素移动到左半部分的末尾int temp arr[j];for (int k j; k i; k--) {arr[k] arr[k - 1];}arr[i] temp;// 更新指针和中间位置mid;j;}i;}}2.5 非比较排序 非比较排序是不需要将记录进行两两比较的 非比较排序的特点 不依赖比较操作非比较排序算法不基于元素之间的比较操作而是利用其他技巧实现排序。常见的非比较排序算法有计数排序、桶排序和基数排序。时间复杂度非比较排序算法通常具有较好的时间复杂度。计数排序、桶排序和基数排序的平均和最坏时间复杂度都为O(nk)其中k是数据的取值范围。适用性局限非比较排序算法通常对输入数据有一定的限制比如要求数据是整数或字符串并且取值范围不过大。在满足条件的情况下非比较排序算法可以获得更好的性能。稳定性非比较排序算法中的计数排序和基数排序是稳定的而桶排序在某些实现方式下可以是稳定的。
2.5.1 计数排序
算法介绍 计数排序Counting Sort是一种线性时间复杂度的排序算法适用于一定范围内的整数排序。它不基于比较而是通过统计每个元素出现的次数然后根据统计信息将元素排列在正确的位置上。 实现步骤 Step1计算max、min、range。找出待排序数组中的最大值max和最小值min确定统计数组的大小range。Step2构造count数组。①记录每个元素出现的次数。遍历待排序数组统计每个元素的出现次数并将统计结果保存到count数组中。②求前缀和。计算每个元素在排序结果中的位置即前缀和使得count[i]表示小于等于元素i的元素个数。Step3构造temp数组。创建一个与待排序数组大小相同的辅助数组temp用于存储排序结果。Step4映射元素。从后向前遍历待排序数组根据count数组确定每个元素在排序结果中的位置并将元素放入temp数组中。Step5拷贝。将temp数组复制回原始数组完成排序。 示意图
算法实现 /*** 计数排序** param arr 待排序的数组*/public static void countingSort(int[] arr) {int n arr.length;// 获取数组中的最大值和最小值int max Arrays.stream(arr).max().getAsInt();int min Arrays.stream(arr).min().getAsInt();// 计算出数据的范围int range max - min 1;// 计数数组用于记录每一个元素出现的次数int[] count new int[range];// 结果数组用于临时存储排序的结果int[] temp new int[n];// 统计每个元素出现的次数for (int num : arr) {// num-min的目的是为了缩小范围范围从0开始避免浪费空间count[num - min];}// 计算前缀和for (int i 1; i range; i) {count[i] count[i - 1];}// 根据count数组确定每个元素在排序结果中的位置for (int i n - 1; i 0; i--) {// 通过索引定位到对应的元素让后将对应的元素映射到对应的位置int index count[arr[i] - min] - 1;temp[index] arr[i];// 计数器数组对应索引的元素已经被用过一次了计数-1count[arr[i] - min]--;}// 将临时数组复制回原始数组System.arraycopy(temp, 0, arr, 0, n);}count数组是核心
count的索引-1 arr[i] - min-1对应的 arr 元素的索引减一的是因为索引是从0开始的count的值count[index]对应的是当前元素前还有多少个元素
.5.2 桶排序
算法介绍 桶排序Bucket Sort是一种线性时间复杂度的排序算法它通过将待排序元素分布到不同的桶中并对每个桶内的元素进行排序最后按照桶的顺序将各个桶中的元素依次合并得到有序结果。 实现步骤 Step1确定桶的数量和范围。根据待排序数据的特点确定需要的桶的数量。一般来说桶的数量可以根据数据量的大小进行设置范围可以根据数据的最大值和最小值来计算。Step2将待排序数组元素分配到不同的桶中。遍历待排序数组根据元素的大小将其放入相应的桶中。Step3对每个桶内的元素进行排序。可以使用其他排序算法如插入排序、快速排序等对每个非空桶进行排序或者递归地使用桶排序对每个非空桶进行排序。Step4合并桶内的元素。将每个非空桶中的元素按照顺序依次合并到一个临时数组中。 示意图
算法实现 方式一基于Collections.sort()实现的桶排序 这种方式严格意义来说可能属于比较排序因为对于桶中的元素是直接使用了其它的比较排序算法比如插入排序、快速排序等等方式通过将桶中的元素排序完之后再进行合并 /*** 桶排序** param arr 待排序的数组*/public static void bucketSort(int[] arr) {int n arr.length;if (n 0) {return;}// 计算最小值和最大值int min arr[0];int max arr[0];for (int num : arr) {if (num min) {min num;} else if (num max) {max num;}}// 计算桶的数量 (最大元素-最小元素) / 桶的大小 1int bucketCount (max - min) / n 1;// 创建桶并将元素分配到桶中ArrayListArrayListInteger buckets new ArrayList(bucketCount);for (int i 0; i bucketCount; i) {buckets.add(new ArrayList());}for (int num : arr) {int bucketIndex (num - min) / n;buckets.get(bucketIndex).add(num);}// 对每个非空桶进行排序然后合并结果int index 0;for (ArrayListInteger bucket : buckets) {if (bucket.isEmpty()) {continue;}// 对桶中的元素进行排序可以使用其他排序算法对桶内元素进行排序Collections.sort(bucket);for (int num : bucket) {arr[index] num;}}}方式二基于递归实现的桶排序自顶向上3的递归 这种方式算是严格意义上的桶排序了完全没有进行元素之间的比较而是直接通过不断将元素划分成不同的桶最终划分成一个元素之后所有的元素都按照一定顺序分布在不同的桶中最后再进行合并即可完成排序 备注其实之前的计数排序本质也是桶排序它是自底向上4的桶排序 /*** 桶排序** param arr 待排序的数组*/public static void bucketSort(int[] arr){bucketSort(arr, arr.length);}/*** 桶排序* param arr 待排序的数组* param bucketCount 桶的数量*/public static void bucketSort(int[] arr, int bucketCount) {if (arr null || arr.length 0) {return;}// 查找最小值和最大值这种方式比 stream 流性能更好int min Integer.MAX_VALUE;int max Integer.MIN_VALUE;for (int num : arr) {min Math.min(min, num);max Math.max(max, num);}// 计算桶的大小和范围int bucketSize (max - min) / bucketCount 1;// 创建桶列表ListListInteger buckets new ArrayList();for (int i 0; i bucketCount; i) {buckets.add(new ArrayList());}// 分配元素到不同的桶中for (int num : arr) {int index (num - min) / bucketSize;buckets.get(index).add(num);}// 递归地对每个非空桶进行排序for (ListInteger bucket : buckets) {if (!bucket.isEmpty()) {int[] bucketArr bucket.stream().mapToInt(Integer::intValue).toArray();bucketSort(bucketArr, bucketCount);// 将排序后的结果放回桶中for (int i 0; i bucketArr.length; i) {bucket.set(i, bucketArr[i]);}}}// 合并桶的结果得到最终的有序数组int index 0;for (ListInteger bucket : buckets) {for (int num : bucket) {arr[index] num;}}}2.5.3 基数排序
算法介绍 基数排序Radix Sort是一种非比较性的排序算法它根据元素的位数进行排序。基数排序将待排序的元素按照个位、十位、百位等位数进行分组并依次对每个位数进行稳定的排序操作最终得到有序的结果。 实现步骤 Step1确定待排序数组中的最大值并确定其位数。这将用于确定排序的轮数。Step2创建 10 个桶每个桶对应一个数字0-9。Step3从最低有效位个位开始按照当前位的值将所有元素分配到相应的桶中。Step4将各个桶中的元素按照顺序合并为一个新的数组。Step5重复步骤 3 和步骤 4直到遍历完最高有效位最高位。 示意图
算法实现 /*** 基数排序** param arr 待排序的数组*/public static void radixSort(int[] arr) {if (arr null || arr.length 0){return;}// 获取数组中的最大值int max Integer.MIN_VALUE;for (int num : arr) {max Math.max(max, num);}// 确定最大值的位数int digits (int) Math.log10(max) 1;// 创建 10 个桶ListListInteger buckets new ArrayList();for (int i 0; i 10; i) {buckets.add(new ArrayList());}// 进行基数排序for (int i 0; i digits; i) {// 分配到桶中for (int num : arr) {// 计算num的第(i1)位上的数值并将该数存入对应的桶中int digit (num / (int) Math.pow(10, i)) % 10;buckets.get(digit).add(num);}// 合并桶中的元素int index 0;for (ListInteger bucket : buckets) {for (int num : bucket) {arr[index] num;}bucket.clear();}}}注意进行桶合并时一定要按照索引顺序从前往后遍历获取元素因为通过一位的合并最小的先入桶也就是桶中的元素索引越小值越小
备注如果想要降序排序只需要将合并桶元素的代码修改为 for (int j buckets.size() - 1; j 0; j--) {ListInteger bucket buckets.get(j);for (int k bucket.size() - 1; k 0; k--) {arr[index] bucket.get(k);}bucket.clear();}总结 备注
n数据规模也就是参与排序的元素个数k桶的个数In-place占用常数内存不占用额外内存Out-place占用额外内存 其中最为常见的排序算法有快速排序、归并排序
以上是对十大常见排序算法的一个基础讲解关于十大排序算法的水还是很深的其中有很多的扩展和变种要想完全吃透十大常见的排序算法还需要进一步学习感兴趣的可以直接到 LeetCode 上搜索对应的排序算法题进行专项练习一次来提高自己对这十大排序算法的熟练度以及更加深入的理解 参考文章 数据结构Java语言版雷军环、吴名星编著十大经典排序算法 十大经典排序你全都会了吗附源码、动图、万字详解十大经典排序算法动图演示堆排序完全二叉树最后一个非叶子节点的序号是n/2-1的原因 - 为了得到而努力 - 博客园 (cnblogs.com)【算法总结】快速排序及边界问题分析_快速排序边界分析_Ethan-Code的博客-CSDN博客三分钟搞懂桶排序 - 知乎 (zhihu.com) 在此致谢(^_^ゞ 内存也称主存是计算机的内部存储器是CPU与外存沟通的桥梁 ↩︎ 外存也称辅存是计算机的外部存储器常见的U盘、移动硬盘都是外存 ↩︎ 自顶向下自顶向下的方法是从原始问题开始通过将问题分解为更小的子问题并递归地解决这些子问题最终得到整体的解。在这种方法中我们先处理原始问题然后逐步地将问题分解为更小的子问题并通过递归调用解决这些子问题。自顶向下的方法通常使用递归的方式来实现 ↩︎ 自底向上自底向上的方法是从解决最基本、最小规模的子问题开始逐步合并得到整体的解。在这种方法中我们先处理较小规模的子问题然后将子问题的解合并起来直到达到原始问题的解。自底向上的方法通常使用迭代或者循环的方式来实现 ↩︎
