柚子快報激活碼778899分享：【排序算法】選擇排序、堆排序

http://yzkb.51969.com/

文章目錄

選擇排序選擇排序的概念選擇排序的基本步驟：選擇排序的特點選擇排序的代碼實現（C語言）

選擇排序-優(yōu)化雙向選擇排序的步驟

堆堆的基本概念堆排序詳細步驟堆排序代碼講解

選擇排序

選擇排序的概念

選擇排序是一種簡單直觀的排序算法。它的工作原理是每次從未排序的部分中選擇一個最?。ɑ蜃畲螅┑脑兀⑵渑c未排序部分的第一個元素進行交換。這個過程重復 n-1 次，直到數組排序完畢。

選擇排序的基本步驟：

從未排序的部分中找到最小的元素。將這個元素與未排序部分的第一個元素交換。每次遍歷數組，未排序部分就會減少，已排序部分逐漸擴大。當所有元素都經過選擇排序后，數組就變?yōu)橛行虻摹?/p>

選擇排序的特點

時間復雜度: O(n2)，因為對于每個元素，都需要掃描剩下的未排序元素來找到最小值?？臻g復雜度: O(1)，因為它是原地排序算法，不需要額外的存儲空間。穩(wěn)定性: 選擇排序是不穩(wěn)定的排序算法。因為元素交換時，可能會改變相同值元素的相對順序。雖然很好理解，效率不好，實際中很少使用。

選擇排序的代碼實現（C語言）

#include

// 選擇排序函數

void SelectionSort(int arr[], int n) {

// 外層循環(huán)，逐漸縮小未排序部分

for (int i = 0; i < n - 1; i++) {

// 初始化最小值的索引為當前未排序部分的第一個元素

int minIndex = i;

//注意i

//但j是

// 內層循環(huán)，從 i+1 開始查找未排序部分的最小元素

for (int j = i + 1; j < n; j++) {

// 如果找到比當前最小值更小的元素，更新最小值索引

if (arr[j] < arr[minIndex]) {

minIndex = j;

}

}

// 如果最小值的索引不是 i，則交換元素

if (minIndex != i) {

int temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

}

}

// 打印數組函數

void PrintArray(int arr[], int n) {

for (int i = 0; i < n; i++) {

printf("%d ", arr[i]);

}

printf("\n");

}

int main() {

// 示例數組

int arr[] = {64, 25, 12, 22, 11};

int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前的數組: ");

PrintArray(arr, n);

// 執(zhí)行選擇排序

SelectionSort(arr, n);

printf("排序后的數組: ");

PrintArray(arr, n);

return 0;

}

輸出示例

排序前的數組: 64 25 12 22 11

排序后的數組: 11 12 22 25 64

詳細講解

外層循環(huán) for (int i = 0; i < n - 1; i++):

控制循環(huán)次數，每次選擇一個最小元素并將其放到正確位置。循環(huán)結束后，前 i 個元素已經排好序。 初始化最小值索引int minIndex = i;:

在每一輪選擇中，將當前未排序部分的第一個元素假設為最小元素。 內層循環(huán) for (int j = i + 1; j < n; j++):

通過從 i+1 開始的未排序部分中尋找最小值。如果發(fā)現比當前最小值更小的元素，更新 minIndex，標記該元素的索引。 元素交換 if (minIndex != i):

如果最小值不是當前元素，就交換最小值和未排序部分第一個元素。交換之后，已排序部分擴大一個元素。 PrintArray()** 函數**:

一個簡單的輔助函數，用于打印數組的當前狀態(tài)。

選擇排序的運行步驟舉例

假設排序數組 arr[] = {64, 25, 12, 22, 11}:

第1輪:

i = 0，未排序部分為 {64, 25, 12, 22, 11}。找到最小值 11，將其與 64 交換，數組變?yōu)?{11, 25, 12, 22, 64}。 第2輪:

i = 1，未排序部分為 {25, 12, 22, 64}。找到最小值 12，將其與 25 交換，數組變?yōu)?{11, 12, 25, 22, 64}。 第3輪:

i = 2，未排序部分為 {25, 22, 64}。找到最小值 22，將其與 25 交換，數組變?yōu)?{11, 12, 22, 25, 64}。 第4輪:

i = 3，未排序部分為 {25, 64}。最小值是 25，不需要交換，數組保持 {11, 12, 22, 25, 64}。

最后得到有序數組 {11, 12, 22, 25, 64}。

總結

選擇排序的核心思想就是每次從未排序的部分中選擇最小的元素，并把它放到正確的位置。雖然算法實現簡單，但它的時間復雜度為 O(n2)，效率較低，適用于小規(guī)模數組的排序問題。

選擇排序-優(yōu)化

