數據結構第五節：排序

?1.常見的排序算法

插入排序：直接插入排序、希爾排序
選擇排序：直接選擇排序、堆排序
交換排序：冒泡排序、快速排序
歸并排序：歸并排序

排序的接口實現：

// 1. 直接插入排序
void InsertSort(int* a, int n);
// 2. 希爾排序
void ShellSort(int* a, int n);// 3. 直接選擇排序
void SelectSort(int* a, int n);
// 4. 堆排序
void HeapSort(int* a, int n);// 5.冒泡排序
void BubbleSort(int* a, int n);
// 6.快速排序
void QuickSort(int* a, int left, int right);// 7.歸并排序
void MergeSort(int* a, int n);

注意：以下排序的例子都是將數據進行從小到大的升序排序。

2.插入排序

2.1 直接插入排序（Insert Sort）

2.1.1?例子

初始數組： {12, 11, 13, 5, 6}?

排序過程：

輪次已排序區間未排序區間操作動作
初始[12][11,13,5,6]—
1[11,12][13,5,6]插入 11 → 移動 12
2[11,12,13][5,6]插入 13 → 無需移動
3[5,11,12,13][6]插入 5 → 移動 13,12,11
4[5,6,11,12,13][]插入 6 → 移動 13,12,11

2.1.2?算法步驟

  1. 初始化：假設第一個元素已經是已排序的序列。
  2. 遍歷未排序部分：從第二個元素開始，依次取出元素。
  3. 插入到正確位置：將當前元素與已排序序列從后向前比較，找到合適的插入位置，將其插入。
  4. 重復：直到所有元素都被插入到正確位置。

2.1.3 代碼

// 1. 直接插入排序(最壞的時間復雜度為o（n^2）)
void InsertSort(int* a, int n)
{// 在有序數組 a[0,end] 之間，插入 a[end+1]// 外層循環控制層數for (int i = 0; i < n - 1; i++){// 內層循環控制每一層內部的插入排序int end = i;int tmp = a[end + 1];while (end >= 0){// 當 a[end+1] 小于 a[end] 時，將 a[end] 后移if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}// 找到了本層中插入 a[end+1] 的位置，插入a[end+1]a[end + 1] = tmp;}
}

2.1.4?代碼關鍵點解析

外層循環：for (i=0; i < n-1; i++)

????????控制處理?a[i+1]?元素（從第2個到最后一個元素）。

內層循環：while (end >= 0)

????????從后向前比較，移動比?tmp?大的元素。

插入位置：a[end+1] = tmp

????????最終空出的位置即為?tmp?的插入點。

2.1.5?特點

特性說明
時間復雜度最好 O(n)，最壞 O(n2)
空間復雜度O(1)
穩定性穩定（相同元素順序不變）
適用場景小規模數據或基本有序的數據

2.2 希爾排序（Shell Sort）

希爾排序是插入排序的優化版本，通過分組插入排序逐步縮小間隔（gap），最終使數組基本有序，最后進行一次完整插入排序，提升效率。

2.2.1 例子

初始數組：{9, 5, 7, 3, 1, 6, 2, 4}

? ? ? ?0?1? 2?3?4?5?6?7?
排序過程（以?gap = 4 → 2 → 1?為例）：

Gap分組區間（下標）排序后子序列合并結果
4[0,4], [1,5], [2,6], [3,7][1,9], [5,6], [2,7], [3,4]1,5,2,3,9,6,7,4
2[0,2,4,6], [1,3,5,7][1,2,7,9], [3,4,5,6]1,3,2,4,7,5,9,6
1整體數組完全有序1,2,3,4,5,6,7,9

2.2.2 算法步驟

2.2.3 代碼

// 2. 希爾排序(時間復雜度為o（N^1.3-N^2）)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;// [0,end] 插入 end+gap [0, end+gap]有序  -- 間隔為gap的數據for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}
}

2.2.4 代碼關鍵點解析

  1. 動態調整?gap

    • gap = gap / 3 + 1?保證?gap?逐步縮小，最終為1（例如?n=8?時：8→3→2→1）。

    • 相比固定除以2，此方式更高效（經驗公式，時間復雜度接近 O(n^1.3)）。

  2. 分組插入排序邏輯

    • 外層循環：for (int i = 0; i < n - gap; i++)
      控制每組起始位置，遍歷所有子序列。

    • 內層循環：while (end >= 0)
      在間隔為?gap?的子序列中，將?tmp?插入到正確位置，元素后移由?end -= gap?實現。

  3. 邊界處理

    • i < n - gap?確保?a[end + gap]?不越界。

    • end >= 0?防止訪問負下標。

