| 排序 | 平均時間復(fù)雜度 | 最差時間復(fù)雜度 | 最好時間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n^2) | O(n^2) | O(n) | 穩(wěn)定 |
| 選擇排序 | O(n^2) | O(n^2) | O(n^2) | 不穩(wěn)定 |
| 快速排序 | O(n*logn) | O(n^2) | O(n*logn) | 不穩(wěn)定 |
| 插入排序 | O(n^2) | O(n^2) | O(n) | 穩(wěn)定 |
| 希爾排序 | O(n^1.3) | O(n^2) | O(n) | 不穩(wěn)定 |
| 堆排序 | O(n*logn) | O(n) | 不穩(wěn)定 | |
| 歸并排序 | O(n*logn) | O(n*logn) | O(n*logn) | 穩(wěn)定 |
穩(wěn)定性：相同元素，排序后，相對位置的變化情況，不變則穩(wěn)定
公共代碼
//交換
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個元素小的則互換
比較次數(shù)：順序n次牺弄，逆序(n-1)+(n-2)+...+1=(1+n-1)(n-1)/2=n(n-1)/2
交換次數(shù)：順序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) {
//一次到底后，沒有交換過缀辩，提前結(jié)束，有這一步踪央，冒泡排序最好情況才能達(dá)到O(n)
return;
}
}
}
選擇排序
在數(shù)組中找到最小的元素放到起始位置臀玄，剩余的在繼續(xù)找最小的元素放到已排序的末尾，一直到排序完
比較次數(shù)：順序=逆序=(n-1)+(n-2)+...+1=(1+n-1)(n-1)/2=n(n-1)/2
交換次數(shù)：順序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);
}
}
快速排序（包含重復(fù)元素）
分治算法的思想
- 將某一個元素作為基準(zhǔn)元素健无，然后將數(shù)組分成兩邊，左側(cè)的數(shù)據(jù)比基準(zhǔn)元素小液斜，右側(cè)的比基準(zhǔn)元素大
- 然后將兩側(cè)的數(shù)組遞歸重復(fù)第一步
左右指針?biāo)鶎?yīng)的元素重復(fù)時（等于基準(zhǔn)元素）累贤，將左指針向右移動一位，繼續(xù)比較少漆，可使快速排序支持重復(fù)元素
最壞情況是每次的基準(zhǔn)為最大或者最小數(shù)字臼膏，那么所有數(shù)都劃分到一側(cè)去了 時間復(fù)雜度為O(n^2)
不穩(wěn)定是基準(zhǔn)值不保證都能在中間
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) {//當(dāng)左>=右時結(jié)束
while (leftIndex < rightIndex && array[leftIndex] < mid) {//從左向右一直找到>=基準(zhǔn)點(diǎn)
leftIndex++;
}
while (leftIndex < rightIndex && array[rightIndex] > mid) {//從右向左一直找到<=基準(zhǔn)點(diǎn)
rightIndex--;
}
//重復(fù)元素，左索引進(jìn)1再比較示损，左側(cè)將含有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);
}
插入排序
- 默認(rèn)第一個為有序數(shù)組
- 取下一個新元素渗磅，從有序數(shù)組后往前比較，小于新元素的往后移检访，直到找到大于新元素夺溢，然后在它后面新元素，一直重復(fù)排完所有
比較次數(shù)：順序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;
}
}
希爾排序
初始給定一個步進(jìn)長度step（一般是數(shù)組的一半）风响，則數(shù)組可劃分為[[0, step, step+step...],[1, 1+step, 1+step+step...]......[n, n+step, n+step+step...]]
依次對分組后的數(shù)組進(jìn)行插入排序
都排序好后步進(jìn)長度step在縮減一半，重新劃分?jǐn)?shù)組丹禀，在依次對分組后的數(shù)組進(jìn)行插入排序状勤，直到步進(jìn)長度step=1
步進(jìn)長度為1的時候鞋怀，就是最原始的插入排序，但由于之前的分組排序持搜，所以進(jìn)行原始插入排序密似，移動的數(shù)據(jù)量少，效率高
//寫法一
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;
//分組葫盼，一組組進(jìn)行插入排序
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】
//每組交替執(zhí)行残腌，先執(zhí)行第一組的step位，在執(zhí)行第二組1+step...直到所有組執(zhí)行了一次贫导，在步進(jìn)后一個段位抛猫，重復(fù)各組
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;
}
}
堆排序
將數(shù)組看成一個完全二叉樹
構(gòu)建一個任意節(jié)點(diǎn)都大于等于子節(jié)點(diǎn)完全二叉樹
完全二叉樹有以下性質(zhì)：
根節(jié)點(diǎn) = 0，節(jié)點(diǎn) = i孩灯，節(jié)點(diǎn)數(shù)量 = n闺金，則：
- 節(jié)點(diǎn)的左孩子 = 2i+1
- 節(jié)點(diǎn)的右孩子 = 2i+2
- 節(jié)點(diǎn)的父親 = (i-1)/2
- 最后的非葉子節(jié)點(diǎn) = 最后的葉子節(jié)點(diǎn)的父親 = (n-1)/2
構(gòu)建堆的復(fù)雜度
深度k = log(n)，要處理的節(jié)點(diǎn)數(shù) =n/2
最好的情況是峰档，不交換或交換后不用處理子節(jié)點(diǎn)
<= n/2
=> O(n)
最壞的是交換后還要處理子節(jié)點(diǎn)
節(jié)點(diǎn)i 的層數(shù) = log(i)败匹，節(jié)點(diǎn)i 的處理次數(shù) = 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層有節(jié)點(diǎn)數(shù) = 2^(i-1)讥巡，每個節(jié)點(diǎn)需要處理次數(shù) = (k-i)
=> 第i層需要處理的次數(shù) = 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)
調(diào)整堆的復(fù)雜度
循環(huán)次數(shù)：n-1掀亩，剩一個的時候不執(zhí)行
每次都是從根節(jié)點(diǎn)往下，調(diào)整次數(shù)為樹的層數(shù)-1欢顷，且每次調(diào)整都會少個節(jié)點(diǎn)
= 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))
所以起碼復(fù)雜度不會超過O(n*log(n))
整個算法最復(fù)雜的復(fù)雜度為O(nlog(n))+O(n) = O(nlog(n))
//調(diào)整堆，使節(jié)點(diǎ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;
//構(gòu)建堆
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);
}
}
歸并排序
自頂向下（先代碼分組成一個個數(shù)組刹泄，再一個個合并）
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;
}
自底向上（主觀上將他們分成一個個了，代碼直接對相鄰的數(shù)組合并）
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;
//兩兩合并相同長度的數(shù)組
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++];
}
}
//拷貝回原數(shù)組
int k = 0;
while (k < r.length) {
array[start++] = r[k++];
}
}