雙向選擇排序或雙端選擇排序，這種方法通過同時從兩個方向進行選擇，以減少排序的時間復雜度。具體來說，它在每一輪中既選擇最小值也選擇最大值，并將它們放到數組的兩端。

雙向選擇排序的步驟

初始化：設置兩個指針，一個指向數組的開始位置（left），一個指向數組的結束位置（right）。選擇最小值和最大值：

遍歷當前的未排序部分，找到最小值和最大值。將最小值放到left指針指向的位置，將最大值放到right指針指向的位置。 更新指針：

將left指針向右移動一位（因為最小值已經放到正確的位置）。將right指針向左移動一位（因為最大值已經放到正確的位置）。 重復步驟2和3，直到left指針與right指針交叉或重疊。

雙向選擇排序的C語言實現

#include

// 函數用于交換兩個整數的值

void swap(int *x, int *y) {

int temp = *x;

*x = *y;

*y = temp;

}

// 雙向選擇排序函數

void biDirectionalSelectionSort(int arr[], int n) {

int left = 0; // 指向未排序部分的起始位置

int right = n - 1; // 指向未排序部分的結束位置

while (left < right) {

int minIndex = left; // 初始化最小值的索引

int maxIndex = right; // 初始化最大值的索引

// 遍歷未排序部分，找到最小值和最大值

for (int i = left; i <= right; i++) {

if (arr[i] < arr[minIndex]) {

minIndex = i;

}

if (arr[i] > arr[maxIndex]) {

maxIndex = i;

}

}

// 交換最小值到當前左邊界

swap(&arr[left], &arr[minIndex]);

// 如果最大值在左邊界位置，交換最大值到右邊界位置

if (maxIndex == left) {

maxIndex = minIndex; // 更新最大值的索引

}

// 交換最大值到當前右邊界

swap(&arr[right], &arr[maxIndex]);

// 更新邊界

left++;

right--;

}

}

// 輔助函數：打印數組元素

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {

printf("%d ", arr[i]);

}

printf("\n");

}

// 測試雙向選擇排序的主函數

int main() {

int arr[] = {64, 25, 12, 22, 11, 90};

int n = sizeof(arr) / sizeof(arr[0]);

printf("原始數組：\n");

printArray(arr, n);

biDirectionalSelectionSort(arr, n);

printf("排序后的數組：\n");

printArray(arr, n);

return 0;

}

swap函數：

用于交換兩個整數的值，以便在數組中重新排列元素。 biDirectionalSelectionSort函數：

初始化：left指針從數組的開始位置開始，right指針從數組的結束位置開始。找到最小值和最大值：

遍歷當前未排序的部分，記錄最小值和最大值的索引。 交換最小值和最大值：

將最小值交換到left位置。如果最大值在left位置（也就是最小值交換后，最大值可能在左邊），需要更新最大值的索引，然后將最大值交換到right位置。 更新邊界：

將left指針向右移動一位，將right指針向左移動一位，準備處理下一輪。 printArray函數：

用于打印數組中的元素，幫助觀察排序的結果。 main函數：

初始化一個數組，打印原始數組，調用biDirectionalSelectionSort函數進行排序，然后打印排序后的數組。

性能分析

時間復雜度：最壞情況下是O(n^2)，因為每一輪的遍歷操作都需要O(n)的時間，總共會執(zhí)行n/2輪?？臻g復雜度：O(1)，因為排序過程在原地完成，沒有使用額外的存儲空間。

雙向選擇排序通過同時選擇最小值和最大值來減少了需要排序的次數，從而比傳統(tǒng)的選擇排序略微優(yōu)化了性能。

堆

堆的基本概念

堆是一種特殊的完全二叉樹，滿足以下條件：

最大堆（Max-Heap）：在最大堆中，每個父節(jié)點的值都大于或等于其子節(jié)點的值。因此，堆頂（根節(jié)點）是最大值。最小堆（Min-Heap）：在最小堆中，每個父節(jié)點的值都小于或等于其子節(jié)點的值，因此堆頂是最小值。

堆是一個完全二叉樹，因此它可以用數組來高效地表示。對于任意節(jié)點i：

左子節(jié)點的索引是2 * i + 1右子節(jié)點的索引是2 * i + 2父節(jié)點的索引是(i - 1) / 2

堆排序詳細步驟

1. 構建最大堆 構建最大堆的過程是從最后一個非葉子節(jié)點開始，依次對每一個節(jié)點執(zhí)行“堆化”操作。堆化（Heapify）是一個過程，它將以某個節(jié)點為根的子樹調整為最大堆。

構建最大堆的過程：

從數組的最后一個非葉子節(jié)點開始（索引為n/2 - 1），向前逐步調整每個節(jié)點，保證每個子樹都是最大堆。

2. 排序過程

