1. 排序算法
1.1. 排序算法比較
| 排序算法 | 平均時間復(fù)雜度 | 最差時間復(fù)雜度 | 空間復(fù)雜度 | 數(shù)據(jù)對象穩(wěn)定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n2) | O(n2) | O(1) | 數(shù)組不穩(wěn)定，鏈表穩(wěn)定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(nlog2n) | O(n2) | O(log2n) | 不穩(wěn)定 |
| 歸并排序 | O(nlog2n) | O(nlog2n) | O(n) | 穩(wěn)定 |
| 希爾排序 | O(nlog2n) | O(n2) | O(1) | 不穩(wěn)定 |
| 堆排序 | O(nlog2n) | O(nlog2n) | O(1) | |
| 計數(shù)排序 | O(n+k) | O(m+n) | O(k) | 穩(wěn)定 |
| 桶排序 | O(n+k) | O(n) | O(n+k) | 穩(wěn)定 |
| 基數(shù)排序 | O(n*k) | O(n2) | O(n+k) | 穩(wěn)定 |
| 錦標(biāo)賽排序 |
1.2. 排序算法詳解
1.2.1. 起泡排序
insertionSort
- 起泡排序思路：
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。這步做完后，最后的元素會是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
<details><summary>實(shí)現(xiàn)</summary>
void swap(int & a, int & b) {
int c = a;
a = b;
b = c;
}
int bubble(int *num, int m) {
int flag = 0;
for (int i = 1; i < m; i++) {
if (num[i-1] > num[i]) {
swap(num[i-1], num[i]);
flag = i;
}
}
return flag;
}
void bubbleSort(int *num, int n) {
int fl = bubble(num, n);
while (fl) {
fl = bubble(num, fl);
}
}
<span id = "SelectionSort"></span>
1.2.2. 選擇排序
image
- 選擇排序思路：
- 在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置
- 從剩余未排序元素中繼續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?/li>
- 以此類推，直到所有元素均排序完畢
void SelectionSort(vector<int>& v) {
int min, len = v.size();
for (int i = 0; i < len - 1; ++i) {
min = i;
for (int j = i + 1; j < len; ++j) {
if (v[j] < v[min]) { // 標(biāo)記最小的
min = j;
}
}
if (i != min) // 交換到前面
swap(v[i], v[min]);
}
}
// 模板實(shí)現(xiàn)
template<typename T>
void Selection_Sort(std::vector<T>& arr) {
int len = arr.size();
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++)
if (arr[j] < arr[min])
min = j;
if(i != min)
std::swap(arr[i], arr[min]);
}
}
<span id = "InsertSort"></span>
1.2.3. 插入排序
image
- 插入排序思路：
- 從第一個元素開始，該元素可以認(rèn)為已經(jīng)被排序
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描
- 如果該元素（已排序）大于新元素，將該元素移到下一位置
- 重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置
- 將新元素插入到該位置后
- 重復(fù)步驟2~5
void InsertSort(vector<int>& v)
{
int len = v.size();
for (int i = 1; i < len - 1; ++i) {
int temp = v[i];
for(int j = i - 1; j >= 0; --j)
{
if(v[j] > temp)
{
v[j + 1] = v[j];
v[j] = temp;
}
else
break;
}
}
}
<span id = "QuickSort"></span>
1.2.4. 快速排序
image
- 快速排序思路：
- 選取第一個數(shù)為基準(zhǔn)
- 將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面
- 對左右區(qū)間重復(fù)第二步，直到各區(qū)間只有一個數(shù)
int partition(vector<int> & num, int lo, int hi) {
int pivot = num[lo];
int temp = lo;
while (lo < hi) {
while ((lo < hi) && (pivot <= num[hi]))
hi--;
num[lo] = num[hi];
while ((lo < hi) && (pivot >= num[lo]))
lo++;
num[hi] = num[lo];
//std::swap(num[hi], num[lo]);
}
num[lo] = pivot;
//std::swap(num[lo], num[temp]);
//for (auto w : num)
// cout << w << " ";
//cout << endl;
return lo;
}
void quickSo(vector<int> & num, int lo, int hi) {
if (hi - lo < 2)
return;
int mi = partition(num, lo, hi - 1);
quickSo(num,lo, mi);
quickSo(num,mi + 1, hi);
}
void quickSort(vector<int> & num) {
quickSo(num, 0, num.size());
}
迭代實(shí)現(xiàn)
// ----------------------------------------------------
// 模板實(shí)現(xiàn)快速排序（迭代）
struct Range {
int start, end;
Range(int s = 0, int e = 0) {
start = s, end = e;
}
};
template <typename T> // 整數(shù)或浮點(diǎn)數(shù)皆可使用,若要使用物件(class)時必須設(shè)定"小於"(<)、"大於"(>)、"不小於"(>=)的運(yùn)算子功能
void quick_sort(T arr[], const int len) {
if (len <= 0)
return; // 避免len等於負(fù)值時宣告堆疊陣列當(dāng)機(jī)
// r[]模擬堆疊,p為數(shù)量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
T mid = arr[range.end];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left] < mid && left < right) left++;
while (arr[right] >= mid && left < right) right--;
std::swap(arr[left], arr[right]);
}
if (arr[left] >= arr[range.end])
std::swap(arr[left], arr[range.end]);
else
left++;
r[p++] = Range(range.start, left - 1);
r[p++] = Range(left + 1, range.end);
}
}
<span id = "MergeSort"></span>
1.2.5. 歸并排序
image
- 核心思想：分而治之
- 實(shí)現(xiàn)步驟：
void MergeSort(){
遞歸條件
分組1
分組2
歸并
}
遞歸實(shí)現(xiàn)
template<typename T>
void merge(vector<T> &num, int lo, int mi, int hi) {
int lb = mi - lo;
int lc = hi - mi;
T *pa = &num[lo];
T *pb = new T[lb];
T *pc = &num[mi];
for (int i = 0; i < lb; i++) {
pb[i] = pa[i];
}
for (int m = 0, n = 0, k = 0; (m < lb) || (n < lc);) {
if ((m < lb) && ((n >= lc) || (pb[m] < pc[n])))
pa[k++] = pb[m++];
else
pa[k++] = pc[n++];
}
}
template <typename T>
void mergeSort(vector<T> & A,int lo, int hi) {
if (hi - lo < 2) //遞歸條件
return;
int mi = (hi + lo) >> 1;
mergeSort(A,lo, mi);
mergeSort(A,mi, hi);
merge(A,lo, mi, hi);
}
迭代實(shí)現(xiàn)
template<typename T>
void merge_sort(T arr[], int len) {
T* a = arr;
T* b = new T[len];
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
T* temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
delete[] b;
}
<span id = "ShellSort"></span>
1.2.6. 希爾排序
算法思想：
算法思想來源于插入排序，
先將n個待排序的序列分割成n/2組數(shù)據(jù)分別進(jìn)行插入排序，
然后依次分割成n/4組,n/8組,
直至最后只能分成一組數(shù)據(jù)進(jìn)行插入排序
算法演示：
1940317-0f04f8b6aec097bb
算法實(shí)現(xiàn)：
//希爾排序
void shellSort(int *p, int n) {
int temp = n;
while (temp >>= 1) {
for (int i = temp; i < n; i++) {
for (int j = i; j > 0; j -= temp) {
if (p[j] < p[j - temp]) {
Swap(p[j], p[j - temp]);
break;
}
}
}
}
}
<span id = "CountSort"></span>
1.2.7. 計數(shù)排序
算法思想：
對值比較集中的數(shù)據(jù)進(jìn)行排序先統(tǒng)計每個數(shù)據(jù)個數(shù)，再根據(jù)個數(shù)進(jìn)行排序
算法圖解
countingSort
算法實(shí)現(xiàn)
//計數(shù)排序
void countSort(int *p, int n) {
int max = p[0];
int min = p[0];
for (int i = 0; i < n; i++) { //找到最小與最大值
if (max < p[i])
max = p[i];
if (min > p[i])
min = p[i];
}
int space = max - min + 1;
int *num = new int[space](); //申請輔助空間
for (int i = 0; i < n; i++) { //統(tǒng)計
num[p[i] - min]++;
}
int j = 0;
for (int i = 0; i < space; i++) { //排序
while (num[i]--) {
p[j++] = i+min;
}
}
delete[]num;
}
<span id = "BucketSort"></span>
1.2.8. 桶排序
<span id = "RadixSort"></span>
1.2.9. 基數(shù)排序
image
<span id = "HeatSort"></span>
1.2.10. 堆排序
image
