力扣(LeetCode)- 常见的排序算法总结 收藏 阅读:38
2020-11-17 17:58:50

1. 如何分析一个排序算法好坏

时间复杂度、比较和交换次数、原地排序(空间复杂度为(1))、排序稳定性(相等元素之间的位置先后顺序不变)。

有序度:是数组中具有有序关系的元素对的个数

逆序度:和有序度相反。

选择排序是不稳定排序,所以应用最少。

2. 插入排序比冒泡排序哪个好?

插入排序好。原因有如下两点:

  • 冒泡和插入虽然时间复杂度都是O(n2) ,元素移动次数都是等于逆序度,但是冒泡排序比插入排序多了三个赋值操作,性能有损耗,如下代码:

//冒泡排序数据交换 
if(a[j] > a[j+1]) {
  int tmp = a[j];    
  a[j]  = a[j+1];    
  a[j+1]  = tmp;    
  flag  = true;    
}  

//插入排序数据交换:  
if (a[j] > value) {    
 a[j+1]  = a[j];        
}

  • 插入排序比冒泡排序有更多的优化空间,比如希尔排序。

3. 常见的排序算法总结

序号 算法 时间复杂度 空间复杂度 是否原地排序 是否稳定算法 描述
1 冒泡排序 最好O(n)、最坏O(n2) O(1) 应用少
2 插入排序 O(n)、最坏O(n2)、平均O(n2) O(1) 应用较多
3 选择排序 最好最坏平均时间复杂度都是O(n2)。 O(1) 由于是不稳定排序算法,应用较少
4 归并排序(Merge Sort) O(nlogn) O(n) 分治思想。把数组不断的一分为二,排序后,归并。适合大量数据排序。
5 快速排序(Quicksort) O(nlogn),极端情况:O(n2) O(1) 分治思想。适合大量数据排序。
6 桶排序(Bucket sort) O(n)
7 计数排序(Counting sort) O(n) 桶排序特殊的一种
8 基数排序(Radix sort) O(n) 对数据有要求,前面的位数比较完毕,就可以确定大小。

4. 排序算法原理描述

  • 冒泡排序

    移动相邻位置的两个数据,重复执行。

  • 插入排序

    把数组分为两个区间,已排序和未排序区间。把数据从未排序区间插入已排序区间的合适位置。

  • 选择排序

    分已排序和未排序区间,从未排序中找到最小的元素,放到已排序区间的额末尾。原地排序、不稳定排序、最好最坏平均时间复杂度都是O(n2)。

  • 归并排序Merge Sort

    分治思想。假如把数组下标从x到y开始排序,不断的把数组一分为二,直到x>=y,结束。

    然后merge。建立一个临时数组,大小和要比较的数组大小相同,也就是A[x,y]。我们用两个游标 i 和 j,分别指向 A[x...q] 和 A[q+1...y] 的第一个元素。比较这两个元素 A[i] 和 A[j],如果 A[i]<=A[j],我们就把 A[i] 放 入到临时数组 tmp,并且 i 后移一位,否则将 A[j] 放入到数组 tmp,j 后移一位。

    继续上述比较过程,直到其中一个子数组中的所有数据都放入临时数组中,再把另一个数组中的数 据依次加入到临时数组的末尾,这个时候,临时数组中存储的就是两个子数组合并之后的结果了。 最后再把临时数组 tmp 中的数据拷贝到原数组 A[x...y] 中。

    稳定排序算法。时间复杂度都是O(nlogn) ,与原始数据是否有序无关。不是原地排序算法。

  • 快速排序 Quicksort

    从数组下标p到r,任意选一个数据作为pivot(分区点,一般选p到r最后一个),将小于pivot的数据放左边,大于放右边。然后将pivot左侧和右侧继续按照此方式排序,直到区间为1。

  • 桶排序(Bucket sort)

    将数据分成若干个有顺序的桶,每个桶内单独排序,然后依次取出就是有顺序了。

  • 计数排序(Counting sort)

    找出数组中最大的元素k,然后分成k个桶,每个桶内数据是相同的,桶之间就是排序好的数据。和桶排序的的大小力度不同。

  • 基数排序(Radix sort)

    对排序数据有要求,数据分隔不同的位,比较完前面的大小,数据后面的位数就不需要比较了。


读后有收获,请作者喝杯咖啡


全部评论

发表评论