將堆頂（最大值）與堆的最后一個元素交換，堆的大小減1。重新調整堆（heapify），以確保剩下的部分仍然是最大堆。重復上述步驟，直到堆的大小減小到1。

代碼實現

#include

// 函數用于交換兩個整數的值

void swap(int *x, int *y) {

int temp = *x;

*x = *y;

*y = temp;

}

// 函數用于維護最大堆的性質

void heapify(int arr[], int n, int i) {

int largest = i; // 初始化最大值為當前節(jié)點

int left = 2 * i + 1; // 左子節(jié)點的索引

int right = 2 * i + 2; // 右子節(jié)點的索引

// 如果左子節(jié)點比根節(jié)點大，更新最大值的索引

if (left < n && arr[left] > arr[largest]) {

largest = left;

}

// 如果右子節(jié)點比當前最大值的節(jié)點還大，更新最大值的索引

if (right < n && arr[right] > arr[largest]) {

largest = right;

}

// 如果最大值不是根節(jié)點，交換節(jié)點并遞歸調整

if (largest != i) {

swap(&arr[i], &arr[largest]);

heapify(arr, n, largest); // 遞歸調整

}

}

// 主函數實現堆排序

void heapSort(int arr[], int n) {

// 構建最大堆

for (int i = n / 2 - 1; i >= 0; i--) {

heapify(arr, n, i);

}

// 一個一個取出元素進行排序

for (int i = n - 1; i >= 0; i--) {

// 當前最大值（根節(jié)點）與堆的最后一個元素交換

swap(&arr[0], &arr[i]);

// 重新調整堆，排除已排序的部分

heapify(arr, i, 0);

}

}

// 輔助函數：打印數組元素

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {

printf("%d ", arr[i]);

}

printf("\n");

}

// 測試堆排序的主函數

int main() {

int arr[] = {12, 11, 13, 5, 6, 7};

int n = sizeof(arr) / sizeof(arr[0]);

printf("原始數組：\n");

printArray(arr, n);

heapSort(arr, n);

printf("排序后的數組：\n");

printArray(arr, n);

return 0;

}

代碼逐步講解

swap函數：

交換兩個整數的值，用于調整堆中元素的位置。 heapify函數：

heapify用于維護最大堆的性質。它從節(jié)點i開始，調整以i為根的子樹，確保子樹符合最大堆的特性。largest變量用來追蹤當前子樹中的最大值索引。如果largest不是i，說明子樹不符合最大堆的特性，需要交換并遞歸調用heapify。 heapSort函數：

首先構建最大堆。for循環(huán)從最后一個非葉子節(jié)點開始，通過heapify將整個數組調整為最大堆。然后逐個取出堆頂元素（最大值）并將其與數組的最后一個元素交換，接著調整剩余部分，保持最大堆的性質。 printArray函數：

打印數組中的元素，幫助觀察排序的結果。 main函數：

初始化一個數組，打印原始數組，調用heapSort函數進行排序，然后打印排序后的數組。

希望這些詳細解釋和代碼示例能幫助你更好地理解堆排序。如果還有其他問題或需要更深入的解釋，請告訴我！

堆排序代碼講解

堆排序簡介

堆排序是一種基于堆（Heap）數據結構的排序算法。堆是一棵完全二叉樹，可以通過數組表示：

最大堆：每個節(jié)點的值都大于或等于其子節(jié)點的值。根節(jié)點是最大值。最小堆：每個節(jié)點的值都小于或等于其子節(jié)點的值。根節(jié)點是最小值。

堆排序的核心思想是：

首先將無序數組構建為一個最大堆。然后，將堆頂（即最大值）與數組的最后一個元素交換，縮小堆的范圍，對剩下的元素繼續(xù)調整成最大堆，直到排序完成。

1. `AdjustDown` 函數分析（向下調整）

該函數用于維護最大堆的性質。它從父節(jié)點開始，將其與子節(jié)點比較，并向下調整，使得父節(jié)點的值始終大于等于它的子節(jié)點。

void AdjustDown(int* a, int n, int parent)

{

int child = parent * 2 + 1; // 左孩子的索引

while (child < n) // 確保孩子節(jié)點存在

{

// 找出兩個孩子中較大的那個

if (child + 1 < n && a[child + 1] > a[child])

{

++child; // 右孩子比左孩子大，選擇右孩子

}

// 如果孩子的值大于父節(jié)點，則進行交換

if (a[child] > a[parent])

{

Swap(&a[child], &a[parent]); // 交換父節(jié)點和較大孩子

// 繼續(xù)向下調整，將孩子當作新的父節(jié)點

parent = child;

child = parent * 2 + 1; // 更新左孩子的索引

}

else

{

break; // 如果父節(jié)點已經大于等于孩子，則無需再調整

}

}

}

解釋：

