選擇法排序

選擇法排序是一種簡單的容易實現的對數據排序的算法。不論待排序是正序還是逆序，它們所經過的時間複雜度都是一樣的，即經過n*（n-1）/2.因此選擇法的時間複雜度為O（n^2）.
以整形數組元素為例，有數組A[10]（以C語言為例描述），即A[0]，A[1]，…，A[8]，A[9]（假設其元素均互不相同）。要求對其元素排序使之遞增有序。
首先以一個元素為基準，從一個方向開始掃描，比如從左至右掃描，以A[0]為基準。
接下來從A[0]，…，A[9]中找出最小的元素，將其與A[0]交換。
然後將基準位置右移一位，重複上面的動作，比如，以A[1]為基準，找出A[1]~A[9]中最小的，將其與A[1]交換。
一直進行到基準位置移到數組最後一個元素時排序結束（此時基準左邊所有元素均遞增有序，而基準為最後一個元素，故完成排序）。
以下為一個用C描述的函式用兩者方式（本質都是選擇排序法，但是第二種代碼較少）實現上述排序：
第一種：
void sort(int array[],int n)
{ // n 為數組元素個數
int i,j,k,temp; // i 為基準位置，j 為當前被掃描元素位置，k 用於暫存出現的較小的元素的位置
for(i=0;i<n-1;i++)
{k=i;//初始化為基準位置
for(j=i+1;j<n;j++)
{
if (array&#91;j&#93;<array&#91;k&#93;) k=j ; // k 始終指示出現的較小的元素的位置
} //for
if(k!=i)
{ temp=array&#91;i&#93;;
array&#91;i&#93;=array&#91;k&#93;;
array&#91;k&#93;=temp; // 將此趟掃描得到的最小元素與基準互換位置
}
}
}
第二種：
void sort(int array&#91;&#93;,int n)
{ // n 為數組元素個數
int i,j,k,temp; // i 為基準位置，j 為當前被掃描元素位置，k 用於暫存出現的較小的元素的位置
for(i=0;i<n-1;i++)
{k=i;//初始化為基準位置
for(j=i+1;j<n;j++)
{
if (array&#91;j&#93;<array&#91;k&#93;) // k 始終指示出現的較小的元素的位置
{ temp=array&#91;j&#93;;
array&#91;j&#93;=array&#91;k&#93;;
array&#91;k&#93;=temp;}// 將此趟掃描得到的最小元素與基準互換位置
}
}
}
其實現相對簡單，效率比較低，時間複雜度為O(n2) （n 的平方） ，為就地排序。
--------------
選擇排序(Straight Selection Sort)選擇排序的基本思想
n個記錄的檔案的選擇排序可經過n-1趟直接選擇排序得到有序結果：
①初始狀態：無序區為R&#91;1..n&#93;，有序區為空。
②第1趟排序
在無序區R&#91;1..n&#93;中選出關鍵字最小的記錄R&#91;k&#93;，將它與無序區的第1個記錄R&#91;1&#93;交換，使R&#91;1..1&#93;和R&#91;2..n&#93;分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
……
③第i趟排序
第i趟排序開始時，當前有序區和無序區分別為R&#91;1..i-1&#93;和R&#91;i..n&#93;(1≤i≤n-1)。該趟排序從當前無序區中選出關鍵字最小的記錄 R&#91;k&#93;，將它與無序區的第1個記錄R&#91;i&#93;交換，使R&#91;1..i&#93;和R&#91;i+1..n&#93;分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。
這樣，n個記錄的檔案的直接選擇排序可經過n-1趟直接選擇排序得到有序結果。
using System;
using System.Collections.Generic;
using System.Text;
namespace ExSelectionSorter
{
class SelectionSorter
{
private int min;
public void Sort(int&#91;&#93; arr)
{
for (int i = 0; i < arr.Length - 1; ++i)
{
min = i;
for (int j = i + 1; j < arr.Length; ++j)
{
if (arr&#91;j&#93; < arr&#91;min&#93;)
min = j;
}
int t = arr&#91;min&#93;;
arr&#91;min&#93; = arr&#91;i&#93;;
arr&#91;i&#93; = t;
}
}
static void Main(string&#91;&#93; args)
{
int&#91;&#93; array = new int&#91;&#93; { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
SelectionSorter s = new SelectionSorter();
s.Sort(array);
foreach (int m in array)
Console.WriteLine("{0}", m);
}
}
}