選擇排序原理及代碼實作(c/c++)

選擇排序與冒泡排序類似，采用逐輪掃描最值然後将其置于頂端的方式完成數組排序。差別是，冒泡法采取的是依次比較相鄰元素并不斷交換逆序元素的政策，逐漸将最值向前推進；而選擇排序法采取标記最值位置的政策，掃描過程中不交換元素位置，隻修改标記，直至找到最值，将最值交換到頂端。相對于冒泡法，可顯著減少交換次數，每輪掃描至多交換1次。

原理：設定最值位置标記，逐輪掃描未排序部分元素最值。每一輪掃描過程中，以未排序部分首部元素為基準(将位置标記設定為未排序首元素下标)與後續元素進行比較。遇到更小(或更大)的元素則将位置标記修改為其下标，直至掃描完成，将标記位置的元素與未排序部分首元素交換位置。至多進行n-1輪掃描，序列完全有序。

步驟：

第 1 輪，所有元素均未經排序，将标記設定為第一個元素下标，以第一個元素為基準依次與後面的元素進行比較，不斷修改最值标記為較小元素的下标，經過 n-1 次比較位置标記必将為最值下标，然後将最值與第一個元素交換位置。此時首元素稱作已排序部分，其餘元素為未排序部分。

第 i 輪，前 i-1 個元素為已排序部分，将标記設定為第 i 個元素下标，并以第 i 個元素為基準依次與後面的元素進行比較，不斷修改最值标記為較小元素的下标，經過 n-i 次比較位置标記必将為最值下标，然後将最值與未排序部分第一個元素(即第 i 個元素)交換位置。此時前 i 個元素有序，其餘元素無序。

第 n-1 輪，将标記設定為第 n-i 個元素下标，然後與最後一個元素進行比較，較小者前置，至此所有元素完成排序。

代碼：

void selectionsort(int A[], int n)
{
	int mark;
	for (int i = 1; i < n; i++)  //i的取值範圍為[1,n-1]，共n-1輪
	{
		mark = i-1;   //初始化标記，元素下标從零開始，比輪次落後1
		for (int j = i; j < n; j++)  //j的取值範圍為[i，n-1]，共比較n-1-i+1次，即n-i次
		{
			if (A[mark]>A[j])        //最值不在标記處則修改标記
				mark = j;
		}
		if (mark != i - 1)           //标記若修改則将最值置換至頂端
		{
			A[mark] = A[mark] + A[i - 1];
			A[i-1] = A[mark] - A[i - 1];
			A[mark] = A[mark] - A[i - 1];
		}
	}
}