一、排序分類
簡單寫下如下4種排序：
| 排序算法 | 平均時間復雜度 | 空間復雜度 | 穩(wěn)定性 |
|---|---|---|---|
| 冒泡排序 | O(n2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n2) | O(1) | 不穩(wěn)定 |
| 插入排序 | O(n2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(nlogn) | O(logn) | 不穩(wěn)定 |
二、排序介紹
2.1 冒泡排序
思路：比較相鄰的元素普碎。如果第一個比第二個大龙宏，就交換他們兩個晌涕。每輪冒泡出一個最大或者最小元素出來蚣常。
public static int[] bubbleSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
return arr;
}
冒泡排序
2.2選擇排序
思路：第一輪找到最小元素厘惦，與0號元素互換饥侵，第二輪找到第二小元素與1號元素互換鸵赫，以此類推
public static int[] selectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int min = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
return arr;
}
選擇排序
2.3 插入排序
思路：遍歷數組，后面的每一位都與前面已排序的數組進行掃描比較躏升，確定對應的順序位置并插入辩棒，其余元素均往后移1位。
public static int[] insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int cur = arr[i];
int j;
for (j = i-1; j >= 0; j--) { //與之前的每一個數比較
if(cur < arr[j]){
arr[j+1] = arr[j];//比較之后立即移動位置
}else {
break;
}
}
//插入屬于到對應位置（這里因為做了j--，所以需要+1加回來）
arr[j+1] = cur;
}
return arr;
}
插入排序
2.4 快速排序
思路：分治 + 遞歸
先從數列中取出一個數作為key值一睁，左右兩邊指針往中間走钻弄，左邊找出比基準大的數，右邊找出比基準小的數者吁，兩者交換窘俺。如果左右指針相交，則該位置值與基準位置交換值复凳。然后再依次遞歸當前基準位置的左邊部分和右邊部分瘤泪。最終每個小數列有序，拼成一整個有序數列育八。
public static void quickSort(int[] arr, int low, int high) {
if (low > high) {
return;
}
int i = low;
int j = high;
int key = arr[low];
while (i < j) {
while (key <= arr[j] && i < j) {
j--;
}
while (key >= arr[i] && i < j) {
i++;
}
if (i < j) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
}
}
//最后將基準位置與i和j重疊的位置交換
arr[low] = arr[i];
arr[i] = key;
//遞歸調用左半邊數組
quickSort(arr, low, j - 1);
//遞歸調用右半邊數組
quickSort(arr, j + 1, high);
}
快速排序
未完待續(xù)...
