| 排序 | 平均时间复杂度 | 最差时间复杂度 | 最好时间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | 稳定 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | 不稳定 |
| 快速排序 | O(n*logn) | O(n^2) | O(n*logn) | 不稳定 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n^2) | O(n) | 不稳定 |
| 堆排序 | O(n*logn) | O(n) | 不稳定 | |
| 归并排序 | O(n*logn) | O(n*logn) | O(n*logn) | 稳定 |
稳定性：相同元素，排序后，相对位置的变化情况，不变则稳定
公共代码
//交换
public static void swap(int[] array, int i, int j) {
if (i == j) {
return;
}
array[i] ^= array[j];
array[j] ^= array[i];
array[i] ^= array[j];
}
public static void main(String[] args) {
int[] array = new int[10];
for (int i = 0; i < 10; i++) {
int num = ThreadLocalRandom.current().nextInt(100);
array[i] = num;
}
// array[1] = array[0];
System.out.println("原始：" + JsonManager.getGson().toJson(array));
int[] copyArray = Arrays.copyOf(array, array.length);
bubbleSort(copyArray);
System.out.println("冒泡：" + JsonManager.getGson().toJson(copyArray));
copyArray = Arrays.copyOf(array, array.length);
quickSort(copyArray, 0, copyArray.length - 1);
System.out.println("快排：" + JsonManager.getGson().toJson(copyArray));
}
冒泡排序
第i个元素和后面的元素一一比较，比第i个元素小的则互换
比较次数：顺序n次，逆序(n-1)+(n-2)+...+1=(1+n-1)(n-1)/2=n(n-1)/2
交换次数：顺序0次，逆序n*(n-1)/2
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
boolean swap = false;
for (int j = i + 1; j < array.length; j++) {
if (array[i] > array[j]) {
swap(array, i, j);
swap = true;
}
}
if (!swap) {
//一次到底后，没有交换过，提前结束，有这一步，冒泡排序最好情况才能达到O(n)
return;
}
}
}
选择排序
在数组中找到最小的元素放到起始位置，剩余的在继续找最小的元素放到已排序的末尾，一直到排序完
比较次数：顺序=逆序=(n-1)+(n-2)+...+1=(1+n-1)(n-1)/2=n(n-1)/2
交换次数：顺序0次，逆序n次
public static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int min = i;
for (int j = i + 1; j < array.length; j++) {
if (array[min] > array[j]) {
min = j;
}
}
swap(array, i, min);
}
}
快速排序（包含重复元素）
分治算法的思想
- 将某一个元素作为基准元素，然后将数组分成两边，左侧的数据比基准元素小，右侧的比基准元素大
- 然后将两侧的数组递归重复第一步
左右指针所对应的元素重复时（等于基准元素），将左指针向右移动一位，继续比较，可使快速排序支持重复元素
最坏情况是每次的基准为最大或者最小数字，那么所有数都划分到一侧去了 时间复杂度为O(n^2)
不稳定是基准值不保证都能在中间
public static void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int mid = array[left];
int leftIndex = left;
int rightIndex = right;
while (leftIndex < rightIndex) {//当左>=右时结束
while (leftIndex < rightIndex && array[leftIndex] < mid) {//从左向右一直找到>=基准点
leftIndex++;
}
while (leftIndex < rightIndex && array[rightIndex] > mid) {//从右向左一直找到<=基准点
rightIndex--;
}
//重复元素，左索引进1再比较，左侧将含有mid的值
if (leftIndex + 1 <= rightIndex && array[leftIndex] == array[rightIndex]) {
leftIndex++;
} else {
swap(array, leftIndex, rightIndex);//交换
}
}
quickSort(array, left, leftIndex - 1);
quickSort(array, leftIndex + 1, right);
}
插入排序
- 默认第一个为有序数组
- 取下一个新元素，从有序数组后往前比较，小于新元素的往后移，直到找到大于新元素，然后在它后面新元素，一直重复排完所有
比较次数：顺序n次，逆序1+2+...+(n-1)=n*(n-1)/2
交换词素：顺序=逆序=n次
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int preIndex = i - 1;
int value = array[i];
while (preIndex >= 0 && value < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = value;
}
}
希尔排序
初始给定一个步进长度step（一般是数组的一半），则数组可划分为[[0, step, step+step...],[1, 1+step, 1+step+step...]......[n, n+step, n+step+step...]]
依次对分组后的数组进行插入排序
都排序好后步进长度step在缩减一半，重新划分数组，在依次对分组后的数组进行插入排序，直到步进长度step=1
步进长度为1的时候，就是最原始的插入排序，但由于之前的分组排序，所以进行原始插入排序，移动的数据量少，效率高
//写法一
public static void shellSort(int[] array) {
int len = array.length;
int step = len / 2;
while (step > 0) {
//【0, step, step+step】
//【1, 1+step, 1+step+step】
int i = 0;
//分组，一组组进行插入排序
while (i < step) {
for (int j = i + step; j < array.length; j = j + step) {
int preIndex = j - step;
int value = array[j];
while (preIndex >= 0 && value < array[preIndex]) {
array[preIndex + step] = array[preIndex];
preIndex = preIndex - step;
}
array[preIndex + step] = value;
}
i++;
}
step /= 2;
}
}
//写法二
public static void shellSort2(int[] array) {
int len = array.length;
int step = len / 2;
while (step > 0) {
//【i, i+step, i+step+step】
//【i+1, i+1+step, i+1+step+step】
//每组交替执行，先执行第一组的step位，在执行第二组1+step...直到所有组执行了一次，在步进后一个段位，重复各组
for (int i = step; i < array.length; i++) {
int preIndex = i - step;
int value = array[i];
while (preIndex >= 0 && value < array[preIndex]) {
array[preIndex + step] = array[preIndex];
preIndex = preIndex - step;
}
array[preIndex + step] = value;
}
step /= 2;
}
}
堆排序
将数组看成一个完全二叉树
构建一个任意节点都大于等于子节点完全二叉树
完全二叉树有以下性质：
根节点 = 0，节点 = i，节点数量 = n，则：
- 节点的左孩子 = 2i+1
- 节点的右孩子 = 2i+2
- 节点的父亲 = (i-1)/2
- 最后的非叶子节点 = 最后的叶子节点的父亲 = (n-1)/2
构建堆的复杂度
深度k = log(n)，要处理的节点数 =n/2
最好的情况是，不交换或交换后不用处理子节点
<= n/2
=> O(n)
最坏的是交换后还要处理子节点
节点i 的层数 = log(i)，节点i 的处理次数 = k - log(i) = log(n) - log(i)
= log(n) -log(1)+...+log(n) -log(n)=n * log(n) - log(!n)=log(n^n / !n)
=>不会简化，换下一种解法
第i层有节点数 = 2^(i-1)，每个节点需要处理次数 = (k-i)
=> 第i层需要处理的次数 = 2^(i-1)*(k-i)
S = 2^(1-1)*(k-1) + 2^(2-1)*(k-2) + ... + 2^(k-1)*(1)
乘2错位
2S = 2^(2-1)*(k-1) + ....+ 2^(k-1)*(2) + 2^k*(1)
两个式相减
S = -2^(1-1)*(k-1) + 2^(2-1) + ...... + 2^(k-1) + 2^k*(1)
= 2+2^2+...+2^(k-1)-(k-1)
再乘2错位
2S = 2^2+...+2^(k-1)+2^k - 2(k-1)
再两个式相减
S = 2^k - 2 -(k-1) = 2^k - k-1
=>2^(log(n)) - log(n) -1 = n - logn -1
=>O(n)
调整堆的复杂度
循环次数：n-1，剩一个的时候不执行
每次都是从根节点往下，调整次数为树的层数-1，且每次调整都会少个节点
= log(n)-1 + log(n-1)-1 + log(n-2)-1 +...+ log(2)-1 = log(2)+...+log(n) - (n-1)
=log(!n)-n+1
完了又不会简化，和n*log(n)比较下吧
n*logn=log(n^n) > log(!n)
O(n*log(n)) > O(log(!n))
所以起码复杂度不会超过O(n*log(n))
整个算法最复杂的复杂度为O(nlog(n))+O(n) = O(nlog(n))
//调整堆，使节点k的子树，k最大
public static void adjustHeap(int[] array, int k, int length) {
int parent = k;
int child = 2 * parent + 1;
while (child < length) {
int rightChild = child + 1;
if (rightChild < length && array[child] < array[rightChild]) {
child = rightChild;
}
if (array[parent] >= array[child]) {
break;
}
swap(array, parent, child);
parent = child;
child = 2 * parent + 1;
}
}
//堆排序
public static void heapSort(int[] array) {
int len = array.length;
//构建堆
for (int i = (len - 1) / 2; i >= 0; i--) {
adjustHeap(array, i, len);
}
for (int i = len - 1; i > 0; i--) {
swap(array, 0, i);
adjustHeap(array, 0, i);
}
}
归并排序
自顶向下（先代码分组成一个个数组，再一个个合并）
public static int[] mergeSort(int[] array, int start, int end) {
if (start == end) {
return new int[]{array[start]};
}
//分组
int mid = (start + end) / 2;
int[] left = mergeSort(array, start, mid);
int[] right = mergeSort(array, mid + 1, end);
//合并
int i = 0, j = 0, rIndex = 0;
int[] r = new int[left.length + right.length];
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
r[rIndex++] = left[i++];
} else if (left[i] > right[j]) {
r[rIndex++] = right[j++];
} else {
r[rIndex++] = left[i++];
r[rIndex++] = right[j++];
}
}
if (j >= right.length) {
while (i < left.length) {
r[rIndex++] = left[i++];
}
}
if (i >= left.length) {
while (j < right.length) {
r[rIndex++] = right[j++];
}
}
return r;
}
自底向上（主观上将他们分成一个个了，代码直接对相邻的数组合并）
public static void mergeSort2(int[] array) {
int len = array.length;
//i为间隔
for (int i = 1; i < len; i *= 2) {
int start = 0;
int end = start + 2 * i;
//两两合并相同长度的数组
while (end < len) {
merge(array, start, start + i, end);
start = end;
end = start + 2 * i;
}
//剩余大于一个间隔，但不足两个间隔长度的
if (start + i < len) {
merge(array, start, start + i, len);
}
}
}
public static void merge(int[] array, int start, int mid, int end) {
int[] r = new int[end - start];
int i = start, j = mid, rIndex = 0;
while (i < mid && j < end) {
if (array[i] < array[j]) {
r[rIndex++] = array[i++];
} else if (array[i] > array[j]) {
r[rIndex++] = array[j++];
} else {
r[rIndex++] = array[i++];
r[rIndex++] = array[j++];
}
}
if (j >= end) {
while (i < mid) {
r[rIndex++] = array[i++];
}
}
if (i >= mid) {
while (j < end) {
r[rIndex++] = array[j++];
}
}
//拷贝回原数组
int k = 0;
while (k < r.length) {
array[start++] = r[k++];
}
}
