時間復(fù)雜度和空間復(fù)雜度
O(1) 常數(shù)
O(n) 線性
O(n^2) 平方
O(n^3)立方
O（n!）階乘
O(logn) 對數(shù)
O(nlogn)
O(2^) 指數(shù)
時間復(fù)雜度順序從小到大的順序O(1)<O(log n) < O(n )< O(nlogn) < O(n^2) <O(n^3) < O(2^n) <O(n!) < O(n^n)
對比.png
排序分類以及時間復(fù)雜度
| 類型 | 排序方法 | 時間復(fù)雜度-平均情況 | 時間復(fù)雜度-最好情況 | 時間復(fù)雜度-最壞情況 | 空間復(fù)雜度 | 穩(wěn)定性 |
|---|---|---|---|---|---|---|
| 插入排序 | 直接插入 | O(n^2) | O(N) | O(n^2) | O(1) | 穩(wěn)定 |
| 插入排序 | shell(希爾)排序 | O(n^2) | O(N) | O(n^2) | O(1) | 不穩(wěn)定 |
| 選擇排序 | 直接選擇 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
| 選擇排序 | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
| 交換排序 | 冒泡排序 | O(n^2) | O(N) | O(n^2) | O(1) | 穩(wěn)定 |
| 交換排序 | 快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(nlogn) | 不穩(wěn)定 |
| 歸并排序 | 快速排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 穩(wěn)定 |
快速排序（挖坑埋數(shù) + 分治法）
初始化 i= i帅刀， j =r吃警，x = a[i]，取數(shù)組第一個數(shù)作為基準數(shù)
j--,找出小與基準數(shù)的數(shù)據(jù)毁枯，挖出來挡鞍，放到默認的第一個坑中法褥；
i++找出大于等于基準數(shù)的值卖氨，放到剛才的坑中；
重復(fù)2残炮，3操作韭赘，當i==j中的話，把基準數(shù)放入其中
求出第一個基準數(shù)后势就，然后遞歸基準數(shù)的左邊泉瞻，基準數(shù)的右邊
void quick_sort(int s[], int l, int r)
{
if (l < r)
{
int i = l, j = r, x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) {// 從右向左找第一個小于x的數(shù)
j--;
}
if(i < j) {
s[i++] = s[j];
}
while(i < j && s[i] < x) {// 從左向右找第一個大于等于x的數(shù)
i++;
}
if(i < j) {
s[j--] = s[i];
}
}
s[i] = x;
quick_sort(s, l, i - 1); // 遞歸調(diào)用
quick_sort(s, i + 1, r);
}
}
冒泡排序
void bubbleSort(int arr[]){
if(arr==null || arr.length < 2 ){
return;
}
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1 ; j++) {
if(arr[j] > arr[j+1]){
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