child = parent * 2 + 1：左孩子節(jié)點的索引。因為堆是一棵完全二叉樹，所以對于索引為 parent 的節(jié)點，左孩子的索引為 2 * parent + 1，右孩子的索引為 2 * parent + 2。核心邏輯：找到較大的孩子（如果右孩子存在并且比左孩子大，則選擇右孩子），并與父節(jié)點進行比較，如果父節(jié)點比孩子小，則交換它們的值，并繼續(xù)向下調整。while 循環(huán)確保只要存在孩子節(jié)點，繼續(xù)調整，直到父節(jié)點大于等于孩子節(jié)點或到達樹的底部。

2. `HeapSort` 函數分析（堆排序的實現）

void HeapSort(int* a, int n)

{

// 建堆過程，從最后一個非葉子節(jié)點開始調整，逐步向上調整

for (int i = (n - 1 - 1) / 2; i >= 0; i--)

{

AdjustDown(a, n, i);

}

// 逐步將堆頂元素（最大值）與最后一個未排序元素交換

int end = n - 1;

while (end > 0)

{

Swap(&a[0], &a[end]); // 將堆頂元素與當前未排序部分的最后一個元素交換

AdjustDown(a, end, 0); // 重新調整堆，使剩余部分維持最大堆的性質

--end; // 排除最后一個已排序的元素

}

}

詳細講解：

建堆過程：

for (int i = (n - 1 - 1) / 2; i >= 0; i--)：

(n - 1 - 1) / 2 計算的是最后一個非葉子節(jié)點的索引。葉子節(jié)點不需要調整，所以從最后一個非葉子節(jié)點開始向上遍歷，逐一調整每個節(jié)點，以確保整個數組滿足最大堆的性質。調用 AdjustDown(a, n, i) 對從 i 開始的子樹進行調整，確保以 i 為根節(jié)點的子樹是一個最大堆。 排序過程：

Swap(&a[0], &a[end])：將當前堆的堆頂元素（最大值）與最后一個未排序的元素交換。AdjustDown(a, end, 0)：交換后，堆頂元素可能破壞了堆的性質，需要再次從堆頂（即索引 0）開始進行向下調整，恢復最大堆性質。--end：每次處理完一個最大元素后，end 減少1，表示縮小待排序區(qū)域，直到所有元素都排序完成。

示例：堆排序的執(zhí)行過程

假設我們有一個數組 [4, 10, 3, 5, 1]，我們將詳細分析堆排序的執(zhí)行過程。

建堆：

原數組為 [4, 10, 3, 5, 1]。從最后一個非葉子節(jié)點開始（i = 1，即 10）。

比較 10 與其孩子（5 和 1），10 已經大于它的孩子，不需要調整。 繼續(xù)處理 i = 0（4）。

比較 4 與其孩子（10 和 3），10 更大，交換 4 和 10。現在數組變?yōu)?[10, 4, 3, 5, 1]。繼續(xù)向下調整，4 與它的孩子 5 比較，交換 4 和 5，得到 [10, 5, 3, 4, 1]。 完成建堆后，最大堆為 [10, 5, 3, 4, 1]。 排序：

交換堆頂 10 和最后一個元素 1，得到 [1, 5, 3, 4, 10]。調整堆 [1, 5, 3, 4]，結果是 [5, 4, 3, 1, 10]。繼續(xù)交換堆頂 5 和 1，得到 [1, 4, 3, 5, 10]。調整堆 [1, 4, 3]，結果是 [4, 1, 3, 5, 10]。交換堆頂 4 和 3，得到 [3, 1, 4, 5, 10]，調整堆 [3, 1]，結果是 [3, 1, 4, 5, 10]。最后交換 3 和 1，得到 [1, 3, 4, 5, 10]。

時間復雜度

建堆的時間復雜度是 O(n)，因為每個節(jié)點調整的次數與其深度成正比，而總的深度是 log(n)。排序的時間復雜度是 O(n*log(n))，因為需要執(zhí)行 n 次堆調整，而每次堆調整的時間是 O(log(n))。

堆排序的特點

空間復雜度為 O(1)，因為堆排序是在原地排序，不需要額外的數組存儲空間。不穩(wěn)定性：堆排序是不穩(wěn)定的，因為元素在交換時可能破壞它們的相對順序。

通過這段代碼，整個堆排序的邏輯就清晰地展示了出來：先建堆，再逐步通過調整最大堆進行排序。

? [ 聲明 ] 由于作者水平有限，本文有錯誤和不準確之處在所難免， 本人也很想知道這些錯誤，懇望讀者批評指正！我是：勇敢滴勇~感謝大家的支持！

柚子快報激活碼778899分享：【排序算法】選擇排序、堆排序

http://yzkb.51969.com/

好文鏈接