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

http://yzkb.51969.com/

文章目錄

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

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

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

選擇排序

選擇排序的概念

選擇排序是一種簡單直觀的排序算法。它的工作原理是每次從未排序的部分中選擇一個最小（或最大）的元素，并將其與未排序部分的第一個元素進(jìn)行交換。這個過程重復(fù) n-1 次，直到數(shù)組排序完畢。

選擇排序的基本步驟：

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

選擇排序的特點

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

選擇排序的代碼實現(xiàn)（C語言）

#include

// 選擇排序函數(shù)

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

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

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

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

int minIndex = i;

//注意i

//但j是

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

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

// 如果找到比當(dāng)前最小值更小的元素，更新最小值索引

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

minIndex = j;

}

}

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

if (minIndex != i) {

int temp = arr[i];

arr[i] = arr[minIndex];

arr[minIndex] = temp;

}

}

}

// 打印數(shù)組函數(shù)

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

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

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

}

printf("\n");

}

int main() {

// 示例數(shù)組

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

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

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

PrintArray(arr, n);

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

SelectionSort(arr, n);

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

PrintArray(arr, n);

return 0;

}

輸出示例

排序前的數(shù)組: 64 25 12 22 11

排序后的數(shù)組: 11 12 22 25 64

詳細(xì)講解

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

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

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

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

如果最小值不是當(dāng)前元素，就交換最小值和未排序部分第一個元素。交換之后，已排序部分?jǐn)U大一個元素。 PrintArray()** 函數(shù)**:

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

選擇排序的運(yùn)行步驟舉例

假設(shè)排序數(shù)組 arr[] = {64, 25, 12, 22, 11}:

第1輪:

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

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

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

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

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

總結(jié)

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

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

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

雙向選擇排序的步驟

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

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

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

雙向選擇排序的C語言實現(xiàn)

#include

// 函數(shù)用于交換兩個整數(shù)的值

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

int temp = *x;

*x = *y;

*y = temp;

}

// 雙向選擇排序函數(shù)

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

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

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

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;

}

}

// 交換最小值到當(dāng)前左邊界

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

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

if (maxIndex == left) {

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

}

// 交換最大值到當(dāng)前右邊界

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

// 更新邊界

left++;

right--;

}

}

// 輔助函數(shù)：打印數(shù)組元素

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

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

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

}

printf("\n");

}

// 測試雙向選擇排序的主函數(shù)

int main() {

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

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

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

printArray(arr, n);

biDirectionalSelectionSort(arr, n);

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

printArray(arr, n);

return 0;

}

swap函數(shù)：

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

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

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

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

將left指針向右移動一位，將right指針向左移動一位，準(zhǔn)備處理下一輪。 printArray函數(shù)：

用于打印數(shù)組中的元素，幫助觀察排序的結(jié)果。 main函數(shù)：

初始化一個數(shù)組，打印原始數(shù)組，調(diào)用biDirectionalSelectionSort函數(shù)進(jìn)行排序，然后打印排序后的數(shù)組。

性能分析

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

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

堆

堆的基本概念

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

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

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

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

堆排序詳細(xì)步驟

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

構(gòu)建最大堆的過程：

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

2. 排序過程

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

代碼實現(xiàn)

#include

// 函數(shù)用于交換兩個整數(shù)的值

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

int temp = *x;

*x = *y;

*y = temp;

}

// 函數(shù)用于維護(hù)最大堆的性質(zhì)

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

int largest = i; // 初始化最大值為當(dāng)前節(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é)點比當(dāng)前最大值的節(jié)點還大，更新最大值的索引

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

largest = right;

}

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

if (largest != i) {

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

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

}

}

// 主函數(shù)實現(xiàn)堆排序

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

// 構(gòu)建最大堆

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

heapify(arr, n, i);

}

// 一個一個取出元素進(jìn)行排序

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

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

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

// 重新調(diào)整堆，排除已排序的部分

heapify(arr, i, 0);

}

}

// 輔助函數(shù)：打印數(shù)組元素

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

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

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

}

printf("\n");

}

// 測試堆排序的主函數(shù)

int main() {

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

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

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

printArray(arr, n);

heapSort(arr, n);

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

printArray(arr, n);

return 0;

}

代碼逐步講解

swap函數(shù)：

交換兩個整數(shù)的值，用于調(diào)整堆中元素的位置。 heapify函數(shù)：

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

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

打印數(shù)組中的元素，幫助觀察排序的結(jié)果。 main函數(shù)：

初始化一個數(shù)組，打印原始數(shù)組，調(diào)用heapSort函數(shù)進(jìn)行排序，然后打印排序后的數(shù)組。

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

堆排序代碼講解

堆排序簡介

堆排序是一種基于堆（Heap）數(shù)據(jù)結(jié)構(gòu)的排序算法。堆是一棵完全二叉樹，可以通過數(shù)組表示：

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

堆排序的核心思想是：

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

1. `AdjustDown` 函數(shù)分析（向下調(diào)整）

該函數(shù)用于維護(hù)最大堆的性質(zhì)。它從父節(jié)點開始，將其與子節(jié)點比較，并向下調(diào)整，使得父節(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é)點，則進(jìn)行交換

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

{

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

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

parent = child;

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

}

else

{

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

}

}

}

解釋：

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

2. `HeapSort` 函數(shù)分析（堆排序的實現(xiàn)）

void HeapSort(int* a, int n)

{

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

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]); // 將堆頂元素與當(dāng)前未排序部分的最后一個元素交換

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

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

}

}

詳細(xì)講解：

建堆過程：

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

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

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

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

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

建堆：

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

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

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

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

時間復(fù)雜度

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

堆排序的特點

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

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

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

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

http://yzkb.51969.com/

好文鏈接