選擇排序演算法的思路的教案

① 選擇排序法的演算法

簡單選擇排序演算法分析：在簡單選擇排序過程中，所需移動記錄的次數比較少。最好情況下，即待排序記錄初始狀態就已經是正序排列了，則不需要移動記錄。最壞情況下，需要移動記錄的次數最多為3（n-1）（此情況中待排序記錄並非完全逆序，給完全逆序記錄排序的移動次數應為(n/2)*3，其中n/2向下取整）。簡單選擇排序過程中需要進行的比較次數與初始狀態下待排序的記錄序列的排列情況無關。當i=1時，需進行n-1次比較；當i=2時，需進行n-2次比較；依次類推，共需要進行的比較次數是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即進行比較操作的時間復雜度為O(n2)。
選擇排序法 是對 定位比較交換法（也就是冒泡排序法） 的一種改進。在講選擇排序法之前我們先來了解一下定位比較交換法。為了便於理解，設有10個數分別存在數組元素a[0]～a[9]中。定位比較交換法是由大到小依次定位a[0]～a[9]中恰當的值（和武林大會中的比武差不多），a[9]中放的自然是最小的數。如定位a[0],先假定a[0]中當前值是最大數，a[0]與後面的元素一一比較，如果a[4]更大，則將a[0]、a[4]交換，a[0]已更新再與後面的a[5]～a[9]比較，如果a[8]還要大，則將a[0]、a[8]交換，a[0]又是新數，再與a[9]比較。一輪比完以後，a[0]就是最大的數了，本次比武的武狀元誕生了，接下來從a[1]開始，因為狀元要休息了，再來一輪a[1]就是次大的數，也就是榜眼，然後從a[2]開始，比出探花，真成比武大會了，當比到a[8]以後，排序就完成了。
下面給大家一個例子：
int main(void)
{
int a[10];
int i,j,t;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0; i < 9; i ++ )
for ( j = i + 1; j < 10; j ++)
if ( a[ i ] < a[ j ] ) { t = a[ i ]; a[ i ] = a[ j ]; a[ j ] = t; } /*打不過就要讓出頭把交椅，不過a[ i ]比較愛面子，不好意思見 a[ j ]，讓t幫忙*/
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/
return 0;
}
好啦，啰嗦了半天總算把定位比較排序法講完了，這個方法不錯，容易理解，就是有點麻煩，一把椅子換來換去，哎～
所以就有了下面的選擇排序法，開始的時候椅子誰也不給，放在一邊讓大家看著，找個人k記錄比賽結果，然後發椅子。具體來講呢就是，改進定位比較排序法，但是這個改進只是一部分，比較的次數沒變，該怎麼打還是怎麼打，就是不用換椅子了。每次外循環先將定位元素的小標i值記錄到K，認為a[k]是最大元素其實k=i還是a[ i ]最大，a[k]與後面的元素一一比較，該交換的也交換，就是把K的值改變一下就完了，最後在把a[k]與a[ i ]交換，這樣a就是最大的元素了。然後進入下一輪的比較。選擇排序法與定位比較排序法相比較，比的次數沒變，交換的次數減少了。
下面也寫個例子：
由大到小時：
int main(void)
{
int a[10];
int i,j,t,k;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0;i < 9;i ++ ) /*10個數，所以只需比9次*/
{
k = i; /*裁判AND記者實時追蹤報道比賽情況*/
for ( j = i + 1; j < 10; j ++)
if ( a[ k ] < a[ j ] ) k = j; /*使a[k]始終表示已比較的數中的最大數*/
if （k！=i）
{ t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t;} /* t 發放獎品* /
}
for( i = 0; i < 10; i ++) printf("%4d",a[ i ]); /*顯示排序後的結果*/
return 0;
}
由小到大時：
int main(void)
{
int a[10];
int i,j,t,k;
for ( i = 0; i < 10; i ++ ) scanf("%d",&a[ i ]); /*輸入10個數，比武報名，報名費用10000￥ ^_^*/
for ( i = 0; i < 9; i ++ )
{
k = i; /*裁判AND記者實時追蹤報道比賽情況*/
for ( j = i + 1; j < 10; j ++)
if ( a[ k ] > a[ j ] ) k = j;
if （k！=i）
{ t = a[ i ]; a[ i ] = a[ k ]; a[ k ] = t; }/* t 發放獎品*/
}
for( i = 9; i >= 0; i --) printf("%4d",a[ i ]); /*顯示排序後的結果*/
return 0;
}
java選擇排序法代碼public static void main(String[] args) {
Random random=new Random();
int[] pData=new int[10];
for(int i=0;i<pData.length;i++){ //隨機生成10個排序數
Integer a =random.nextInt(100);
pData[i]= a;
System.out.print(pData[i]+" ");
}
System.out.println();
pData=Choose(pData);
for(int i=0;i<pData.length;i++){
System.out.print(pData[i]+" ");
}
System.out.println();
}
public static int[] Choose(int[] pData){
System.out.println();
for (int i = 0; i < pData.length; i++) {
for (int j = i; j < pData.length; j++) {
if(pData[j]<pData[i]){
int a=pData[j];
pData[j]=pData[i];
pData[i]=a;
}
}
}
return pData;
}

② 用選擇法對10個整數由大到小排序。要求畫出流程圖

選擇排序的過程如下：

1. 從待排序的n個元素中找到最大的元素，將其鋒嘩與第n個元素交換位置。

2. 在剩餘的n-1個元素中，再找到最大的元素，將其與第n-1個元素交換位置。

3. 重復上述步驟，直到只剩下一個元素為止。

其中，每經過一輪，就能確定出一個元素的位置。通過n-1輪選擇，就能將這n個元素按照從大到小的順序排好序。選擇排序的時間復雜度為O(n^2)。

下面是銀改行使用C語言實現選擇排序演算法的示例代碼：

#include <stdio.h>

void selection_sort(int arr[], int n)

{

int i, j, max_idx;

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

max_idx = i;

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

if (arr[j] > arr[max_idx]) {

max_idx = j;

}

}

// 將找到的最大元素與當前位置交換

int temp = arr[i];

arr[i] = arr[max_idx];

arr[max_idx] = temp;

}

}

int main()

{

int i, n;

int arr[10] = {23, 4, 56, 77, 12, 45, 89, 34, 67, 90};

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

// 輸出排序前的列表

printf("排序前： ");

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

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

}

printf(" ");

// 調用選擇排序函數

selection_sort(arr, n);

// 輸出排序後的列表

printf("殲猛排序後： ");

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

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

}

printf(" ");

return 0;

}

選排序流程圖：