一、概述?
假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的。
?
?
二、冒泡排序算法
1. 圖解：
2. 代碼：?
#include <iostream>
#include <vector>
using namespace std;void bubblesort(vector<int>& nums)
{int n = nums.size();int flag;for (int j = n - 1; j > 0; --j){flag = 0;for (int i = 0; i < j; ++i){if (nums[i] > nums[i + 1]){swap(nums[i], nums[i + 1]);flag = 1;}}if (flag == 0) break;}
}int main()
{vector<int> vec;int n;cin >> n;for (int i = 0; i < n; i++){int a;cin >> a;vec.push_back(a);}cout << "排序：";for (auto c : vec)cout << c << " ";return 0;
}
?
?
三、選擇排序算法
#include <iostream>
#include <vector>
using namespace std;void selectsort(vector<int>& res)
{int n = res.size(), min;for (int i = 0; i < n - 1; ++i){min = i;for (int j = i + 1; j < n; ++j){if (res[j] < res[min])min = j;}if (i != min)swap(res[i], res[min]);}
}int main()
{int n;cin >> n;vector<int> data;for (int i = 0; i < n; ++i){int a;cin >> a;data.push_back(a);}cout << "排序：";for (auto c : data)cout << c << " ";return 0;
}
?
?
四、直接插入排序算法
1. 動態演示
2. 時間復雜度：
- 插入排序最好、最壞、平均情況時間復雜度分析
3. 示例代碼：
#include <iostream>
#include <vector>
using namespace std;void insertSort(vector<int> &num)
{int len = num.size(), j;for (int i = 1; i < len; ++i){int key = num[i];j = i - 1;while (j >= 0 && num[j] > key){num[j + 1] = num[j];--j;}num[j + 1] = key;}
}int main()
{int n;cin >> n;vector<int> num;int s;for (int i = 0; i < n; ++i){cin >> s;num.push_back(s);}insertSort(num);for (auto c : num)cout << c << " ";
}?
?
六、
?
?
可以看到這種結構很像一棵完全二叉樹，本文的歸并排序我們采用遞歸去實現（也可采用迭代的方式去實現）。分階段可以理解為就是遞歸拆分子序列的過程，遞歸深度為logn。
2. 治階段：
再來看看治階段，我們需要將兩個已經有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1, 2, 3, 4, 5, 6, 7, 8]，來看下實現步驟。
?
代碼：
?
七、快速排序算法:
?
?
八、堆排序算法：
1. 算法圖解：
- 圖解堆排序
2. 代碼：?
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;void heapAdjust(vector<int>& arr, int i, int len)
{int left, right, j;while ((left = 2 * i + 1) <= len) //判斷當前父節點有無左節點(即有無孩子節點，left為左節點){right = left + 1; //右節點j = left; //j指針指向左節點if (right <= len && arr[left] < arr[right]) //右節點大于左節點j++; //當前把"指針"指向右節點//將父節點與孩子節點交換（如果上面if為真，則arr[j]為右節點，如果為假arr[j]則為左節點）if (arr[i] < arr[j]) swap(arr[i], arr[j]);else //說明比孩子節點都大，直接跳出循環語句break;i = j;}
}void heapSort(vector<int> & arr)
{int len = arr.size() - 1;for (int i = len / 2 - 1; i >= 0; i--)heapAdjust(arr, i, len);while (len >= 0){swap(arr[0], arr[len--]); //將堆頂元素與尾節點交換后，長度減1，尾元素最大heapAdjust(arr, 0, len); //再次對堆進行調整}
}int main()
{vector<int> vec;int n;cin >> n;for (int i = 0; i < n; i++){int a;cin >> a;vec.push_back(a);}heapSort(vec);for (auto c : vec)cout << c << " ";return 0;
}
?
)
)
)
)
