排序算法时间复杂

常用排序算法总结对比

相关术语

• **稳定:**如果a原本在b前面,而a=b,排序之后a仍然在b的前面
• **不稳定:**如果啊原本在b前面.而a=b,排序之后a可能出现在b的后面
• **内排序:**所有的排序操作都在内存中完成
• **外排序:**由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行
• **时间复杂度:**一个算法指向所耗费的时间
• **空间复杂度:**运行完一个程序所需的内存的大小
• **n:**数据规模
• k:"桶"的个数
• **In-place:**不占额外内存
• **Out-place:**占用额外内存
  

上面的堆排序我们还没有学过,我们将在二叉树中学习

冒泡排序

基本介绍
冒泡排序(Bubble Sorting)的基本思想:通过对待排序序列从前向后(从下标较小的元素开始,依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的气泡一样逐渐向上冒.
因为排序过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行交换,说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换,从而减少不必要的比较,(这里说的是优化,之后在基本的学完之后再说)

选择排序

基本介绍
选择排序也属于内部排序,是从欲排序的数据中,按指定的规则选出来某一元素,在依次规定交换位置后达到排序的目的.

排序思想
选择排序(Select sorting)也是一种简单的排序方法,它的基本思想是:第一次从arr[0] 到arr[n-1]中选取最小值,与arr[0]交换,第二次从arr[1]到arr[n-1]中选取最小值,与arr[1]交换,的三次arr[2]到arr[n-1]中选取最小值,与arr[2]交换,…,第i次从arr[i-1]到arr[n-1]中选取最小值,与arr[i-1]进行交换,…第arr[n-2]与arr[n-1]中选取最小值,与arr[n-2]交换,总共通过n-1次交换,得到一个排序码从小到大的排序有序序列.

插入排序

插入排序法思想
插入排序(Insertion Sorting)的基本思想是:把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含n-1个元素,排序的过程中每次从无序表中取出第一个元素,把它的排序码依次与有序表元素的排序码进行比较,将它插入到有序表中的适当位置,使之成为有序表.

希尔排序(优化的插入排序)

希尔排序法介绍
希尔排序(Donald Shell)于1959年提出的一种排序算法,希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序

希尔排序法基本思想
希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增加量逐渐减少,每组包含的关键词越来越多,每当增量减至1时,整个文件恰好被分为一组

快速排序

快速排序法介绍
快速排序(Quicksort)是对冒泡排序的一种改进,基本思想是:通过一趟排序将要排序的数据分割成独立两部分,其中一部分的所有数据都比另外一部分的所有数据小,然后在按照此方法对两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.

归并排序

归并排序介绍
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用金典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各个答案"修补"在一起,即分而治之)

基数排序

基数排序(桶排序)介绍:
1)基数排序(radixsort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或 bin sort,顾名思义,它是通过关键值的各个位的值,将要排序的元素分配至某些"桶"中,达到排序的作用.
2.基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法
3.基数排序(Radix Sort)是桶排序的扩展
4,基数排序是1887年赫尔曼,何乐礼发明的,他是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较.

基数排序的基本思想
1,将所有带比较数值同样为同样的数位长度,数位较短的数前面补零,然后,从最低位开始,依次进行排序,这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列.