【数据结构】七大排序算法

排序的相关概念

排序的分类

根据在排序过程中带排序的记录是否全部被放置在内存中,排序分为:

  • 内排序
  • 外排序

1.内排序

内排序是在排序整个过程中,带排序的所有记录全部放置在内存中。

影响内排序的主要因素:

  • 时间性能。(主要受比较和移动两种操作的影响)
  • 辅助空间。
  • 算法的复杂性。
  • 内排序的分类

根据排序过程中借助的主要操作,内排序分为:

  • 插入排序
  • 交换排序
  • 选择排序
  • 归并排序

2.外排序

外排序是由于排序的记录个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才能进行。 按照算法的复杂度分类

  • 简单算法:冒泡排序、简单选择排序、直接插入排序。
  • 复杂排序:希尔排序、堆排序、归并排序、快速排序。

冒泡排序算法

因为在冒泡排序中要用到顺序表结构和数组两元素的交换,先把这些写成函数

1.1 冒泡排序的初级版实现

冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。

对于这段代码,是最简单的冒泡,其实就是最简单的交换排序而已。它的思路就是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在第一次循环后一定变成最小值。

假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}

  • i = 1时,9与1交换后,在第一位置的1与后面的关键字比较都小,因此它就只最小值。
  • i = 2时,第二位置先后由9换成5,换成3,换成2,完成了第二小的数字交换。
  • 后面数字依次比较和交换,得到最终结果。

1.2 冒泡排序的实现

对于上面的算法,代码虽然简单易懂,但是效率非常低。可以改进成接下来的代码

代码解释

假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}

i = 1时,变量j由8反向循环到1,逐个比较,将较小值交换到前面,直到最后找到最小值放置在了第1的位置。

i = 1j = 8时,6 > 2 ,因此交换了它们的位置,j = 7时,4 > 2, 所以交换......直到j = 2时,因为 1 < 2, 所以不交换。j = 1 时,9 > 1,交换,最终得到最小值1放置第一的位置。

在不断循环的过程中,除了将关键字1放到第一的位置,还将关键字2从第九位置提到了第三的位置,显然比前面的算法有进步。

i = 2时,变量j由8反向循环到2,逐个比较,在将关键字2交换到第二位置的同时,也将关键字4和3有所提升。

1.3 冒泡排序的优化

  • 在排序的过程中,增加一个标记变量flag来记录位置是否发生了变化
  • 如果没有发生交换,说明数组已经有序了。

测试

#define N 9 
int main(int argc, const char * argv[]) { 
     int i;
     int d[N] = {9,1,5,8,3,7,4,6,2};          
     SqList l0;     
     for (i = 0; i < N; i++)         
     l0.r[i+1] = d[i];     
     l0.length = N;          
     printf("排序前:\n");     
     for (i = 0; i < l0.length; i++) {         
     printf("%d ", l0.r[i+1]);     
     }     
     printf("\n");           
     printf("1.0 初级冒泡排序结果:\n");     
     BubblSort0(&l0);     
     for (i = 0; i < l0.length; i++) {         
     printf("%d ", l0.r[i+1]);     
     }     
     printf("\n");          
     printf("1.1 冒泡排序结果:\n");     
     BubbleSort(&l0);     
     for (i = 0; i < l0.length; i++) {         
     printf("%d ", l0.r[i+1]);     
     }     
     printf("\n");      
     printf("1.2 优化后冒泡排序结果:\n");     
     BubbleSort1(&l0);     
     for (i = 0; i < l0.length; i++) {         
     printf("%d ", l0.r[i+1]);     
     }     
     printf("\n");      
     return 0; 
     }

简单选择排序

简单选择排序法(Simple Selection Sort)是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换。

简单选择排序法的工作原理是:每一次从无序组的数据元素中选出最小(或最大)的一个元素,存放在无序组的起始位置,无序组元素减少,有序组元素增加,直到全部待排序的数据元素排完。

代码说明

  • 简单选择排序相对简单,交换移动数据的次数相当少,节约时间。
  • 简单选择排序的时间复杂度为O(n^2)

直接插入排序

直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录增1的有序表。

直接插入排序的核心思想:将一个记录插入到一个已经排序好的表中,以得到一个记录增加1的有序表。并且它把当前元素大的记录都往后移动,用以腾出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。

代码说明

  • 直接插入排序的时间复杂度为O(n^2)
  • 直接插入排序比冒泡和简单选择排序的性能要好一些。

希尔排序

希尔排序是对直接插入排序的改进:

  • 将原本有大量记录数的记录进行分组。分割成若干个子序列;
  • 对子序列分别进行直接插入排序;
  • 当整个序列都基本有序时(注意是基本有序),再对全体记录进行一次直接插入排序。
  • 所谓的基本有序,就是小的关键字基本在前,大的基本在后面,不大不小的基本在中间,如{9,1,5,8,3,7,5,6,2},变成{2,1,3,6,4,7,8,9}这样就是基本有序,但是像{1,5,9,7,8,2,4,6}这样9在第三位,2在倒数第三位就不是基本有序。
  • 对于分割子序列,采取跳跃分割的策略:将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序而不是局部有序。
  • 增量的选取非常关键,但是现在还是一个数学难题(迄今没有找到一种最好的增量序列),大量研究表明,增量序列为dlta[k] = 2^(t-k+1) - 1时,可以获得不错的效果。

希尔排序的核心思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

代码说明

  • 希尔排序的时间复杂度为O(n^(3/2)),要好于直接插入排序的O(n^2);
  • 增量的最后一个增量之必须等于1才行。
  • 由于记录是跳跃式的移动,所以希尔排序不是一种稳定的排序算法。

堆排法

堆的概念

堆是具有如下性质的完全二叉树:

  • 每个结点的值都大于或等于其其左右孩子结点的值,为大顶堆。
  • 或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。
  • 因此根节点一定是堆中所有结点最大(小)者。
  • 如图左边为大顶堆,右边为小顶堆:

堆排序算法

