選擇排序—簡單選擇排序（Simple Selection Sort）

基本思想：

在要排序的一組數中，選出最小（或者最大）的一個數與第1個位置的數交換；然後在剩下的數當中再找最小（或者最大）的與第2個位置的數交換，依次類推，直到第n-1個元素（倒數第二個數）和第n個元素（最後一個數）比較為止。

簡單選擇排序的示例：

操作方法：

第一趟，從n 個記錄中找出關鍵碼最小的記錄與第一個記錄交換；

第二趟，從第二個記錄開始的n-1 個記錄中再選出關鍵碼最小的記錄與第二個記錄交換；

以此類推.....

第i 趟，則從第i 個記錄開始的n-i+1 個記錄中選出關鍵碼最小的記錄與第i 個記錄交換，

直到整個序列按關鍵碼有序。

算法實作：

void print(int a[], int n ,int i){
	cout<<"第"<<i+1 <<"趟 : ";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl;
}
/**
 * 數組的最小值
 *
 * @return int 數組的鍵值
 */
int SelectMinKey(int a[], int n, int i)
{
	int k = i;
	for(int j=i+1 ;j< n; ++j) {
		if(a[k] > a[j]) k = j;
	}
	return k;
}

/**
 * 選擇排序
 *
 */
void selectSort(int a[], int n){
	int key, tmp;
	for(int i = 0; i< n; ++i) {
		key = SelectMinKey(a, n,i);           //選擇最小的元素   遞歸
		if(key != i){
			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素與第i位置元素互換
		}
		print(a,  n , i);
	}
}
int main(){
	int a[8] = {3,1,5,7,2,4,9,6};
	cout<<"初始值：";
	for(int j= 0; j<8; j++){
		cout<<a[j] <<"  ";
	}
	cout<<endl<<endl;
	selectSort(a, 8);
	print(a,8,8);
}
      

 簡單選擇排序的改進——二進制選擇排序

簡單選擇排序，每趟循環隻能确定一個元素排序後的定位。我們可以考慮改進為每趟循環确定兩個元素（目前趟最大和最小記錄）的位置,進而減少排序所需的循環次數。改進後對n個資料進行排序，最多隻需進行[n/2]趟循環即可。具體實作如下

void SelectSort(int r[],int n) {  
02.    int i ,j , min ,max, tmp;  
03.    for (i=1 ;i <= n/2;i++) {    
04.        // 做不超過n/2趟選擇排序   
05.        min = i; max = i ; //分别記錄最大和最小關鍵字記錄位置  
06.        for (j= i+1; j<= n-i; j++) {  
07.            if (r[j] > r[max]) {   
08.                max = j ; continue ;   //continue不可少，否則可能會漏掉一些資料，min的值偏大
09.            }    
10.            if (r[j]< r[min]) {   
11.                min = j ;   
12.            }     
13.      }    
14.      //該交換操作還可分情況讨論以提高效率  
15.      tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;  
16.      tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp;   
17.  
18.    }   
19.}