2.2.5 特點

特性說明
時間復雜度平均 O(n^1.3) ~ 最壞 O(n2)
空間復雜度O(1)（原地排序）
穩定性不穩定（分組可能破壞相同元素順序）
適用場景中等規模數據，對插入排序的優化場景

3.選擇排序

3.1 直接選擇排序（Selection Sort）

直接選擇排序通過每次從未排序區間中選出最小和最大元素，分別放置到已排序區間的首尾，逐步縮小未排序范圍，直到完全有序。
特點：簡單但效率較低（時間復雜度 O(n2)），適合小規模數據。

3.1.1 例子

以數組?[5, 2, 9, 3, 6, 1, 8, 7]?為例，排序過程如下：

輪次操作步驟數組變化說明
初始未排序區間?[0,7]5,2,9,3,6,1,8,7初始狀態
1找到?min=1（索引5），max=9（索引2）

1,2,5,3,6,9,8,7?

→?1,2,5,3,6,7,8,9

min?交換到?begin=0，max?交換到?end=7
2未排序區間?[1,6]，找到?min=2，max=8

1,2,5,3,6,7,8,9?

→?1,2,5,3,6,7,8,9

無需交換（已有序）
3未排序區間?[2,5]，找到?min=3，max=6

1,2,3,5,6,7,8,9?

→?1,2,3,5,6,7,8,9

min=3?交換到?begin=2
4未排序區間?[3,4]，找到?min=5，max=6

1,2,3,5,6,7,8,9?

→?1,2,3,5,6,7,8,9

完成排序

3.1.2 算法步驟

  1. 初始化區間：

    begin=0，end=n-1，表示當前未排序的區間。

  2. 遍歷找極值：

    在?[begin, end]?區間內找到最小值?mini?和最大值?maxi。

  3. 交換元素：

    將?a[mini]?與?a[begin]?交換，將?a[maxi]?與?a[end]?交換。

  4. 修正?maxi：

    若?maxi == begin，說明最大值被交換到了?mini?的位置，需更新?maxi = mini。

  5. 縮小區間：

    begin++，end--，重復直到?begin >= end。

3.1.3 代碼

// 3. 直接選擇排序(時間復雜度為o（n^2）)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){// 選出最小的放在 begin// 選出最大的放在 endint mini = begin;int maxi = end;for (int i = begin; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);// 修正一下maxiif (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);begin++;end--;}
}

3.1.4 代碼關鍵點解析

  1. 同時找最小和最大值：

    通過一次遍歷找到?mini?和?maxi，減少遍歷次數（傳統選擇排序需兩次遍歷）。

  2. 修正?maxi?的邏輯：

    若?maxi == begin，在交換?a[begin]?和?a[mini]?后，原最大值已被移動到?mini?的位置，需更新?maxi。示例：初始數組?[9, 1, 5]，第一次交換后?maxi?需要從?0?修正到?1。

  3. 邊界處理：

    while (begin < end)?確保區間有效，避免重復交換。

3.1.5 特點

特性說明
時間復雜度O(n2)（無論數據是否有序）
空間復雜度O(1)（原地排序）
穩定性不穩定（交換可能破壞相同元素順序）
適用場景小規模數據，或對穩定性無要求的場景

3.2 堆排序（Heap Sort）

堆排序是一種基于二叉堆數據結構的排序算法，通過構建大頂堆（升序）或小頂堆（降序），逐步將堆頂元素（極值）交換到數組末尾并調整堆，最終完成排序。

3.2.1 例子

初始數組：[4, 10, 3, 5, 1]
排序過程：

建堆階段（構建大堆）

// 初始完全二叉樹：4  /   \  10    3  /  \  
5    1// 向下調整后的堆10  /   \  5     3  /  \  
4    1

排序階段

// 交換對頂的10 與最后一個數 1  ，重新調整1/   \  5     3  /  \  
4    10

