改进网站建设,wordpress后台设置,然后做服装网站,深圳专业手机网站建设文章目录简介1.分析排序算法2.插入排序2.1.直接插入排序2.2.希尔排序3.选择排序3.1.直接选择排序3.2.堆排序3.2.1.堆的数据结构3.2.2.算法实现4.交换排序4.1.冒泡排序4.2.快速排序5.归并排序6.基数排序7.八大排序算法总结简介 排序对于任何一个程序员来说#xff0c;可能都不会…
文章目录简介1.分析排序算法2.插入排序2.1.直接插入排序2.2.希尔排序3.选择排序3.1.直接选择排序3.2.堆排序3.2.1.堆的数据结构3.2.2.算法实现4.交换排序4.1.冒泡排序4.2.快速排序5.归并排序6.基数排序7.八大排序算法总结简介 排序对于任何一个程序员来说可能都不会陌生。我学的第一个算法就是冒泡排序。大部分编程语言中也都提供了排序函数如Java语言在Jdk1.8版本里Arrays.sort里使用排序算法根据不同数据量使用不同的算法在数组元素小于47的时候用插入排序大于47小于286用双轴快排大于286用timsort归并排序; 比较经典和常用的就是以下八大排序。
推荐一个数据结构可视化的页面: https://visualgo.net/en
1.分析排序算法
排序算法的执行效率 对于排序算法执行效率的分析我们一般会从这几个方面来衡量
1.最好情况、最坏情况、平均情况时间复杂度: 分析排序算法的时间复杂度时要分别给出最好情况、最坏情况、平均情况下的时间复杂度。2.时间复杂度的系数、常数 、低阶 时间复杂度反应的是数据规模n很大的时候的一个增长趋势所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中我们排序的可能是10个、100个这种规模很小的数据所以在对同一阶时间复杂度的排序算法性能对比的时候我们就要把系数、常数、低阶也考虑进来。3.比较次数和交换次数 基于比较的排序算法的执行过程会涉及两种操作一种是元素比较大小另一种是元素交换。所以如果我们在分析排序算法的执行效率(时间复杂度)的时候应该把比较次数和交换或移动次数也考虑进去。
排序算法的内存消耗 算法的内存消耗可以通过空间复杂度来衡量排序算法也不例外。不过针对排序算法的空间复杂度有一个新的概念原地排序Sorted in place。原地排序算法就是特指空间复杂度是O(1)的排序算法原地排序就是指不申请多余的空间来进行的排序就是在原来的排序数据中比较和交换的排序像归并排序和 属于原地排序算法希尔排序、冒泡排序、直接插入排序、直接选择排序、堆排序、快速排序
排序算法的稳定性 仅仅用执行效率和内存消耗来衡量排序算法的好坏是不够的。针对排序算法我们还有一个重要的度量指标稳定性。这个概念是说如果待排序的序列中存在值相等的元素经过排序之后相等元素之间原有的先后顺序不变。 例如我们有一组数据156786按照大小排序之后就是156678。 这组数据里有两个6。经过某种排序算法排序之后如果两个6的前后顺序没有改变那我们就把这种排序算法叫作稳定的排序算法如果前后顺序发生变化那对应的排序算法就叫作不稳定的排序算法。
稳定排序算法: 冒泡排序、直接插入排序、归并排序、基数排序不稳定排序算法: 希尔排序、堆排序、直接选择排序快速排序
2.插入排序
2.1.直接插入排序
基本思想 直接插入排序(Insertion Sort) 对于少量元素的排序它是一种最简单的排序方法它的基本思想是将一个记录插入到已经排好序的有序表中从而一个新的、记录数增1的有序表。在其实现过程使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动。 例如我们在打牌玩斗地主的时候摸完牌然后整理顺序是一张一张的来将每一张牌插入到其他已经有序的牌中的适当位置。在计算机的实现中为了要给插入的元素腾出空间我们需要将其余所有元素在插入之前都向右移动一位。
算法描述 一般来说插入排序都采用in-place在数组上实现。具体算法描述如下
1.从第一个元素开始该元素可以认为已经被排序2.取出下一个元素在已经排序的元素序列中从后向前扫描3.如果该元素已排序大于新元素将该元素移到下一位置4.重复步骤3直到找到已排序的元素小于或者等于新元素的位置5.将新元素插入到该位置后6.重复步骤2~5 平均时间复杂度最好情况最坏情况空间复杂度O(n²)O(n²)O(n²)O(1)
基于Java语言实现代码如下 public static void sort(int nums[]) {for (int i 1; i nums.length; i) {//若第 i 个元素大于 i-1 元素则直接插入反之需要找到适当的插入位置后在插入。if (nums[i] nums[i - 1]) {int j i - 1;int x nums[i];//采用顺序查找方式找到插入的位置在查找的同时将数组中的元素进行后移操作给插入元素腾出空间while (j -1 x nums[j]) {nums[j 1] nums[j];j--;}//插入到正确位置nums[j 1] x;}}}//测试public static void main(String[] args) {int nums[] new int[]{3, 44, 38, 5, 47, 15, 36, 26, 27,2,46,4,19,50,48};sort(nums);System.out.println(Arrays.toString(nums));}总结: 插入排序所需的时间取决于输入元素的初始顺序。例如对一个很大且其中的元素已经有序(或接近有序)的数组进行排序将会比随机顺序的数组或是逆序数组进行排序要快得多。
2.2.希尔排序
基本思想 希尔排序(SheII Sort)也称 递减增量排序算法是插入排序的一种更高效的改进版本。希尔排序是 非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的
插入排序在对几乎已经排好序的数据操作时效率高即可以达到线性排序的效率但插入排序一般来说是低效的因为插入排序每次只能将数据移动一 希尔排序是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行依次直接插入排序。 将待排序数组按照步长gap进行分组然后将每组的元素利用直接插入排序的方法进行排序每次再将gap折半减小循环上述操作当gap1时利用直接插入完成排序。 可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量之后每次再减半直到增量为1。更好的步长序列取值可以参考维基百科。
算法描述
1.选择一个增量序列 q1q2……qk其中 qi qj, qk 12.按增量序列个数 k对序列进行 k 趟排序3.每次排序根据对应的增量 qi将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。 平均时间复杂度最好情况最坏情况空间复杂度O(nlog2 n)O(nlog2 n)O(nlog2 n)O(1)
基于Java语言实现代码如下 public static void sort(int nums[]) {int gap nums.length;while (true) {//增量每次减半gap / 2; for (int i 0; i gap; i) {//下面循环是一个插入排序for (int j i gap; j nums.length; j gap) {int k j - gap;while (k 0 nums[k] nums[k gap]) {int temp nums[k];nums[k] nums[k gap];nums[k gap] temp;k - gap;}}}if (gap 1) {break;}}}public static void main(String[] args) {int nums[] {86, 11, 54, 34, 53,12,45,81,19,65};sort(nums);System.out.println(Arrays.toString(nums));}总结 希尔排序更高效的原因是它权衡了子数组的规模和有序性。排序之初各个子数组都很短排序之后子数组都是部分有序的这两种情况都很适合插入排序。
3.选择排序
3.1.直接选择排序
基本思想 选择排序Selection sort是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上则它不会被移动。选择排序每次交换一对元素它们当中至少有一个将被移到其最终位置上因此对 n个元素的表进行排序总共进行至多 n-1 次交换。在所有的完全依靠交换去移动元素的排序方法中选择排序属于非常好的一种。
算法描述
1.从未排序序列中找到关键字最小的元素2.如果最小元素不是未排序序列的第一个元素将其和未排序序列第一个元素互换3.重复1、2步直到排序结束。
平均时间复杂度最好情况最坏情况空间复杂度O(n²)O(n²)O(n²)O(1)
基于Java语言实现代码如下 public static void sort(int[] nums) {for (int i 0; i nums.length; i) {int min i;//选出之后待排序中值最小的位置for (int j i 1; j nums.length; j) {if (nums[j] nums[min]) {min j;}}//最小值不等于当前值时进行交换if (min ! i) {int temp nums[i];nums[i] nums[min];nums[min] temp;}}}public static void main(String[] args) {int nums[] new int[]{3, 44, 38, 5, 47, 15, 36, 26, 27,2,46,4,19,50,48};sort(nums);System.out.println(Arrays.toString(nums));}总结选择排序的简单和直观名副其实这也造就了它”出了名的慢性子”无论是哪种情况哪怕原数组已排序完成它也将花费将近n²/2次遍历来确认一遍。即便是这样它的排序结果也还是不稳定的。 唯一值得高兴的是它并不耗费额外的内存空间。
3.2.堆排序
3.2.1.堆的数据结构 堆HeapHeapHeap一种特殊的树堆这种数据结构的应用场景非常多最经典的莫过于堆排序了。堆排序是一种原地的排序算法。 符合以下两点的树就是堆(二叉堆):
1.堆是一个完全二叉树2.堆中每一个节点的值都必须大于等于或小于等于其子树中每个节点的值。
第一点: 堆必须是一个完全二叉树,完全二叉树要求除了最后一层其他层的节点个数都是满的最后一层的节点都靠左排列。 第二点: 堆中的每个节点的值必须大于等于或者小于等于其子树中每个节点的值。实际上我们还可以换一种说法堆中每个节点的值都大于等于或者小 于等于其左右子节点的值。这两种表述是等价的。 下图中其中第1个和第2是大顶堆第3个是小顶堆第4个不是堆一般在应用中大顶堆用的比较多可用参考这个数据结构可视化网站二叉堆 https://visualgo.net/zh/heap 完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针单纯地通过数组的下标就可以找到一个节点的左右子节点和父节点。 以下用数组存储堆的例子
3.2.2.算法实现
基本思想 此处以大顶堆为例堆排序的过程就是将待排序的序列构造成一个堆选出堆中最大的移走再把剩余的元素调整成堆找出最大的再移走重复直至有序。
算法描述
1.先将初始序列K[1…n]建成一个大顶堆, 那么此时第一个元素K1最大, 此堆为初始的无序区.2.再将关键字最大的记录K1 (即堆顶, 第一个元素)和无序区的最后一个记录 Kn 交换, 由此得到新的无序区K[1…n−1]和有序区K[n], 且满足K[1…n−1].keys⩽K[n].key3.交换K1 和 Kn 后, 堆顶可能违反堆性质, 因此需将K[1…n−1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止。 平均时间复杂度最好情况最坏情况空间复杂度O(nlog2n)O(nlog2n)O(nlog2n)O(1)
代码实现 从算法描述来看堆排序需要两个过程一是建立堆二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆函数二是反复调用建堆函数以选择出剩余未排元素中最大的数来实现排序的函数。
创建堆和排序:
最大堆调整Max_Heapify将堆的末端子节点作调整使得子节点永远小于父节点创建最大堆Build_Max_Heap将堆所有数据重新排序堆排序HeapSort移除位在第一个数据的根节点并做最大堆调整运算
对于堆节点的访问
父节点i的左子节点在位置(2*i1);父节点i的右子节点在位置(2*i2);子节点i的父节点在位置floor((i-1)/2); public static void sort(int[] nums) {for (int i nums.length - 1; i 0; i--) {max_heapify(nums, i);//堆顶元素(第一个元素)与Kn交换int temp nums[0];nums[0] nums[i];nums[i] temp;}}/***** 将数组堆化* i 第一个非叶子节点。* 从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。* 叶子节点可以看作已符合堆要求的节点根节点就是它自己且自己以下值为最大。*/public static void max_heapify(int[] nums, int n) {int child;for (int i (n - 1) / 2; i 0; i--) {//左子节点位置child 2 * i 1;//右子节点存在且大于左子节点child变成右子节点if (child ! n nums[child] nums[child 1]) {child;}//交换父节点与左右子节点中的最大值if (nums[i] nums[child]) {int temp nums[i];nums[i] nums[child];nums[child] temp;}}}public static void main(String[] args) {int[] nums new int[]{91, 60, 96, 13, 35, 65, 46, 65, 10, 30, 20, 31, 77, 81, 22};sort(nums);System.out.println(Arrays.toString(nums));}总结由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列。 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序。
4.交换排序
4.1.冒泡排序
基本思想 冒泡排序Bubble Sort是一种简单的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 算法描述 比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 平均时间复杂度最好情况最坏情况空间复杂度O(n²)O(n)O(n²)O(1)
基于Java语言实现代码如下 public static void sort(int nums[]) {int temp;for (int i 0; i nums.length; i) {for (int j i 1; j nums.length; j) {if (nums[i] nums[j]) {temp nums[i];nums[i] nums[j];nums[j] temp;}}}}public static void main(String[] args) {int[] nums new int[]{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};sort(nums);System.out.println(Arrays.toString(nums));}总结由于冒泡排序只在相邻元素大小不符合要求时才调换他们的位置, 它并不改变相同元素之间的相对顺序, 因此它是稳定的排序算法。
4.2.快速排序
基本思想 快速排序(Quick Sort)的基本思想挖坑填数分治法。快速排序使用分治法Divide and conquer策略来把一个串行list分为两个子串行sub-lists。快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看快速排序应该算是在冒泡排序基础上的递归分治法。 快速排序的名字起的是简单粗暴因为一听到这个名字你就知道它存在的意义就是快而且效率高它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n²)但是人家就是优秀在大多数情况下都比平均时间复杂度为 O(n logn) 的排序算法表现要更好。
算法描述 快速排序使用分治策略来把一个序列list分为两个子序列sub-lists。步骤为
1.从数列中挑出一个元素称为基准pivot。2.重新排序数列所有比基准值小的元素摆放在基准前面所有比基准值大的元素摆在基准后面相同的数可以到任一边。在这个分区结束之后该基准就处于数列的中间位置。这个称为分区partition操作。3.递归地recursively把小于基准值元素的子数列和大于基准值元素的子数列排序。 递归到最底部时数列的大小是零或一也就是已经排序好了。这个算法一定会结束因为在每次的迭代iteration中它至少会把一个元素摆到它最后的位置去。 平均时间复杂度最好情况最坏情况空间复杂度O(nlog₂n)O(nlog₂n)O(n²)O(1)原地分区递归版
基于Java语言实现代码如下 /*** param nums * param low 起始* param high 结束*/public static void sort(int[] nums, int low, int high) {//已经排完if (low high) {return;}int left low;int right high;//保存基准值int pivot nums[left];while (left right) {//从后向前找到比基准小的元素while (left right nums[right] pivot) {right--;}nums[left] nums[right];//从前往后找到比基准大的元素while (left right nums[left] pivot) {left;}nums[right] nums[left];}// 放置基准值准备分治递归快排nums[left] pivot;sort(nums, low, left - 1);sort(nums, left 1, high);}public static void main(String[] args) {int[] nums new int[]{2, 5, 4, 3, 7, 1, 6, 2, 10};sort(nums,0,nums.length-1);System.out.println(Arrays.toString(nums));}总结快速排序和归并排序是两种稍微复杂的排序算法它们用的都是分治的思想代码都通过递归来实现过程非常相似。归并排序算法是一种在任何情况下时间复杂度都比较稳定的排序算法这也使它存在致命的缺点即归并排序不是原地排序算法空间复杂度比较高是O(n)。正因为此它也没有快排应用广泛。
5.归并排序
基本思想 归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法Divide and Conquer的一个非常典型的应用且各层分治递归可以同时进行。 归并排序算法是将两个或两个以上有序表合并成一个新的有序表即把待排序序列分为若干个子序列每个子序列是有序的。然后再把有序子序列合并为整体有序序列
算法描述 归并排序可通过两种方式实现:
自上而下的递归 (本文讲递归法)自下而上的迭代(请自行补充)
递归法假设序列共有n个元素
1.将序列每相邻两个数字进行归并操作形成 floor(n/2)个序列排序后每个序列包含两个元素2.将上述序列再次归并形成 floor(n/4)个序列每个序列包含四个元素3.重复步骤2直到所有元素排序完毕。 平均时间复杂度最好情况最坏情况空间复杂度O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)
基于Java语言实现代码如下 public static void sort(int [] nums,int lo,int hi){//判断是否是最后一个元素if(lohi){return;}//重中间将数组分为两个部分int midlo(hi-lo)/2;//分别递归将左右两半排好序sort(nums,lo,mid);sort(nums,mid1,hi);//将排好序的左右两半合并merge(nums,lo,mid,hi);}/**** param nums* param low 右偏移的数* param mid 中位数 * param high 查找的范围*/private static void merge(int[] nums,int low,int mid,int high){//复制原来的数组int [] copynums.clone();//定义一个k指定表示重什么位置开始修改原来的数组,i指针左半边的位置,j表示右半边的位置int klow,ilow,jmid1;while (khigh){if(imid){// 左半边的数据处理完成,将右半边的数copy就行nums[k]copy[j];}else if(jhigh){// 右半边的数据处理完成,将左半边的数copy就行nums[k]copy[i];}else if(copy[j]copy[i]){//右边的数小于左边的数,将右边的数拷贝到合适的位置,j指针往前移动一位nums[k]copy[j];}else{//左边的数小于右边的数,将左边的数拷贝到合适的位置,i指针往前移动一位nums[k]copy[i];}}}public static void main(String[] args) {int[] numsnew int[]{1,3,4,5,11,6,7,5,28};sort(nums,0,nums.length-1);System.out.println(Arrays.toString(nums));}总结: 从效率上看归并排序可算是排序算法中的”佼佼者”. 假设数组长度为n那么拆分数组共需logn, 又每步都是一个普通的合并子数组的过程 时间复杂度为O(n) 故其综合时间复杂度为O(nlogn)。另一方面 归并排序多次递归过程中拆分的子数组需要保存在内存空间 其空间复杂度为O(n)。
6.基数排序
基本思想 基数排序Radix sort是一种非比较型整数排序算法其原理是将整数按位数切割成不同的数字然后按每个位数分别比较。由于整数也可以表达字符串比如名字或日期和特定格式的浮点数所以基数排序也不是只能使用于整数。 基数排序将所有待比较数值正整数统一为同样的数位长度数位较短的数前面补零。然后从最低位开始依次进行一次排序。这样从最低位排序一直到最高位排序完成以后数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案 MSDMost significant digital 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。 LSD Least significant digital从最右侧低位开始进行排序。先从kd开始排序再对kd-1进行排序依次重复直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
算法描述 我们以LSD为例从最低位开始具体算法描述如下 1.取得数组中的最大数并取得位数 2.arr为原始数组从最低位开始取每个位组成radix数组 3.对radix进行计数排序利用计数排序适用于小范围数的特点 平均时间复杂度最好情况最坏情况空间复杂度O(d*(nr))O(d*(nr))O(d*(nr))O(nr)
基于Java语言实现代码如下 public static void sort(int[] nums) {if (nums.length 1) return;//取得数组中的最大数并取得位数int max 0;for (int i 0; i nums.length; i) {if (max nums[i]) {max nums[i];}}int maxDigit 1;while (max / 10 0) {maxDigit;max max / 10;}//申请一个桶空间int[][] buckets new int[10][nums.length];int base 10;//从低位到高位对每一位遍历将所有元素分配到桶中for (int i 0; i maxDigit; i) {//存储各个桶中存储元素的数量int[] bktLen new int[10];//分配将所有元素分配到桶中for (int j 0; j nums.length; j) {int whichBucket (nums[j] % base) / (base / 10);buckets[whichBucket][bktLen[whichBucket]] nums[j];bktLen[whichBucket];}//收集将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞int k 0;for (int b 0; b buckets.length; b) {for (int p 0; p bktLen[b]; p) {nums[k] buckets[b][p];}}base * 10;}}public static void main(String[] args) {int[] nums new int[]{3, 44, 38, 5, 47, 15, 36, 26, 27,2,46,4,19,50,48};sort(nums);System.out.println(Arrays.toString(nums));}7.八大排序算法总结
各种排序性能对比如下:
排序类型平均情况最好情况最坏情况辅助空间稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(n^1.3)O(nlogn)O(n²)O(1)不稳定归并排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(n)稳定快速排序O(nlog₂n)O(nlog₂n)O(n²)O(nlog₂n)不稳定堆排序O(nlog₂n)O(nlog₂n)O(nlog₂n)O(1)不稳定基数排序O(d(nk))O(d(nk))O(d(nkd))O(nkd)稳定
从时间复杂度来说:
平方阶O(n²)排序:各类简单排序直接插入、直接选择和冒泡排序线性对数阶O(nlog₂n)排序:快速排序、堆排序和归并排序O(n1§))排序§是介于0和1之间的常数希尔排序线性阶O(n)排序基数排序此外还有桶排序、计数排序
论是否有序的影响
当原表有序或基本有序时直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数时间复杂度可降至On而快速排序则相反当原表基本有序时将蜕化为冒泡排序时间复杂度提高为On2原表是否有序对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。
