想了解更多精彩内容,快来关注一支穿云
1、冒泡排序
基本思想:比较相邻的元素大小,将小的前移,大的后移,就像水中的气泡一样,最小的元素经过几次移动,会最终浮到水面上。原地排序,不需要返回值。
输出:
冒泡排序 9.2384
函数sorted排序 0.0041
排序结果 True
2、选择排序
基本思想:第1趟,在待排序记录r1 ~ r[n]中选出最小的记录, 将它与r1交换;
第2趟,在待排序记录r2 ~ r[n]中选出最小的记录, 将它与r2交换;
以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录, 将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
原地排序,不需要返回值。
输出:
选择排序 7.4946
函数sorted排序 0.0040
排序结果 True
3、插入排序
插入排序总结:
当前需要排序的元素(array[i]),跟已经排序好的最后一个元素比较(array[i-1]), 如果满足条件继续执行后面的程序,否则循环到下一个要排序的元素。 缓存当前要排序的元素的值,以便找到正确的位置进行插入。 排序的元素跟已经排序好的元素比较,比它大的向后移动(升序)。 要排序的元素,插入到正确的位置。
4、希尔排序
希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序, 是直接插入排序算法的一种更高效的改进版本。 希尔排序是非稳定排序算法。该方法因DL.Shell于1959年提出而得名。 希尔排序是记录按下标的一定增量分组,对每组使用直接插入排序算法排序; 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时, 整个文件恰被分成一组,算法便终止。
5、基数排序
基数排序(radix sort)属于“分配式排序”(distribution sort),桶式排序 又称“桶子法”(bucket sort)或bin sort,顾名思义, 它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中, 藉以达到排序的作用,基数排序法是属于稳定性的排序, 其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数, 在某些时候,基数排序法的效率高于其它的稳定性排序法。
例如:对数组中的元素按照从低位到高位排序,对于[192,221,12,23] 第一轮按照个位数字相同的放在一组,是s[1] =[221],s[2]=[192,12],s[3]=23, 第二轮按照十位数字进行排序,s[1]=[12],s[2]=[221,23],s[9]=[192], 第三轮按照百位数字进行排序,s[0]=[12,23],s[1]=[192],s[2]=[221]
6、桶排序
桶排序 (Bucket sort)或所谓的箱排序,顾名思义就是运用桶的思想来将数据放到相应的桶内,再将每一个桶内的数据进行排序,最后把所有桶内数据按照顺序取出来,得到的就是我们需要的有序数据
7、快速排序
快速排序(quickSort) 快速排序是对冒泡排序的改进 快排的思想:首先任意选取一个数据(通常选用数组的第一个数)作为关键数据, 然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面, 这个过程称为一趟快速排序。
一趟快速排序的算法是: 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1; 2)以第一个数组元素作为关键数据,赋值给key,即key=A[0]; 3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j], 将A[j]和A[i]互换; 4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i], 将A[i]和A[j]互换; 5)重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值, 即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1, 直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。 另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
时间复杂度:O(nlgn) 快速排序是原地排序,不需要返回值
8、归并排序
归并排序:先分开再合并,分开成单个元素,合并的时候按照正确顺序合并。分: 假如我们有一个n个数的数列,下标从0到n-1
首先是分开的过程 1 我们按照 n//2 把这个数列分成两个小的数列
2 把两个小数列 再按照新长度的一半 把每个小数列都分成两个更小的 。。。一直这样重复,一直到每一个数分开了并:
两个有序数组排序的方法则非常简单,同时对两个数组的第一个位置进行比大小,将小的放入一个空数组,然后被放入空数组的那个位置的指针往后 移一个,然后继续和另外一个数组的上一个位置进行比较,以此类推。到最后任何一个数组先出栈完,就将另外一个数组里的所有元素追加到新数组后面。
由于递归拆分的时间复杂度是logN 然而,进行两个有序数组排序的方法复杂度是N,该算法的时间复杂度是N*logN 所以是NlogN。
9、堆排序
堆排序是采用二叉堆的数据结构来实现的。
二叉堆具有以下性质:
父节点的键值总是大于或等于(小于或等于)任何一个子节点的键值。每个节点的左右子树都是一个二叉堆(都是最大堆或最小堆)。步骤:
构造最大堆(Build_Max_Heap):若数组下标范围为0~n,考虑到单独一个元素是大根堆,则从下标n/2开始的元素为大根堆。于是只要从n/2-1开始,向前依次构造大根堆,这样就能保证,构造到某个节点时,它的左右子树都已经是大根堆。
堆排序(HeapSort):由于堆是用数组模拟的。得到一个大根堆后,数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点,并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换,再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换,再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间,故操作完后整个数组就是有序的了。
最大堆调整(Max_Heapify):该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整,使得子节点永远小于父节点 。
如果觉得《有哪些排序算法是在面试时经常被问到的?》对你有帮助,请点赞、收藏,并留下你的观点哦!