堆排序(Heap Sort)是利用堆(假设是大顶堆)进行排序。 堆排序的核心思想:

  • 将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。
  • 将根节点移走(其实就是将它与堆数组的末尾元素交换,此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次小值。
  • 重复上诉操作,便能得到一个有序序列。

堆排序算法核心

  • 如何由一个无序序列构建成一个堆
  • 如何在输出堆顶元素后,调整剩余元素成一个新的堆

堆排序算法代码实现

堆排序算法代码说明

  • 堆排序方法HeapSort中有两个for循环:第一个for循环完成将现在的待排序序列构建成一个大顶堆;第二个for循环完成逐渐将每个最大值的根节点与末尾元素交换,并且再调整其成为大顶堆。
  • 第一个for循环中的i = L->length / 2,i[9/2]=4开始,4->3->2->1的变化量。(这里赋值的原因是这些都是有孩子的结点)
  • 构建好有孩子的结点之后,就可以从上到下、从左到右,将每个将每个非终端结点(非叶子结点)当做根节点,将其和子树调整成大顶堆。
  • 函数HeadAdjust的作用是将数组构建成一个大顶堆,在构建的时候利用了二叉树的性质。
  • 构建堆的时间复杂度为O(n),重建堆的时间复杂度为O(nlogn),所以总体来说堆排序的时间复杂度为O(nlogn),性能上远好于冒泡、简单选择、直接插入的时间复杂度。
  • 在空间复杂度上,由于记录的交换和比较是跳跃式进行的,所以堆排序是一种不稳定的排序方法。

归并排序

归并排序(Merging Sort)是利用归并的思想实现的。2路归并排序的核心思想如下:

  • 假设初始序列有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2或者1的有序子序列
  • 再两两归并...如此重复,直至得到一个长度为n的有序序列为止。

6.1归并排序的实现思路(递归实现)

  • 将序列平均分成两部分
  • 分别对这两部分用递归来归并
  • 将这两部分归并到一起

归并排序的代码实现(递归实现)

归并排序的总结(递归实现)

  • 归并排序总的时间复杂度为O(nlogn),并且这是归并排序算法中最好、最坏、平均的时间性能。
  • 归并排序的空间复杂度为O(n+logn)
  • 归并排序是一种比较占内存,但是效率高且稳定的算法。

6.2归并排序的实现(迭代非递归实现)

用迭代实现的话,可以从最小的序列开始归并直到完成。

归并的迭代实现总结

  • 非递归的迭代方法,避免了递归时深度为log2n的栈空间,空间只是用到申请归并临时用的TR数组,因此空间复杂度为O(n).
  • 并且相对于递归,在时间性能上也有一定的提升,所以使用归并时,尽量使用非递归实现。

快速排序

快速排序(Quick Sort)的基本思想是:

  • 通过一趟排序将待排序记录分割成独立的两部分
  • 其中一部分记录的关键字均比另一部分记录的关键字小;
  • 则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。

快速排序的实现思路

  • 选取一个关键字,放到一个位置,使得它的左边的值都比它小,右边的值都比它大,这个关键字叫做枢轴(pivot)
  • 然后分别对左边和右边进行排序。

快速排序的代码实现

快速排序的代码说明

  • Partition函数就是将选取的pivotkey不断交换,将比它小的换到它的左边,比它大的交换到它的右边,它也在交换中不断更改自己的位置,直到完全满足这个要求为止。
  • 快速排序的时间性能取决于快速递归的深度,快排的时间复杂度为O(nlogn)
  • 快速排序的空间复杂度主要是递归造成的栈空间的使用,平均情况下空间复杂度为O(nlogn)
  • 由于关键字的比较和交换是跳跃进行的,因此,快排是一种不稳定的排序算法

快速排序的优化

  1. 优化选取枢轴 在上面的代码中,选取枢轴的方式为:pivotkey = L->r[low],即用序列的第一个元素作为枢轴,这是理想情况下 L->r[low]是中间数。但是对于其他情况,这种固定选取第一个关键子作为首个枢轴的方法就不是很合理。于是可以用下面的方法优化: 三数取中(median-of-three)法:取三个关键子进行排序,将中间数作为枢轴,一般取左端、右端和中间三个数,也可以随机选取。 九数取中(median-of-nine)法:先从数组中分三次取样,每次取三个数,三个样品各取中数,然后从这三个数当中再取出一个中数作为枢轴。

三数取中(median-of-three)法代码:

  1. 优化不必要的交换
  2. 优化小数组时的排序方案
  3. 优化递归操作

快速排序优化后的代码

排序总结

1. 排序分类

  • 希尔排序相当于直接插入排序的升级,同属于插入排序类
  • 堆排序相当于简单选择排序的升级,同属于选择排序类
  • 快速排序相当于冒泡排序的升级,同属于交换排序类

2. 性能比较

原文发布于微信公众号 - 我就是马云飞(coding_ma)

原文发表时间:2017-10-24

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

python学习第二天:python的函数、循环和条件、类

第一天学习了Python的基本操作,以及几种主要的容器类型,今天学习 ,这样才算对Python有一个大致的了解。今天的学习大纲如下: 三、函数 1、定义函数 四...

1796
来自专栏前端说吧

JS-原生代码或方法实现特定效果总结(更新中...)

3676
来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

1263
来自专栏深度学习自然语言处理

【珍藏版】长文详解python正则表达式

想要使用python的正则表达式功能就需要调用re模块,re模块为高级字符串处理提供了正则表达式工具。模块中提供了不少有用的函数,比如:compile函数、ma...

712
来自专栏GreenLeaves

JavaScript引用类型之Array数组的排序方法

数组中已经存在两个JavaScript给我们定义好的重排序的方法:reverse()和sort()方法,下面来简单分析下: 1、reverse()    用于反...

2116
来自专栏QQ音乐前端团队专栏

理解浮点数

相信大家在平常的 JavaScript 开发中,都有遇到过浮点数运算精度误差的问题。

6614
来自专栏我是攻城师

一个优雅的反转数组的算法

` 比较简单粗暴的方法是,遍历原始数组从最后一项向前遍历,然后把输出结果保存在一个新的数组里面,这样就完成了所谓的反转。

921
来自专栏Python数据科学

十大经典排序算法(Python代码实现)

排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。常见...

2681
来自专栏desperate633

深入理解python中的排序

进行一个简单的升序排列直接调用sorted()函数,函数将会返回一个排序后的列表:

851
来自专栏nnngu

算法01 七大排序之:冒泡排序和快速排序

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数...

3697

扫码关注云+社区

领取腾讯云代金券