【概述】

直接選擇排序又稱簡單選擇排序，是一種不穩(wěn)定的排序方法，其是選擇排序中最簡單一種，其基本思想是：第 i 趟排序再待排序序列 a[i]~a[n] 中選取關(guān)鍵碼最小的記錄，并和第 i 個記錄交換作為有序序列的第 i 個記錄。

其實現(xiàn)利用雙重循環(huán)，外層 i 控制當(dāng)前序列最小值存放的數(shù)組元素位置，內(nèi)層循環(huán) j 控制從 i+1 到 n 序列中選擇最小的元素所在位置 k

【排序過程】

1.排序過程

具體的排序過程為：

將整個記錄序列劃分為有序區(qū)和無序區(qū)，初始時有序區(qū)為空，無序區(qū)含有待排序的所有記錄

在無序區(qū)選擇關(guān)鍵碼最小的記錄，將其與無序區(qū)中的第一個元，使得有序區(qū)擴(kuò)展一個記錄，同時無序區(qū)減少了一個記錄

不斷重復(fù)步驟 2，直到無序區(qū)只剩下一個記錄為止

2.實例

?初始關(guān)鍵字：『?8，5，2，6，9，3，1，4，0，7?』

?第一趟排序后：0，『5，2，6，9，3，1，4，8，7』

?第二趟排序后：0，1，『2，6，9，3，5，4，8，7』

?第三趟排序后：0，1，2，『6，9，3，5，4，8，7』

?第四趟排序后：0，1，2，3，『9，6，5，4，8，7』

?第五趟排序后：0，1，2，3，4，『6，5，9，8，7』

?第六趟排序后：0，1，2，3，4，5，『6，9，8，7』

?第七趟排序后：0，1，2，3，4，5，6，『9，8，7』

?第八趟排序后：0，1，2，3，4，5，6，7，『8，9』

?第九趟排序后：0，1，2，3，4，5，6，7，8，『9』

?結(jié)果： ? ? ? ? ?『?0，1，2，3，4，5，6，7，8，9?』

??????????

? ? ?排序過程? ? ? ? ? ? ? ? ? ? 宏觀過程

【時空復(fù)雜度分析】

容易看出，待排序序列為正序，移動次數(shù)最小，為 0 次；待排序序列為逆序時，移動次數(shù)最多，為 3(n-1) 次。

但無論記錄的初始排列如何，關(guān)鍵碼的比較次數(shù)相同，第 i 趟排序需進(jìn)行 n-i 次關(guān)鍵碼的比較，而簡單選擇排序需要進(jìn)行 n-1 趟排序，因此，總的比較次數(shù)為 O(n^2)

故而，無論是最優(yōu)、最差時間復(fù)雜度，還是平均時間復(fù)雜度，均為 O(n^2)

對于空間復(fù)雜度來說，簡單選擇排序僅需一個存儲空間用于記錄交換的暫存單元，即空間復(fù)雜度為 O(1)

【源程序】

void selectSort(int a[],int n){for(int i=1;i<=n-1;i++){//進(jìn)行n-1趟選擇int index=i;for(int j=i+1;j<=n;j++)//從無序區(qū)選取最小的記錄if(a[index]>a[j])index=j;if(index!=i)swap(a[i],a[index]);} }

?

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 排序 —— 直接选择排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。