3.2.2 算法步驟

  1. 建堆：

    從最后一個非葉子節點開始，自底向上調用?AdjustDown，構建大頂堆。

  2. 排序：

    將堆頂元素（最大值）與末尾元素交換，縮小堆范圍。

    對剩余堆調用?AdjustDown?調整，重復直到完全有序。

3.2.3 代碼

// 4. 堆排序(排升序建大堆)
void AdjustDown(int* a, int n, int root)
{int parent = root;int maxChild = parent * 2 + 1; // 初始化最大的孩子為左孩子while (maxChild < n){// 選出左右孩子中最大的if ( n > maxChild + 1  && a[maxChild + 1] > a[maxChild] ){maxChild++;}if (a[maxChild] > a[parent]){Swap(&a[maxChild], &a[parent]);parent = maxChild;maxChild = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 思路：選擇排序，依次選數，從后往前排// 升序 -- 大堆// 降序 -- 小堆// 建堆 -- 向下調整建堆 - O(N)// 從最后一個葉子結點開始for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// 選數 N*logNint i = 1;while (i < n){// 將建好的大堆的第一個數（堆中最大的數）與最后一個數交換位置Swap(&a[0], &a[n - i]);// 將交換位置后的新堆重新建大堆AdjustDown(a, n - i, 0);++i;}
}

3.2.4 代碼關鍵點解析

  1. AdjustDown 函數

    • 參數：a?是待調整數組，n?是堆大小，root?是當前調整的父節點索引。

    • 邏輯：

      • 通過?maxChild?標記較大的子節點，若右孩子存在且更大，則更新?maxChild。

      • 若子節點大于父節點，交換并繼續向下調整；否則終止循環。

      • maxChild + 1 < n，確保右孩子不越界。

  2. HeapSort 函數

    • 建堆：

      ? ? ?從最后一個非葉子節點?(n-2)/2?開始調整（因為葉子節點無需調整）。

    • 排序：

      • 每次交換堆頂?a[0]?與當前末尾?a[n-i]，縮小堆范圍至?n-i。

      • 對剩余堆重新調整，保持大頂堆性質。

3.2.5 特點

特性說明
時間復雜度建堆 O(n)，排序 O(n log n)，總體 O(n log n)
空間復雜度O(1)（原地排序）
穩定性不穩定（交換可能破壞相同元素順序）
適用場景大規模數據，對穩定性無要求的場景

4.交換排序

4.1 冒泡排序（Bubble Sort）

冒泡排序通過重復遍歷數組，依次比較相鄰元素并交換逆序對，使較大元素逐步“浮”到數組末尾。每輪遍歷會確定一個最大值的最終位置，直到數組完全有序。

4.1.1 例子

初始數組：[5, 3, 8, 6, 2]
排序過程：

輪次操作步驟數組變化說明
1遍歷比較并交換逆序對3,5,6,2,8確定最大值?8?的位置
2遍歷剩余未排序部分3,5,2,6,8確定次大值?6?的位置
3繼續遍歷未排序部分3,2,5,6,8確定?5?的位置
4最后一次遍歷2,3,5,6,8完成排序

4.1.2 算法步驟

  1. 外層循環控制輪次：

    共需?n-1?輪，每輪確定一個當前未排序部分的最大值。

  2. 內層循環比較相鄰元素：

    在每輪中，從索引?0?到?n-i-1?比較相鄰元素，若逆序則交換。

  3. 優化：提前終止：

    若某輪未發生交換，說明數組已有序，直接結束排序。

4.1.3 代碼

// 5.冒泡排序(o（N-N^2）)
void BubbleSort(int* a, int n)
{// 控制循環層數for (int i = 0; i < n - 1; i++){// 控制每層循環比較int exchange = 0;for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);exchange = 1;}}if (exchange == 0){break;}}
}

4.1.4 代碼關鍵點解析

  1. 外層循環條件：

    i < n - 1：最多需要?n-1?輪遍歷（如?5?個元素需?4?輪）。

  2. 內層循環范圍：

    j < n - i：每輪遍歷的未排序部分為?[0, n-i-1]，已排序部分無需處理。

  3. 優化邏輯：

    exchange?標記：若某輪無交換，說明數組已有序，直接退出外層循環。

  4. 穩定性：

    相等元素不會交換，因此排序是穩定的。

4.1.5 特點

特性說明
時間復雜度最好 O(n)，最壞/平均 O(n2)
空間復雜度O(1)（原地排序）
穩定性穩定（相同元素順序不變）
適用場景小規模數據或基本有序的數據

