簡(jiǎn)單選擇排序算法

1、簡(jiǎn)單選擇排序算法（Simple Selection Sort）

---- 通過(guò)n-i次關(guān)鍵字間的比較，從n-i+1個(gè)記錄中選出關(guān)鍵字最小的記錄，并和第i（1<=i<=n）個(gè)記錄進(jìn)行交換。

#define?MaxSize?10
typedef?struct?
{
	int?r[MaxSize];
	int?length;
}SqList;

void?swap(SqList?*L,int?i,int?j)
{
	int?t?=?L->r[i];
	L->r[i]?=?L->r[j];
	L->r[j]?=?t;
}
void?SelectSort(SqList?*L)
{
	int?i,j,min;
	for(i=0;ilength-1;i++)
	{
		min?=?i;		//將當(dāng)前下標(biāo)定義為最小值下標(biāo)
		for(j=i+1;jlength;j++)
		{
			if(L->r[j]r[min])?//注意不是和第i個(gè)進(jìn)行比較，是和前面的最小值進(jìn)行比較
			{
				min?=?j;//min是未排序的最小值的下標(biāo)
			}
		}
		if(i!=min)
		{
			swap(L,i,min);
		}
	}

}
int?main()
{
	SqList?*L?=?(SqList*)malloc(sizeof(SqList));
	int?a[MaxSize]?=?{9,1,5,8,3,7,4,6,2,0};
	for(int?i=0;ir[i]?=?a[i];
	}
	L->length?=?MaxSize;
	SelectSort(L);
	cout<<"排序后的序列如下："<<endl;
	for(int?i=0;ilength;i++)
	{
		cout<r[i]<<"?";
	}
	cout<<endl;
	system("pause");
	return?0;
}

最大的特點(diǎn)是：交換移動(dòng)數(shù)據(jù)次數(shù)相當(dāng)少。無(wú)論最好最差的情況，其比較次數(shù)都是一樣的多，第i趟排序需要進(jìn)行n-i次關(guān)鍵字的

比較，此時(shí)需要比較(n-1)+(n-2)+....+1=n(n-1)/2次。

對(duì)于交換次數(shù)而言，最好的時(shí)候，交換為0次，最差的時(shí)候，交換次數(shù)是n-1次，總的時(shí)間復(fù)雜度是O(n^2).