经典的常用的几种排序算法
| 排序算法 | 时间复杂度 | 是否基于比较 |
|---|---|---|
| 冒泡，选择，插入 | O(n2) | 是 |
| 快排，归并 | O(nlogn) | 是 |
| 桶，计数，基数 | O(n) | 否 |
有序度和逆序度
有序度指数组中具有有序关系的元素对的个数
a[i] <= a[j] , i<j
例如数组[2,4,1,3,5]，存在有序元素对 (2,4)，(2,3)，(2,5)，(4,5)，(1,3)，(1,5)
因此有序度是6
基于此，可以得出满有序度的定义，满有序度即有序数组的有序度。
满有序度 = n * (n - 1) / 2
逆序度定义与有序度相反。
逆序度 = 满有序度 - 有序度
排序算法的稳定性
稳定性 是指，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。
冒泡排序 Bubble Sort
public static void sort(int[] a) {
int n = a.length;
for (int i = 0; i < n - 1; i++) {
// （优化）记录是否存在数据交换
boolean hasExchange = false;
for (int j = 0; j < n - i - 1; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
hasExchange = true;
}
}
// 如果不存在数据交换，则说明已处于有序状态
if (!hasExchange) {
return;
}
}
}
原理很简单，每次对两个相邻的元素进行比较，若不满足大小关系则进行互换。
每次冒泡都会使至少一个元素移动到它应该在的位置。
最多重复n次冒泡，就能完成n个元素的排序。
我们发现有序数列冒泡时不存在互换行为，反之亦然，即不存在互换表示数列处于有序状态。
因此可以这样优化：记录一次冒泡过程中是否发生了互换，如果未发生，则表明排序完成。
在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候 不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是 稳定 的排序算法。
最差 / 平均 / 最好 时间复杂度：O(n2) / O(n2) / O(n)
空间复杂度：O(1)
选择排序 Select Sort
public static void sort(int[] a) {
for (int i = 0; i < a.length; i++) {
int minIndex = i;
for (int j = i + 1; j < a.length; j++) {
if (a[minIndex] > a[j]) {
minIndex = j;
}
}
int temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
}
原理 类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾（或者说是与未排序区间的第一位互换）。
选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，所以是 不稳定 的。
最差 / 平均 / 最好 时间复杂度：O(n2) / O(n2) / O(n2)
空间复杂度：O(1)
插入排序 Insertion Sort
public static void sort(int[] a) {
for (int i = 1; i < a.length; i++) {
int temp = a[i];
// 寻找需要插入的位置
int j = i - 1;
for (; j >= 0; j--) {
if (temp < a[j]) {
// 移动数据
a[j + 1] = a[j];
} else {
break;
}
}
// 因为在找到插入位置后j自减1，这里要加回来
a[j+1] = temp;
}
}
原理
首先，我们将数组中的数据分为两个区间，已排序区间和未排序区间。
初始已排序区间只有一个元素，就是数组的第一个元素。
插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。
重复这个过程，直到未排序区间中元素为空，算法结束。
在插入排序中，对于值相同的元素，可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是 稳定 的排序算法。
最差 / 平均 / 最好 时间复杂度：O(n2) / O(n2) / O(n)
空间复杂度：O(1)
希尔排序 Shell Sort
静态图示例如下：
public static void sort(int[] arr) {
// 缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 插入排序
for (int i = gap; i < arr.length; i++) {
int tmp = arr[i];
int j;
for (j = i; j - gap >= 0 && tmp < (arr[j - gap]); j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
希尔排序是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
原理
希尔排序通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
希尔排序不基于相邻比较，在跳跃比较和排序的过程中，是不稳定的。
时间复杂度：O(n1.3~2)
空间复杂度：O(1)