4.2 快速排序（Quick Sort）

快速排序是一種基于分治思想的高效排序算法，通過選定基準元素將數組劃分為左右兩部分，遞歸排序子數組，最終合并成有序序列。優化后的快速排序通常采用三數取中法選擇基準，避免最壞時間復雜度。

4.2.1 例子

初始數組：[6, 1, 3, 9, 8, 5, 2, 7]
排序過程（以三數取中法選基準為例）：

初始數組: [6,1,3,9,8,5,2,7]  ↓ 三數取中選基準7  分區后: [5,1,3,2,7,8,9,6]  |←左遞歸→| |←右遞歸→|  左遞歸: [5,1,3,2] → 選基準3 → [2,1,3,5]  
右遞歸: [8,9,6]   → 選基準8 → [6,8,9]  最終結果: [1,2,3,5,6,7,8,9]

4.2.2 算法步驟

  1. 三數取中法選基準：

    • 從?left、mid=(left+right)/2、right?中選擇中間值的索引作為基準。

  2. 分區操作：

    • 將基準交換到?left?位置，定義雙指針?begin=left、end=right。

    • 右指針左移：找到第一個小于基準的元素。

    • 左指針右移：找到第一個大于基準的元素。

    • 交換左右指針元素，直到兩指針相遇，將基準交換到相遇點。

  3. 遞歸排序：

    • 對基準左右子數組遞歸調用快速排序。

4.2.3 代碼

// 6.快速排序// 三數取中法選擇基準索引
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]) {if (a[mid] < a[right]) return mid;else return (a[left] > a[right]) ? left : right;}else {if (a[mid] > a[right]) return mid;else return (a[left] < a[right]) ? left : right;}
}// 分區函數
int PartQSort(int* a, int left, int right) 
{assert(a);// 三數取中法選基準，并交換到 left 位置int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[mid]); // 基準置于 leftint key = a[left];int begin = left, end = right;while (begin < end) {// 右指針找小while (begin < end && a[end] >= key) end--;// 左指針找大while (begin < end && a[begin] <= key) begin++;Swap(&a[begin], &a[end]);}Swap(&a[left], &a[begin]); // 基準歸位return begin;
}// 快速排序主函數
void QuickSort(int* a, int left, int right) 
{if (left >= right) return;int div = PartQSort(a, left, right);QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);
}

4.2.4 代碼關鍵點解析

  1. 三數取中法優化：

    • GetMidIndex?選擇?left、mid、right?中的中間值索引，避免極端分布（如完全逆序）導致 O(n2) 時間復雜度。

  2. 分區邏輯：

    • 將基準值交換到?left?位置，確保雙指針移動邏輯正確。
    • 循環結束后將基準值交換到?begin?位置。

  3. 雙指針移動條件：

    • 右指針先走：確保相遇點的值小于等于基準值，避免最后交換時錯誤。

    • 嚴格比較條件：a[end] >= key?和?a[begin] <= key?保證相等元素均勻分布。

4.2.5 特點

特性說明
時間復雜度平均 O(n log n)，最壞 O(n2)（可優化）
空間復雜度O(log n)（遞歸棧深度）
穩定性不穩定（交換可能破壞順序）
適用場景大規模數據，對緩存友好的場景

5. 歸并排序（Merge Sort）

歸并排序是一種基于分治思想的穩定排序算法，通過遞歸將數組分割為最小單元（單個元素），再兩兩合并有序子數組，最終得到完全有序的數組。

5.1 例子

初始數組：[8, 3, 5, 2, 7, 1]
排序過程：

  1. 分割階段：

    [8,3,5,2,7,1]  
→ [8,3,5] 和 [2,7,1]  
→ [8], [3,5], [2], [7,1]  
→ [8], [3], [5], [2], [7], [1]

  2. 合并階段：

    [3,8] ←合并 [8] 和 [3]  
[3,5,8] ←合并 [3,8] 和 [5]  
[1,7] ←合并 [7] 和 [1]  
[1,2,7] ←合并 [2] 和 [1,7]  
→ 最終合并 [3,5,8] 和 [1,2,7] → [1,2,3,5,7,8]

