排序：
基于比较：冒泡、插入、选择、快排、归并
非基于比较：桶、计数、基数
| 排序算法 | 最坏情况 | 最好情况 | 平均时间复杂度 | 是否稳定 | 原地排序 |
|---|---|---|---|---|---|
| 冒泡 | O(n^2) | O(n) | O(n^2) | 稳定 | O(1) |
| 插入 | O(n^2) | O(n) | O(n^2) | 稳定 | O(1) |
| 选择 | O(n^2) | O(n^2) | O(n^2) | 不稳定 | O(1) |
| 快排 | O(n^2) | O(nlogn) | O(nlogn) | 不稳定 | O(1) |
| 归并 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | O(n) |
冒泡排序：
交换次数=数组逆序度
// js 代码
function bubble(arr) {
let n = arr.length;
for (let i = 0; i < n; i++) {
let flag = false;
for (let j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = true;
}
}
if (!flag) { break; }
}
return arr;
}
// java
public static void bubble(int[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
插入排序：
移动次数=数组逆序度
function insert(arr) {
let n = arr.length;
for (let i = 1; i < n; i++) {
let j = i - 1;
let val = arr[i];
while(val < arr[j] && j >= 0) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = val;
}
return arr;
}
public static void insert(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
int j = i+1;
int val = arr[j];
while(j >= 1 && val < arr[j-1]) {
arr[j] = arr[j-1];
j--;
}
arr[j] = val;
}
}
归并排序：
分治法，合并
function mergeSort(arr, p, r) {
if (p >= r) {return;}
let q = Math.floor((p+r)/2);
mergeSort(arr, p, q);
mergeSort(arr, q+1, r);
merge(arr, p, q, r);
}
function merge(arr, p, q, r) {
let temp = [];
let i = p, j = q+1;
while(i <= q && j <= r) {
if (arr[i] <= arr[j]) {
temp.push(arr[i++]);
} else {
temp.push(arr[j++]);
}
}
let start = i <= q ? i : j;
let end = i <= q ? q : r;
while(start <= end) {
temp.push(arr[start++]);
}
let n = temp.length;
for (i = 0; i < n; i++) {
arr[p + i] = temp[i];
}
}
public static void mergeSort(int[] arr, int p, int r) {
if (p >= r) { return; }
int q = (p+r)/2;
Sort.mergeSort(arr, p, q);
Sort.mergeSort(arr, q+1, r);
Sort.merge(arr, p, q, r);
}
public static void merge(int[] arr, int p, int q, int r) {
int n = r-p+1;
int[] temp = new int[n];
int i = p, j = q+1, k = 0;
while(i <= q && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
int start = i <= q ? i : j;
int end = i <= q ? q : r;
while (start <= end) {
temp[k++] = arr[start++];
}
k = 0;
for (i = p; i <= r; i++) {
arr[i] = temp[k++];
}
}
快排：
分治法，分区
function quickSort(arr, p, r) {
if (p >= r) {return;}
let q = partition(arr, p, r);
quickSort(arr, p, q-1);
quickSort(arr, q+1, r);
}
function partition(arr, p, r) {
let pivot = arr[p];
let i = p+1, j = p+1;
while (i <= r && j <= r) {
if (arr[j] < pivot) {
let temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
}
j++;
}
let temp = arr[i-1];
arr[i-1] = pivot;
arr[p] = temp;
return i-1;
}
public static void quickSort(int[] arr, int p, int r) {
if (p >= r) { return; }
int q = Sort.partition(arr, p, r);
Sort.quickSort(arr, p, q-1);
Sort.quickSort(arr, q+1, r);
}
public static int partition(int[] arr, int p, int r) {
int pivot = arr[r];
int i = p, j = p;
for (j = p; j < r; j++) {
if (arr[j] < pivot) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
i++;
}
}
arr[r] = arr[i];
arr[i] = pivot;
return i;
}
