資料結構與算法——排序算法之選擇排序

• 一：選擇排序原理：

  将要排序的資料元素選出最小（大），将他和資料元素的首位交換位置。再次從剩下的資料元素中 找到最小（大）的元素，然後與資料元素的第二位子交換。。。直到将整個資料元素排序。

  總之他在不斷選擇剩餘元素的最小值，然後放在恰當的位置。

• 二：選擇排序的特點：

  1.運作時間和輸入無關。

  為了找出最小的元素，周遊整個數組并不能為下一次周遊提供資訊。這樣的缺點是：一個有序的數組與一個随機數組所用的排序時間相同。

  2.資料移動最少。

  每次交換都會改變兩個元素的值，是以數組多大，就幾次資料移動。

• 三：代碼描述（java實作）：

public static void sort(int[] a){
    int N=a.length;
    for(int i=0;i<N;i++){
        int min=i;
        for(int j=i+1;j<N;j++){
            if(a[j]<a[min]){  
                min=j;
            }
        }
        int temp=a[i];
        a[i]=a[min];
        a[min]=temp;
    }
}
           

内循環為找到目前序列的最小元素。然後最小元素與相應的位置的元素交換位置。每次交換能确定一個元素的位置，是以總交換次數為N.是以算法的時間效率取決于比較次數N*（N-1）/2

2.（c實作）

//選擇法排序
#include<stdio.h>
int main(void)
{
	int i,n,k,temp,index;
	int a[10];
	printf("Enter n:");
	scanf("%d",&n);
	printf("Enter %d integers:",n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	
	for(k=0;k<n-1;k++)
	{
		index=k;
		for(i=k+1;i<n;i++)
			if(a[i]>a[index])
				index=i;
		temp=a[index];
		a[index]=a[k];
		a[k]=temp;
	}
	
	printf("After sorted:");
	for(i=0;i<n;i++)
		printf("%d ",a[i]);
	printf("\n");
	
	return 0;
}