5.2 算法步驟

  1. 分割：

    • 遞歸將數組從中間位置（mid = (begin+end)/2）分割為左右子數組，直到每個子數組長度為1。

  2. 合并：

    • 創建臨時數組?tmp，依次比較左右子數組的元素，將較小者放入?tmp。

    • 將剩余未遍歷的元素直接追加到?tmp。

    • 將?tmp?中的數據拷貝回原數組的對應區間。

5.3 代碼

// 7.歸并排序// 遞歸分割與合并
void _MergeSort(int* a, int begin, int end, int* tmp) {if (begin >= end) return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);     // 遞歸左半部分_MergeSort(a, mid + 1, end, tmp);   // 遞歸右半部分// 合并左右子數組int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] <= a[begin2]) tmp[i++] = a[begin1++];else tmp[i++] = a[begin2++];}// 處理剩余元素while (begin1 <= end1) tmp[i++] = a[begin1++];while (begin2 <= end2) tmp[i++] = a[begin2++];// 拷貝回原數組for (i = begin; i <= end; i++) a[i] = tmp[i];
}// 入口函數
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

5.4 代碼關鍵點解析

  1. 遞歸分割：

    • 通過?mid = (begin + end) / 2?將數組分為?[begin, mid]?和?[mid+1, end]。

    • 遞歸終止條件?begin >= end?確保子數組長度為1時停止分割。

  2. 合并邏輯：

    • 雙指針遍歷：begin1?和?begin2?分別指向左右子數組的起始位置，選擇較小值放入?tmp。

    • 處理剩余元素：若左或右子數組有剩余元素，直接追加到?tmp。

    • 數據拷貝：將?tmp?中合并后的數據寫回原數組的?[begin, end]?區間。

  3. 穩定性：

    • 合并時判斷?a[begin1] <= a[begin2]，保留相等元素的原始順序。

5.5 特點

特性說明
時間復雜度O(n log n)（所有情況）
空間復雜度O(n)（需額外臨時數組）
穩定性穩定（合并時保留相同元素順序）
適用場景大規模數據、需穩定性的場景

6.完整代碼

6.1 Sort.h

