目錄

1.三種常見的簡單排序：

1.1冒泡排序

1.2 選擇排序

1.3?插?排序

2 常見高級排序算法

?2.1?希爾排序

2.2 快速排序

2.3?歸并排序

2.4計數排序?

先上結論：

1.三種常見的簡單排序：

1.1冒泡排序

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;void bubbleSort(vector<int> &v)
{for (int i = 0; i < v.size() - 1; i++){for (int j = 0; j < v.size() - i - 1; j++){if (v[j] > v[j + 1]){swap(v[j], v[j + 1]);}}}
}int main()
{vector<int> v = {10, 8, 2, 3, 1, 6, 7, 5, 4, 9};bubbleSort(v);for (auto i : v){cout << i << endl;}system("pause");return 0;
}

void selectionSort(vector<int> &arr)
{int n = arr.size();int min_index; //最小值對應的index;for (int i = 0; i < arr.size(); i++){min_index = i; //默認最小值對應的起始索引是當前位置for (int j = i; j < arr.size(); j++){if (arr[j] < arr[min_index]){min_index = j;}}swap(arr[i], arr[min_index]);}
}

// 插入排序函數
void insertionSort(vector<int> &arr)
{int n = arr.size();for (int i = 1; i < n; ++i){int key = arr[i];int j = i - 1;// 將大于key的元素向后移動while (j >= 0 && arr[j] > key){arr[j + 1] = arr[j];j = j - 1;}// 插入key到正確的位置arr[j + 1] = key;}
}

2 常見高級排序算法

? ? ? ?2.1?希爾排序

2.1 算法描述

1959 年 Shell 發(fā)明，第?批突破 O(n2) 時間復雜度的排序算法，是簡單插?排序的改進版。它與插?排序的不同之處在于，它會優(yōu)先?較距離較遠的元素。希爾排序?叫縮?增 量排序

算法核?思想是先將整個待排序的記錄序列分割成為若??序列分別進?直接 插?排序 ，具體算法描述：

1.先根據數組的?度 /n ，獲取增量 K （第?次 n 為 2 ）

2.按增量序列個數 k 進?分組，?般可以分成 k 組；

3.根據以分好的組進?插?排序；（每組排序，根據對應的增量 k 來找到當前組的元素）

4.當每組都排序完畢之后，回到第?步將 n*2 再次分組進?插?排序，直到最終 k=1 的時候，在執(zhí)??次插?排序 完成最終的排序

void shellSort(vector<int> &arr)
{int n = arr.size();// 使用一組增量進行排序for (int gap = n / 2; gap > 0; gap /= 2){// 對每個增量進行插入排序for (int i = gap; i < n; i++){int temp = arr[i];int j;// 將元素插入到正確的位置for (j = i; j >= gap && arr[j - gap] > temp; j -= gap){arr[j] = arr[j - gap];}arr[j] = temp;}}
}

2.2 快速排序

具體描述如下 :

1 ，?先通過?較算法 , 找到基準數，?較過程通過交換，最終達到基準數左邊的數字都?較右邊的要?。分?在頭尾設置兩個指針，并且再將尾部元素作為?較基準。

移動 L 和 R 兩個指針，直到重合，然后交換基準數字

2 ，然后以基準數作為中軸，將數組分為兩部分，分?執(zhí)? 1 步驟的算法（可以通過遞

歸實現），直到?法再次分割排序完畢。

?? 遞歸

?個含直接或間接調?本函數語句的函數被稱之為遞歸函數，它必須滿?以下兩個條件：

1 ） 在每?次調???時，必須是（在某種意義上）更接近于解；

2 ） 必須有?個終?處理或計算的準則。

?算法實現

分解 1 ：創(chuàng)建左右兩個指針，將最后?個值作為基準值，通過不斷交換將數組分為兩部

分，左邊的?右邊的要?。

先判斷左指針和基準的值，如果?于等于就向后移動，直到遇到?基準值?的值

再判斷右邊指針和基準值，如果?于等于就向前移動，直到遇到?基準值?的值

然后交換左右指針的值。

循環(huán)上述操作，直到左右指針重合，然后交換重合值和基準值

// 根據基準元素將數組分成兩部分，并返回基準元素的索引
int partition(vector<int> &arr, int low, int high)
{int pivot = arr[high]; //選擇最后一個作為基準// 初始化較小元素的索引//遞歸里面的low 不一定是0開始的所以，寫成0 一定報錯int index = low;for (int j = low; j <= high - 1; j++){if (arr[j] <= pivot){swap(arr[j], arr[index]);index++;}}// 最后交換arr[i+1]和arr[high]，將基準元素放在正確的位置swap(arr[index], arr[high]);return index;
}void quickSort(vector<int> &arr, int low, int high)
{if (low < high) //[0,0 ]就不在判斷了。{// 獲取基準元素的索引int pivotIndex = partition(arr, low, high);// 對基準元素的左邊和右邊子數組進行遞歸排序quickSort(arr, low, pivotIndex - 1);quickSort(arr, pivotIndex + 1, high);}
}

2.3?歸并排序

1.歸并排序是利? 歸并 的思想實現的排序?法，該算法采?經典的 分治 策略即將問題 分 成?

些?的問題然后 遞歸 求解，? 治 的階段則將分的階段得到的各答案 " 修補 " 在?起，即分?

治之

2.

歸并排序是穩(wěn)定排序，它也是?種?分?效的排序，能利?完全?叉樹特性的排序?般性

能都不會太差。 java 中 Arrays.sort() 采?了?種名為 TimSort 的排序算法，就是歸并排序

的優(yōu)化版本。從上?的圖中可看出，每次合并操作的平均時間復雜度為 O(n) ，?完全?叉

樹的深度為 |log2n| ?？偟钠骄鶗r間復雜度為 O(nlogn) 。?且，歸并排序的最好，最壞，

平均時間復雜度均為 O(nlogn) 。

歸并排序核?思想是先分再治 , 具體算法描述如下 :

1.先將未排序數組 /2 進?分組 , 然后再將分好組的數組繼續(xù) /2 再次分組 , 直到?法分組 , 這

個就是分的過程 .

2.然后在將之后再把兩個數組??為 1 的合并成?個??為 2 的，再把兩個??為 2 的合

并成 4 的 , 同時在合并的過程中完成數組的排序 , 最終直到全部?的數組合并起來 , 這個

就是治的過程 .

? ? ? ?

治的過程中會為兩個數組設計兩個游標 , 和?個新的數組 .

????????分??較兩個游標指對應數組的元素, 將?的插?到新的數組中

????????然后向后移動較?的數組的游標, 繼續(xù)進??較 .

????????反復前?兩步, 最終將兩個數組中的元素排序合并到新的數組中

#include <iostream>
#include <vector>// 合并兩個已排序的子數組
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 創(chuàng)建臨時數組來存儲兩個子數組std::vector<int> leftArr(n1);std::vector<int> rightArr(n2);// 將數據復制到臨時數組中for (int i = 0; i < n1; i++) {leftArr[i] = arr[left + i];}for (int i = 0; i < n2; i++) {rightArr[i] = arr[mid + 1 + i];}// 合并兩個子數組int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}// 處理剩余的元素（如果有）while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[j];j++;k++;}
}// 歸并排序函數
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {// 找到數組中間點int mid = left + (right - left) / 2;// 遞歸排序左半部分和右半部分mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并已排序的兩個子數組merge(arr, left, mid, right);}
}int main() {std::vector<int> arr = {12, 11, 13, 5, 6, 7};std::cout << "原始數組: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;// 調用歸并排序函數mergeSort(arr, 0, arr.size() - 1);std::cout << "排序后數組: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}

2.4計數排序?

實現：

????????

#include <iostream>
#include <vector>void countingSort(std::vector<int>& arr) {int max_val = *std::max_element(arr.begin(), arr.end()); // 找到數組中的最大值int min_val = *std::min_element(arr.begin(), arr.end()); // 找到數組中的最小值int range = max_val - min_val + 1; // 計算數值范圍// 創(chuàng)建計數數組并初始化為0std::vector<int> count(range, 0);// 計算每個元素的出現次數for (int num : arr) {count[num - min_val]++;}// 根據計數數組，重建原始數組int index = 0;for (int i = 0; i < range; i++) {while (count[i] > 0) {arr[index] = i + min_val;index++;count[i]--;}}
}int main() {std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};std::cout << "原始數組: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;// 調用計數排序函數countingSort(arr);std::cout << "排序后數組: ";for (int num : arr) {std::cout << num << " ";}std::cout << std::endl;return 0;
}