目錄

前言

一、代碼實現(xiàn)

二、時空復雜度

時間復雜度：

空間復雜度：

---

前言

建議：1.學習算法最重要的是理解算法的每一步，而不是記住算法。

?????????? 2.建議讀者學習算法的時候，自己手動一步一步地運行算法。

tips:希爾排序算法就是通過該算法衍生出來的，通過理解本算法可以為理解希爾排序打下基礎。同時，本算法的邏輯簡單。

直接排序算法，也稱為選擇排序（Selection Sort），是一種簡單直觀的排序算法。其基本思想是每一趟從待排序的數(shù)據(jù)元素中選擇最小（或最大）的一個元素，將它與序列的第一個元素進行交換，然后再從剩余的元素中選擇最小（或最大）的元素，與序列的第二個元素進行交換，如此循環(huán)，直到整個序列有序。總結就是，將無序元素與其前面的元素比較大小，以此來確定其位置，從而將其加入前面的有序的部分。

一、代碼實現(xiàn)

#include <stdio.h>// 交換數(shù)組中兩個元素的值
void swap(int *xp, int *yp) {int temp = *xp;*xp = *yp;*yp = temp;
}// 直接排序函數(shù)
void selectionSort(int arr[], int n) {int i, j, min_idx;// 選擇排序的主循環(huán)for (i = 0; i < n-1; i++) {// 尋找在未排序部分中的最小元素的索引min_idx = i;for (j = i+1; j < n; j++)if (arr[j] < arr[min_idx])min_idx = j;// 將找到的最小元素與當前位置元素交換swap(&arr[min_idx], &arr[i]);}
}// 打印數(shù)組元素
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};int n = sizeof(arr) / sizeof(arr[0]);printf("原始數(shù)組: \n");printArray(arr, n);// 調用直接排序算法selectionSort(arr, n);printf("\n排序后的數(shù)組: \n");printArray(arr, n);return 0;
}

在這段代碼中，swap 函數(shù)用于交換數(shù)組中兩個元素的值，而 selectionSort 函數(shù)實現(xiàn)了直接排序算法。主要的思路是在未排序的部分中找到最小元素的索引，然后與當前位置的元素進行交換，通過不斷進行這樣的操作，實現(xiàn)整個數(shù)組的排序。

二、時空復雜度

時間復雜度：

直接排序算法的時間復雜度主要由兩層循環(huán)決定。

外層循環(huán)：外層循環(huán)的次數(shù)是 n-1，其中 n是數(shù)組的長度。這是因為在進行 n-1次選擇后，剩下的最后一個元素已經(jīng)有序了。

內(nèi)層循環(huán)：內(nèi)層循環(huán)用于在未排序的部分中尋找最小元素的索引。在最壞情況下，每次選擇都需要遍歷剩余未排序的元素。內(nèi)層循環(huán)的次數(shù)是n,n-1,n-2,…,1。其平均時間復雜度為。

綜合考慮外層和內(nèi)層循環(huán)(只要考慮n的次數(shù)大的復雜度)，直接排序的時間復雜度為

其平均/最好/最差時間復雜度均為

空間復雜度：

直接排序是一種原地排序算法，它只需要常數(shù)級別的額外空間來存儲少量的輔助變量，如循環(huán)中的索引和臨時變量。因此，直接排序的空間復雜度為 O(1)，即常數(shù)級別的額外空間。