如何在C中實現選擇排序？

選擇排序是另一種算法，它通過定位數組的最低整數然後將其分配給頂部位置來運行。 最小整數位置旁邊的索引將用於開始必須掃描的以下數組。

C 中的選擇排序示例

如果我們取一個包含數字 [10,2,8,4,6] 的數組，其中最小的數字是 2。因此，我們將把最小的數字 2 放在第一個位置，然後數組將查找像 [2,10,8,4,6]。 接下來，我們將取下一個最小的數字，因為 2 現在已經在正確的位置上了。 下一個最小的數是 4，它會被排在第二個位置，之後類似地搜索數組，直到最後排序。

C 中的選擇排序按升序對數字進行排序。 通過修改算法，數字可以按降序排列選擇排序也可以在除C之外的其他語言中執行，如選擇排序C++或選擇排序Python。

從世界一流大學在線學習軟件開發課程。 獲得執行 PG 課程、高級證書課程或碩士課程，以快速推進您的職業生涯。

選擇排序算法

• 首先，我們將選擇排序中的初始元素設置為最小值，並在數組中搜索最小元素，以進行選擇排序算法的正確過程。
• 現在將最小元素與第二個分量進行比較。 如果第二個元素低於最小值，我們將交換它們，然後為第三個元素分配一個最小值。
• 否則，我們將繼續到第三個元素並將其與最小值進行比較。 如果第二個元素超過我們的第一個元素，我們將交換它。 重複此過程直到最後一個組件。
• 每次迭代後，我們會看到我們的最小值已經到達未排序列表的開頭。
• 我們將從每次迭代的未排序列表的第一個條目開始索引。 直到列表被排序或所有組件都被適當定位，我們將重複步驟 1 到 4 幾次。

軟件工程熱門課程和文章

以下每次迭代的示例將有助於詳細了解C 語言中選擇排序的過程——

迭代#1

我 [ ] = 8,5,2,6,4

設置最小值 – 8

比較 i 0和 i 1

由於 i 0 > i 1 ，設置最小值 = 5。

• 比較 i 1和 i 2

由於 i 1 > i 2 ，設置最小值 = 2。

• 比較 i 2和 i 3

由於 i 2 < i 3 ，設置最小值= 2。

• 比較 i 2和 i 4

由於 i 2 < i 4 ，設置最小值 =2。

2 是所有元素中最小的數，我們必須交換 i 0和 i 2

­ 迭代 #2

我 [ ]= 2,5,8,6,4

設置最小值 5

• 比較 i 1和 i 2

由於 i 1 < i 2 ，設置最小值 = 5。

• 比較 i 1和 i 3

當i 1 < i 3 時，設置最小值 = 5

• 比較 i 1和 i 4

同樣， i 1 < i 4 ，設置最小值 = 4。

4 是數組中最小的元素，因此，我們必須交換i 1和 i 4 。

迭代 #3

我 [ ]= 2,4,8,6,5

設置最小值 8

• 比較 i 2和 i 3

由於 i 2 > i 3 ，設置最小值 = 6。

• 比較 i 3和 i 4

由於 i 3 > i 4 ，設置最小值 = 5。

5 是數組中的最小元素，您必須交換 i 2和 i 4 。

迭代 #4

我 [ ] = 2,4,5,6,8

設置最小值 6

• 比較 i 3和 i 4

當 i 3 < i 4時，設置最小值 = 6。

最小值放在正確的位置； 因此，不會發生交換。

C 中的選擇排序示例

// C語言中的選擇排序

#include <stdio.h>

// 交換兩個元素位置的函數

void swap(int *a, int *b) {

int temp = *a;

*a = *b;

*b = 溫度；

}

void selectionSort(int array[], int size) {

for (int step = 0; step < size – 1; step++) {

int min_idx = 步驟；

for (int i = step + 1; i < size; i++) {

// 要按降序排序，請在此行中將 > 更改為 <。

// 在每個循環中選擇最小元素。

如果（數組[i] <數組[min_idx]）

min_idx = i;

}

// 將 min 放在正確的位置

交換（&array[min_idx]，&array[step]）；

}

}

//打印數組的函數

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

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

printf(“%d”, 數組[i]);

}

printf(“\n”);

}

// 驅動程序代碼

詮釋主要（）{

int 數據[] = {20, 12, 10, 15, 2};

int size = sizeof(data) / sizeof(data[0]);

選擇排序（數據，大小）；

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

打印數組（數據，大小）；

}

選擇排序的複雜度分析

Input——給定n個輸入項。

輸出——對列表進行排序所需的步驟數。

邏輯——如果給我們 n 個項目，它會在第一遍進行 n-1 次比較，在第二遍進行 n-2 次比較，在第三遍進行 n-3 次比較，依此類推。 因此，可以使用以下方法計算比較總數；

輸出 -

(n+1) + (n+2) + (n+3) + (n+4) + …. +1

總和 = n(n-1)/2 即 O(n²)

因為選擇排序方法需要一些額外的內存空間用於臨時變量的交換，所以時間複雜度為O(n2)，空間複雜度為O(1)。

選擇排序時間複雜度分析

Best Case：對於之前已經排序的數組，選擇排序方法的best-case時間複雜度為O(n²)。

Average Case：當項目雜亂排列時，選擇排序算法的平均時間複雜度為 O(n²)，即既不是升序也不是降序。

最壞情況：當我們將數組的降序反轉為升序時，最壞情況下的時間複雜度為 O(n²)。

在這三種情況下，選擇排序方法的時間複雜度都是 O(n²)。 這是因為我們必須確定每個階段的最低限度項目，以便正確安排它們。 跟踪整個數組後，我們將找到我們的最小元素。

結論

關於“C 中的選擇排序”的博文到此結束。 您必須了解它也可以用其他語言執行，例如選擇排序 C++和選擇排序 Python。 我們希望本文能幫助您了解如何在 C 中對元素進行排序。

選擇排序並不是成為程序員旅程中的唯一環節。 如果您希望通過專業學位顯著提升您的軟件開發職業生涯，upGrad 就在這裡！ upGrad 的前端開發（JavaScript、HTML、CSS）、後端（NoSQL-MongoDB）和微服務，然後您可以攻讀 UpGrad 的計算機科學理學碩士課程。 本課程由 IIT Bangalore 和 LJMU Alumni Status 提供，可幫助您在世界各地的科技巨頭中成為一名軟件工程師/全棧開發人員。

本課程涵蓋 Java、Spring 和 Hibernate 等工具的基本知識，加強我們的全棧開發技能，以探索具有非凡機會的就業市場。

註冊以了解更多信息！