时间复杂度、比较和交换次数、原地排序(空间复杂度为(1))、排序稳定性(相等元素之间的位置先后顺序不变)。
有序度:是数组中具有有序关系的元素对的个数
逆序度:和有序度相反。
选择排序是不稳定排序,所以应用最少。
插入排序好。原因有如下两点:
冒泡和插入虽然时间复杂度都是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];
}
插入排序比冒泡排序有更多的优化空间,比如希尔排序。
序号 | 算法 | 时间复杂度 | 空间复杂度 | 是否原地排序 | 是否稳定算法 | 描述 |
---|---|---|---|---|---|---|
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) | 对数据有要求,前面的位数比较完毕,就可以确定大小。 |
冒泡排序
移动相邻位置的两个数据,重复执行。
插入排序
把数组分为两个区间,已排序和未排序区间。把数据从未排序区间插入已排序区间的合适位置。
选择排序
分已排序和未排序区间,从未排序中找到最小的元素,放到已排序区间的额末尾。原地排序、不稳定排序、最好最坏平均时间复杂度都是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)
对排序数据有要求,数据分隔不同的位,比较完前面的大小,数据后面的位数就不需要比较了。