数据结构之排序算法
作者:离散梦
欢迎大家给出宝贵的建议!
数据结构之排序算法
稳定排序:冒泡、插入、归并、基数
不稳定排序:选择、快速、希尔、堆
口诀就是:快(快速)些(希尔)选(选择)一堆(堆)好朋友来玩吧!
1.冒泡排序
冒泡排序(Bubble Sort)一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。【时间复杂度为O(n^2),最好的情况就是有序的时候为O(n)】
算法思想过程:
冒泡排序算法——python实现程序
2.选择排序
选择排序(Selection Sort )就是通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换之。【时间复杂度为O(n^2)】
算法思想过程:
选择排序算法——python实现程序
3.插入排序
插入排序(Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。【时间复杂度为O(n^2),最好的情况是排好序的时候为O(n)】
算法思想过程:
注:下面排序之后答案是1,2,3,4,5,6,7,8.我下面这幅图有些许错误,就不重新作图了。
插入排序算法——python实现程序
4.归并排序
归并排序(Merging Sort)就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到[n/2]([x]表示不小于x的最小整数)个长度为2或1的有序子序列;再两两归并,......,如此重复,直至得到一个长度为n的有序序列为止,这种排序方法称为2路归并排序。【时间复杂度为O(nlogn),最坏情况和最好情况都是O(nlogn)】
算法思想过程:
归并排序算法——python实现程序
5.快速排序
快速排序(Quick Sort)的基本思想是:通过一趟排序将待记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。【时间复杂度为O(n^2),最优情况是O(nlogn)】
算法思想过程:
快速排序算法——python实现程序:
6.堆排序
堆是具有下列性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为大顶堆;或者每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆。【时间复杂度为O(nlogn)】
大顶堆:
小顶堆:
算法思想过程:
转换成大根堆:
在进行以下操作:
再不断重复以上操作,做大根堆,再排序。
堆排序算法——python实现程序:
7.希尔排序
是插入排序改良的算法,关键是步长的选择,选的越差的话,越接近O(n^2)。插入排序步长为1,希尔排序的步长是从大到小调整的。【时间复杂度为O(nlogn)】
算法思想过程:
希尔排序算法——python实现程序:
8.基数排序
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。【时间复杂度O(n)】
算法思想过程:
(1)建立0~9号桶
(2)把每个数根据个位数的数值选择进入对应的桶
(3)从0号桶到9号桶一次倒出
(4)再让它根据十位上的数值选择进入对应的桶
(5)从0号到9号桶依次倒出
(6)再让它根据百位上的数值进入对应的桶
(7)从0号桶到9号桶依次倒出
基数排序算法——python实现程序: