經(jīng)典排序有以下幾種：
O(n2)：冒泡排序、插入排序、選擇排序 基于比較
O(nlogn)：歸并排序、快速排序 基于比較
O(n)：捅排序、計(jì)數(shù)排序、基數(shù)排序
如何分析排序算法
1，最好時(shí)間復(fù)雜度，最壞時(shí)間復(fù)雜度，平均時(shí)間復(fù)雜度
2，時(shí)間復(fù)雜度的系數(shù)，常數(shù)，低階
3，比較次數(shù)和交換次數(shù)
排序算法內(nèi)存消耗
排序算法穩(wěn)定性
冒泡排序
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
Utils.exchange(arr, j, j + 1);
}
}
}
}
可以優(yōu)化如果沒有交換跳出循環(huán)
public static void sort2(int[] arr) {
for (int i = 0; i < arr.length; i++) {
boolean flag = false;//提前退出排序標(biāo)志
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
Utils.exchange(arr, j, j + 1);
flag = true;//表示有數(shù)據(jù)交換
}
}
if (!flag)//沒有數(shù)據(jù)交換提前退出
break;
}
}
冒泡排序性能分析
是原地排序算法么？
冒泡排序只涉及到相鄰兩個(gè)元素交換，空間復(fù)雜度是O(1)，所有是原地排序
是穩(wěn)定排序算法么？
冒泡排序中只有比較才會(huì)交換順序，所以我們控制在相等時(shí)不交換元素順序即可，所以冒泡排序是穩(wěn)定排序算法
時(shí)間復(fù)雜度是多少？
最好的情況下數(shù)據(jù)為有序，我們只需要進(jìn)行一次冒泡即可，時(shí)間復(fù)雜度為O(n)
最壞的情況下數(shù)據(jù)為倒序，我們需要進(jìn)行n次冒泡操作，時(shí)間復(fù)雜度為O(n2)
平均時(shí)間復(fù)雜度為O(n2)
插入排序
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int value = arr[i];
int j = i - 1;
//查找插入位置
for (; j >= 0; j--) {
if (arr[j] > value) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j+1] = value;//插入數(shù)據(jù)
}
}
插入排序性能分析
是原地排序算法么？
空間復(fù)雜度是O(1)，是原地排序
是穩(wěn)定排序算法么？
對(duì)于相同的值，我們可以把后面出現(xiàn)的元素插入到之前出現(xiàn)元素的后面，所以是穩(wěn)定排序算法
時(shí)間復(fù)雜度是多少？
最好的情況下數(shù)據(jù)為有序，我們只需要遍歷一次，時(shí)間復(fù)雜度為O(n)
最壞的情況下數(shù)據(jù)為倒序，相當(dāng)于每次都是在數(shù)組的第一個(gè)位置插入元素，時(shí)間復(fù)雜度為O(n2)
平均時(shí)間復(fù)雜度為O(n2)
選擇排序
//選擇排序：從待數(shù)組中選擇出一個(gè)最小放入排序數(shù)組中以此類推
public static void sort(int[] arr) {
int minIndex;
for (int i = 0; i < arr.length; i++) {
minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
Utils.exchange(arr, i, minIndex);
}
}
選擇排序性能分析
是原地排序算法么？
空間復(fù)雜度是O(1)，是原地排序
是穩(wěn)定排序算法么？
不是穩(wěn)定的排序算法
時(shí)間復(fù)雜度是多少？
最好的情況下數(shù)據(jù)為有序，復(fù)雜度為O(n2)
最壞的情況下數(shù)據(jù)為倒序，復(fù)雜度為O(n2)
平均時(shí)間復(fù)雜度為O(n2)