#pragma once
#define _CRT_SECURE_NO_WARNING
/*排升序*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>// 插入排序：直接插入排序、希爾排序
// 選擇排序：直接選擇排序、堆排序
// 交換排序：冒泡排序、快速排序
// 歸并排序：歸并排序// 1. 直接插入排序
void InsertSort(int* a, int n);
// 2. 希爾排序
void ShellSort(int* a, int n);// 3. 直接選擇排序
void SelectSort(int* a, int n);
// 4. 堆排序
void HeapSort(int* a, int n);// 5.冒泡排序
void BubbleSort(int* a, int n);
// 6.快速排序
void QuickSort(int* a, int left, int right);// 7.歸并排序
void MergeSort(int* a, int n);

6.2?Sort.c

#include "Sort.h"// 1. 直接插入排序(最壞的時間復雜度為o（n^2）)
void InsertSort(int* a, int n) 
{for (int i = 0; i < n - 1; i++) {      // 外層循環：處理 a[1] 到 a[n-1]int end = i;                        // 已排序部分的末尾索引int tmp = a[end + 1];               // 當前待插入元素while (end >= 0) {                  // 內層循環：從后向前比較if (a[end] > tmp) {             // 若前一個元素更大，后移a[end + 1] = a[end];end--;}else break;}a[end + 1] = tmp;                   // 插入到正確位置}
}// 2. 希爾排序(時間復雜度為o（N^1.3-N^2）)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1) {gap = gap / 3 + 1;  // 動態調整間隔for (int i = 0; i < n - gap; i++) {int end = i;int tmp = a[end + gap];// 間隔為gap的插入排序while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else break;}a[end + gap] = tmp;}}
}// 3. 直接選擇排序(時間復雜度為o（n^2）)
void Swap(int* p1, int* p2) 
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n) 
{int begin = 0, end = n - 1;while (begin < end) {int mini = begin, maxi = end;for (int i = begin; i <= end; i++) {if (a[i] < a[mini]) mini = i;  // 找最小值if (a[i] > a[maxi]) maxi = i;  // 找最大值}Swap(&a[begin], &a[mini]);         // 交換最小值到頭部if (maxi == begin) maxi = mini;    // 修正最大值位置Swap(&a[end], &a[maxi]);           // 交換最大值到尾部begin++;end--;}
}// 4. 堆排序(排升序建大堆)
// 向下調整（大堆）
void AdjustDown(int* a, int n, int root) 
{int parent = root;int maxChild = parent * 2 + 1; // 初始為左孩子while (maxChild < n) {// 選出左右孩子中較大的（需確保右孩子存在）if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) {maxChild++;}if (a[maxChild] > a[parent]) {Swap(&a[maxChild], &a[parent]);parent = maxChild;maxChild = parent * 2 + 1;}else {break;}}
}// 堆排序
void HeapSort(int* a, int n) 
{// 建堆：從最后一個非葉子節點開始調整for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDown(a, n, i);}// 排序：交換堆頂與末尾元素并調整堆int i = 1;while (i < n) {Swap(&a[0], &a[n - i]);AdjustDown(a, n - i, 0);++i;}
}// 5.冒泡排序(o（N-N^2）)
void BubbleSort(int* a, int n) 
{for (int i = 0; i < n - 1; i++) {    // 控制遍歷輪次int exchange = 0;                // 標記是否發生交換for (int j = 1; j < n - i; j++) { // 遍歷未排序部分if (a[j - 1] > a[j]) {       // 比較相鄰元素Swap(&a[j - 1], &a[j]);exchange = 1;            // 標記有交換}}if (exchange == 0) break;        // 未交換則提前終止}
}// 6.快速排序// 三數取中法選擇基準索引
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]) {if (a[mid] < a[right]) return mid;else return (a[left] > a[right]) ? left : right;}else {if (a[mid] > a[right]) return mid;else return (a[left] < a[right]) ? left : right;}
}// 分區函數
int PartQSort(int* a, int left, int right) 
{assert(a);// 三數取中法選基準，并交換到 left 位置int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[mid]); // 基準置于 leftint key = a[left];int begin = left, end = right;while (begin < end) {// 右指針找小while (begin < end && a[end] >= key) end--;// 左指針找大while (begin < end && a[begin] <= key) begin++;Swap(&a[begin], &a[end]);}Swap(&a[left], &a[begin]); // 基準歸位return begin;
}// 快速排序主函數
void QuickSort(int* a, int left, int right) 
{if (left >= right) return;int div = PartQSort(a, left, right);QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);
}// 7.歸并排序// 遞歸分割與合并
void _MergeSort(int* a, int begin, int end, int* tmp) {if (begin >= end) return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);     // 遞歸左半部分_MergeSort(a, mid + 1, end, tmp);   // 遞歸右半部分// 合并左右子數組int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] <= a[begin2]) tmp[i++] = a[begin1++];else tmp[i++] = a[begin2++];}// 處理剩余元素while (begin1 <= end1) tmp[i++] = a[begin1++];while (begin2 <= end2) tmp[i++] = a[begin2++];// 拷貝回原數組for (i = begin; i <= end; i++) a[i] = tmp[i];
}// 入口函數
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

6.3?Test.c

6.3.1?直接插入排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};InsertSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.2 希爾排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,0};ShellSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

?6.3.3 直接選擇排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};SelectSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.4?堆排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,0};HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.5 冒泡排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};BubbleSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.6?快速排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};QuickSort(a, 0, sizeof(a) / sizeof(int) - 1); // 這里的減一是因為傳參的是數組的下標for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.7?歸并排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};MergeSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/71341.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/71341.shtml
英文地址，請注明出處：http://en.pswp.cn/web/71341.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

BambuStudio學習筆記：FaceDetector類

BambuStudio學習筆記：FaceDetector類

面檢測器類解析 這段代碼定義了一個名為 FaceDetector 的 C 類&#xff0c;用于處理三維模型中的面檢測。以下是該類的具體說明&#xff1a; 頭文件保護 #ifndef slic3r_FaceDetector_hpp_ #define slic3r_FaceDetector_hpp_這部分代碼防止頭文件被多次包含。 命名空間聲明…
閱讀更多...
C++發展

C++發展

目錄 ?編輯C 的發展總結&#xff1a;?編輯 1. C 的早期發展&#xff08;1979-1985&#xff09; 2. C 標準化過程&#xff08;1985-1998&#xff09; 3. C 標準演化&#xff08;2003-2011&#xff09; 4. C11&#xff08;2011年&#xff09; 5. C14&#xff08;2014年&a…
閱讀更多...
LeetCode 21. 合并兩個有序鏈表(Python)

LeetCode 21. 合并兩個有序鏈表(Python)

將兩個升序鏈表合并為一個新的 升序 鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。 輸入&#xff1a;l1 [1,2,4], l2 [1,3,4] 輸出&#xff1a;[1,1,2,3,4,4] 示例 2&#xff1a; 輸入&#xff1a;l1 [], l2 [] 輸出&#xff1a;[] 示例 3&#xff1a; 輸…
閱讀更多...
FPGA 配置原理

FPGA 配置原理

用戶編程控制的FPGA 是通過加載比特位流配置內部的存儲單元實現的。該存儲單元就是所謂的配置單元&#xff0c;它必須在器件上電后進行配置&#xff0c;從而設置查找表&#xff08;LUT&#xff09;的屬性、連線方式、IOB 電壓標準和其它的用戶設計。 1.配置幀 以Xilinx 公司的…
閱讀更多...
測試人員如何更好的跟蹤BUG

測試人員如何更好的跟蹤BUG

軟件測試中BUG跟蹤是確保軟件質量的關鍵環節。測試人員不僅需要發現BUG&#xff0c;還需有效管理其狀態&#xff0c;從報告到修復驗證的全過程。如何更好地跟蹤BUG&#xff0c;成為測試人員提升效率的重要課題。本文將詳細探討測試人員可以采用的策略&#xff0c;包括使用工具、…
閱讀更多...
lamp平臺介紹

lamp平臺介紹

一、lamp介紹 網站&#xff1a; 靜態 動態 php語言 .php 作用&#xff1a;運行php語言編寫動態網站應用 lamp Linux Apache MySQL PHP PHP是作為httpd的一個功能模塊存在的 二、部署lamp平臺 1、測試httpd是否可正常返回PHP的響應 2、測試PHP代碼是否可正常連接數據…
閱讀更多...
2025年滲透測試面試題總結-字某跳動-滲透測試實習生（題目+回答）

2025年滲透測試面試題總結-字某跳動-滲透測試實習生（題目+回答）

網絡安全領域各種資源&#xff0c;學習文檔&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各種好玩的項目及好用的工具&#xff0c;歡迎關注。 字某跳動-滲透測試實習生 滲透流程信息收集如何處理子域名爆破中的泛解析問題繞過CDN尋找真實IPPHPINFO頁面關注…
閱讀更多...
Spring Boot 自動裝配深度解析與實踐指南

Spring Boot 自動裝配深度解析與實踐指南

目錄 引言&#xff1a;自動裝配如何重塑Java應用開發&#xff1f; 一、自動裝配核心機制 1.1 自動裝配三大要素 1.2 自動裝配流程 二、自定義自動配置實現 2.1 創建自動配置類 2.2 配置屬性綁定 2.3 注冊自動配置 三、條件注解深度應用 3.1 常用條件注解對比 3.2 自定…
閱讀更多...
《算法筆記》9.6小節 數據結構專題(2)并查集 問題 C: How Many Tables

《算法筆記》9.6小節 數據結構專題(2)并查集 問題 C: How Many Tables

題目描述 Today is Ignatius birthday. He invites a lot of friends. Now its dinner time. Ignatius wants to know how many tables he needs at least. You have to notice that not all the friends know each other, and all the friends do not want to stay with stra…
閱讀更多...
CPU、SOC、MPU、MCU--詳細分析四者的區別

CPU、SOC、MPU、MCU--詳細分析四者的區別

一、CPU 與SOC的區別 1.CPU 對于電腦&#xff0c;我們經常提到&#xff0c;處理器&#xff0c;內存&#xff0c;顯卡&#xff0c;硬盤四大部分可以組成一個基本的電腦。其中的處理器——Central Processing Unit&#xff08;中央處理器&#xff09;。CPU是一臺計算機的運算核…
閱讀更多...
Linux常用指令學習筆記

Linux常用指令學習筆記

文章目錄 前言一、文件和目錄操作指令1. 文件操作2. 目錄操作 二、文件權限管理三、網絡相關指令四、系統管理指令五、文本編輯器基本操作 六、壓縮和解壓指令七、總結 前言 在當今的IT領域&#xff0c;Linux系統因其開源、穩定、安全等特性&#xff0c;廣泛應用于服務器、個人…
閱讀更多...
android studio通過 jni 調用第三方非標準 so庫

android studio通過 jni 調用第三方非標準 so庫

調用第三方的so方法&#xff0c;但這個so內的方法不是標準的jni方法。這就需要我們自己寫jni然后鏈接到第三方so庫&#xff0c;通過jni調用so庫中的方法。 1.簡述&#xff1a; 要先有第三方的so庫.so文件和編譯庫對應的.h頭文件 我們自己用 c/c 創建一個標準的so 庫,比如 my…
閱讀更多...
Spring（三）容器-注入

Spring（三）容器-注入

一 自動注入Autowire 代碼實現&#xff1a; package org.example.spring01.service;import org.springframework.stereotype.Service;Service public class UserService {}package org.example.spring01.controller;import lombok.Data; import lombok.ToString; import org.…
閱讀更多...
mac上最好的Python開發環境之Anaconda+Pycharm

mac上最好的Python開發環境之Anaconda+Pycharm

為了運行修改 label-studio項目源碼&#xff0c;又不想在windows上運行&#xff0c;便在mac上開始安裝&#xff0c;開始使用poetry安裝&#xff0c;各種報錯&#xff0c;不是zip包解壓不了&#xff0c;就是numpy編譯報錯&#xff0c;pipy.org訪問出錯。最后使用anaconda成功啟動…
閱讀更多...
IDEA 接入 Deepseek

IDEA 接入 Deepseek

在本篇文章中&#xff0c;我們將詳細介紹如何在 JetBrains IDEA 中使用 Continue 插件接入 DeepSeek&#xff0c;讓你的 AI 編程助手更智能&#xff0c;提高開發效率。 一、前置準備 在開始之前&#xff0c;請確保你已經具備以下條件&#xff1a; 安裝了 JetBrains IDEA&…
閱讀更多...
前綴和矩陣

前綴和矩陣

前綴和矩陣&#xff08;Prefix Sum Matrix&#xff09;是一種預處理技術&#xff0c;用于快速計算二維矩陣中任意子矩陣的元素和。其核心思想是通過提前計算并存儲每個位置左上角所有元素的和&#xff0c;將子矩陣和的查詢時間從暴力計算的 (O(mn)) 優化到 (O(1))。以下是構建前…
閱讀更多...
系統架構評估中的重要概念

系統架構評估中的重要概念

(1)敏感點(Sensitivity Point) 和權衡點 (Tradeoff Point)。敏感點和權衡點是關鍵的架構 決策。敏感點是一個或多個構件(和/或構件之間的關系)的特性。研究敏感點可使設計人員 或分析員明確在搞清楚如何實現質量目標時應注意什么。權衡點是影響多個質量屬性的特性&#xff0c; …
閱讀更多...
SSL證書和HTTPS：全面解析它們的功能與重要性

SSL證書和HTTPS：全面解析它們的功能與重要性

每當我們在互聯網上輸入個人信息、進行在線交易時&#xff0c;背后是否有一個安全的保障&#xff1f;這時&#xff0c;SSL證書和HTTPS便扮演了至關重要的角色。本文將全面分析SSL證書和HTTPS的含義、功能、重要性以及它們在網絡安全中的作用。 一、SSL證書的定義與基本概念 S…
閱讀更多...
基于微信小程序的停車場管理系統的設計與實現

基于微信小程序的停車場管理系統的設計與實現

第1章 緒論 1.1 課題背景 隨著移動互聯形式的不斷發展&#xff0c;各行各業都在摸索移動互聯對本行業的改變&#xff0c;不斷的嘗試開發出適合于本行業或者本公司的APP。但是這樣一來用戶的手機上就需要安裝各種軟件&#xff0c;但是APP作為一個只為某個公司服務的一個軟件&a…
閱讀更多...
寶塔找不到php擴展swoole，服務器編譯安裝

寶塔找不到php擴展swoole，服務器編譯安裝

1. 在php7.4中安裝swoole&#xff0c;但找不到這個擴展安裝 2. 服務器下載源碼解壓安裝 http://pecl.php.net/package/swoole 下載4.8.0版本 解壓到/www/server/php/74/下 3. 發現報錯問題&#xff1b; 更新一下依賴 yum update yum -y install gcc gcc-c autoconf libjpe…
閱讀更多...
最新文章

Copyright @ 2022~2023