最近小编看了很多文章,总结了很多,今天就让小编带你们看一看排序有哪些吧!
一、众所周知的排序
1.冒泡排序
特点:稳定,简单
原理:依次访问各个元素,如果顺序错误就把它们换过来
名字由来:因为越大的元素会经由交换慢慢浮到数列的顶端,就像碳酸饮料中的二氧化碳气泡最终浮到顶端一样,故叫做“冒泡排序”
时间复杂度:O(n²)
2.插入排序
特点:稳定,简单
原理:构建有序序列,对于未排序的数,在已知数列中找到相应位置,把后面的数据逐个往后挪,插入这个数
时间复杂度:O(n²)
3.快速排序
特点:速度快但不稳定
使用思想:分治
原理:从数列中挑出一个元素称为基准,重新排序,小的在前面,大的在后面,然后递归下去
时间复杂度:O(n²)或O(n log n),很少出现O(n²)的情况
4.归并排序
特点:速度快,稳定
使用思想:分治
原理:将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。
时间复杂度:O(n log n)
5.选择排序
特点:不稳定
原理:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
时间复杂度:O(n²)
6.桶排序
特点:只需要一个一维数组,简单,最快;
要求:需要数组大小和数据量一样大
时间复杂度:(求序列最大值,最小值运算量为n;创建空桶运输量为m,遍历序列运输量为n)O(n+m+n(logn-logm))
二、各路传奇排序
1.猴子排序
介绍:任意打乱数组,再检查是否排好序,如果是则输出,不是就再次打乱,直到排好为止
最佳情况时间复杂度:O(n)
最坏情况时间复杂度:O(n*n!)
无限猴子定理:一只猴子随机敲键盘,如果时间足够长,总能打出特定的文本,如:《莎士比亚全集》
2.面条排序
介绍:找到数组中最大和最小的两个数(O(n)),让最大的数对应一根很长的面条,最小的数对应一根很短的面条。一手握住这n根面条,在平放的桌面上直立着放下,让所有的面条底端接触到桌面。另一只手平行于桌面,从面条上方缓慢往下移动,每当这只手碰到一根面条,移走它,并把对应的数输出到结果数组中,直到移走全部面条。
3.指鹿为马排序
介绍:这个算法时间复杂度 O(n)。 聚集一帮人并向他们展示数组。 询问他们这个数组是否是排序好的。 干掉其中认为没有排序好的人。 重复几次,直到所有人同意这个数组是排序好的。