類似于打撲克牌的操作 直接插入排序(算法過程, 效率分析, 穩(wěn)定性分析)

• 時間復(fù)雜度：最好情況 O(n), 最壞情況 O(n^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：是穩(wěn)定的

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// 插入排序for (int i = 1; i < nums.size(); ++i) {int cur_val = nums[i];int j = i - 1;while (j >= 0 && nums[j] > cur_val) {	// 尋找插入位置nums[j + 1] = nums[j];--j;}nums[j + 1] = cur_val;}return nums;}
};

直接插入排序是使用 順序查找的方法，從后往前尋找插入的位置
同理我們也可以使用二分查找的方式來尋找插入的位置
折半查找減少了比較的次數(shù)，將比較操作的時間復(fù)雜度降低為 O(logn)，但沒有減少移動的次數(shù)，整體時間復(fù)雜度還是 O(n^2)

• 時間復(fù)雜度：最好情況 O(n), 最壞情況 O(n^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：是穩(wěn)定的

class Solution {
public:int binarySearch(vector<int> nums, int right, int target) {// 找到第一個大于 target 的值int left = 0;// 使用左閉右閉區(qū)間while (left <= right) { // 區(qū)間不為空int mid = left + (right - left) / 2;// 循環(huán)不變量// nums[left - 1] <= target// nums[right + 1] > targetif (nums[mid] <= target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;}}return left;}vector<int> sortArray(vector<int>& nums) {// 折半插入排序for (int i = 1; i < nums.size(); ++i) {int cur_val = nums[i];int insert_pos = binarySearch(nums, i - 1, cur_val);for (int j = i - 1; j >= insert_pos; --j) {nums[j + 1] = nums[j]; }nums[insert_pos] = cur_val;}return nums;}
};

插入排序在序列基本有序時效率較高

基于這個特點(diǎn)，希爾排序就是對數(shù)組分組進(jìn)行插入排序，分組的組數(shù)就是 d，也即增量，一種簡單的增量序列就是從 num.size() / 2 開始，一直縮小到 1，當(dāng)然也可以采用其他的增量序列

• 時間復(fù)雜度：最好情況 O(n), 最壞情況 O(n^2)，平均復(fù)雜度 O(n^1.3)(了解即可)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定的

class Solution {
public:vector<int> sortArray(vector<int>& nums) {for (int d = nums.size() / 2; d >= 1; --d) {// 分組插入排序for (int k = 0; k < d; ++k) {// 組內(nèi)進(jìn)行插入排序for (int i = k + d; i < nums.size(); i += d) {int cur_val = nums[i];int j = i - d;while (j >= 0 && nums[j] > cur_val) {nums[j + d] = nums[j];j -= d;}nums[j + d] = cur_val;}}}return nums;}
};

• 時間復(fù)雜度：最好情況 O(n), 最壞情況 O(n^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// 冒泡排序for (int i = nums.size() - 1; i >= 1; --i) {bool swapped = false;for (int j = 0; j < i; ++j) {if (nums[j] > nums[j + 1]) {swap(nums[j], nums[j + 1]);swapped = true;}}if (!swapped) { // 沒有發(fā)生交換，說明代碼已經(jīng)有序break;}}return nums;}
};

步驟：

• 隨機(jī)選取一個位置 nums[i] = x
• 將大于 x 的值都移到 nums[i] 的左邊，小于 x 的值都移動到 nums[i] 的右邊
• 對 nums[0 ~i -1] 和 nums[i + 1 ~ n -1] 分別進(jìn)行快速排序
• …

步驟中的核心問題：如何 將大于 x 的值都移到 nums[i] 的左邊，小于 x 的值都移動到 nums[i] 的右邊?

• 時間復(fù)雜度：最好情況 O(n), 最壞情況 O(n^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：穩(wěn)定

class Solution {
public:void quickSort(vector<int>& nums, int left, int right) {if (left >= right) return; // 遞歸終止條件int p = partition(nums, left, right);quickSort(nums, left, p - 1);quickSort(nums, p + 1, right);}int partition(vector<int>& nums, int left, int right) {int p = left + rand() % (right - left + 1); // 生成 [left ~ right] 區(qū)間內(nèi)的隨機(jī)數(shù)swap(nums[p], nums[right]); // 將 pivot 和末尾值交換int i = left;// 維護(hù)的區(qū)間： [left, i) 區(qū)間內(nèi)的值小于等于 nums[right]// [j, right) 區(qū)間內(nèi)的值大于 nums[right]for (int j = left; j < right; ++j) {if (nums[j] <= nums[right]) {// 此時不滿足我們對區(qū)間的要求了// 調(diào)整區(qū)間使其滿足要求// {nums[left] ... nums[i-1]} {[nums[i] ... nums[j]]}swap(nums[i], nums[j]);++i;// --> {nums[left] ... nums[i-1] nums[j]} { ... nums[i]]}}}swap(nums[i], nums[right]);return i;}vector<int> sortArray(vector<int>& nums) {srand(time(0));     // 以當(dāng)前時間為隨機(jī)數(shù)種子quickSort(nums, 0, nums.size() - 1);return nums;}
};

但是上面這段代碼提交還是會超過時間限制，由于當(dāng)前的快速排序在處理包含大量相同元素的數(shù)組時，表現(xiàn)不佳?？焖倥判蛟谧顗那闆r下的時間復(fù)雜度是 O(n^2)

• 時間復(fù)雜度：最好情況 O(n), 最壞情況 O(n^2)
• 空間復(fù)雜度：O(1)
• 穩(wěn)定性：不穩(wěn)定

不穩(wěn)定性分析：
假設(shè)有一個數(shù)組 [4a, 2, 4b, 3]，其中 4a 和 4b 是兩個相同值的元素，但具有不同的初始順序。

• 第一輪：選擇 2 作為最小元素，然后與 4a 交換，數(shù)組變?yōu)?[2, 4a, 4b, 3]。

• 第二輪：選擇 3 作為最小元素，然后與 4a 交換，數(shù)組變?yōu)?[2, 3, 4b, 4a]。 注意此時 4a 和 4b 的相對順序已經(jīng)被改變：原本 4a 在 4b 之前，現(xiàn)在 4a被排在了 4b 之后。

因此，選擇排序是不穩(wěn)定的，因為它改變了相同值元素的初始順序。

class Solution {
public:vector<int> sortArray(vector<int>& nums) {// 選擇排序for (int i = 0; i < nums.size() - 1; ++i) {int min_idx = i;for (int j = i + 1; j < nums.size(); ++j) {if (nums[j] < nums[i]) {min_idx = j;            // 最小值的索引}}swap(nums[i], nums[min_idx]);   // 和最小值進(jìn)行交換}return nums;}
};

class Solution {
public:// 堆化函數(shù)：調(diào)整以 i 為根的子樹，n 為堆的大小void heapify(vector<int>& nums, int n, int i) {int largest = i;      // 初始化為根節(jié)點(diǎn)int left = 2 * i + 1; // 左孩子int right = 2 * i + 2; // 右孩子// 如果左孩子比根節(jié)點(diǎn)大if (left < n && nums[left] > nums[largest]) {largest = left;}// 如果右孩子比當(dāng)前最大值還大if (right < n && nums[right] > nums[largest]) {largest = right;}// 如果最大值不是根節(jié)點(diǎn)，交換并繼續(xù)堆化if (largest != i) {swap(nums[i], nums[largest]);// 遞歸對受影響的子樹進(jìn)行堆化heapify(nums, n, largest);}}vector<int> sortArray(vector<int>& nums) {int n = nums.size();// 從最后一個非葉子節(jié)點(diǎn)開始建堆，調(diào)整整個堆for (int i = n / 2 - 1; i >= 0; --i) {heapify(nums, n, i);}// 逐一將堆頂元素與末尾元素交換，并重新調(diào)整堆for (int i = n - 1; i > 0; --i) {// 將當(dāng)前堆頂（最大值）與末尾元素交換swap(nums[0], nums[i]);// 重新對剩下的部分進(jìn)行堆化heapify(nums, i, 0);}return nums;}
};