資料結構------簡單選擇排序 C++ 實作

• 簡單選擇排序是一種選擇排序。

• 選擇排序：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結束為止。

(1)從待排序序列中，找到關鍵字最小的元素；

(2)如果最小元素不是待排序序列的第一個元素，将其和第一個元素互換；

(3)從餘下的 N - 1 個元素中，找出關鍵字最小的元素，重複(1)、(2)步，直到排序結束。

• 簡單選擇排序的時間複雜度是 O(n*n）；空間複雜度為 O(1)。

以下是C++源代碼：

#include<iostream> 
using namespace std;
#define MAXSIZE 100
typedef struct 
{
	int key;
	int otherinfo;
}RedType;
typedef struct
{
	RedType r[MAXSIZE+1];
	int length;
}SqList;
void SelectSort(SqList &L)
{
	for(int i=1;i<L.length;++i)	//在 L.r[i...L.length] 中選擇關鍵字最小的記錄 
	{
		int k=i;
		for(int j=i+1;j<=L.length;++j)
			if(L.r[j].key<L.r[k].key)	k=j;// k 指向此趟排序中關鍵字最小的記錄 
		if(k!=i)	//交換 r[i] 與 r[k] 
		{	//在 i 所指的元素不是最小紀錄的情況下 
			//int t;
			L.r[0]=L.r[i];
			L.r[i]=L.r[k];
			L.r[k]=L.r[0];
		}
	}
}
int main()
{
	SqList L;
	int n;
	cout<<"請輸入記錄的個數："<<endl;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>L.r[i].key;
	L.length=n;
	for(int i=1;i<=L.length;i++)
		cout<<L.r[i].key<<"  ";
	cout<<endl;
	SelectSort(L);
	for(int i=1;i<=L.length;i++)
		cout<<L.r[i].key<<"  ";
	cout<<endl;
	return 0;
}
           

• 運作結果：

例如：輸入   6  （記錄個數）

           12    3    4     77    80     20

輸出為

 12    3    4     77    80     20（原序列）

  3     4    12    20    77    80     

另一種實作直接選擇排序的源代碼（不用結構體，用數組實作）：

#include<iostream>
using namespace std;
int s[10000];
int main()
{
	int n,i,j;
	cout<<"請輸入記錄的個數："<<endl;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>s[i];
	for(i=1;i<n;i++)
	{
		int k=i;
		for(j=i+1;j<=n;j++)
		{
			if(s[j]<s[k])
				k=j;
		}
		if(k!=i)
		{
			int t;
			t=s[i];
			s[i]=s[k];
			s[k]=t;
		}
	}
	for(i=1;i<=n;i++)
		cout<<s[i]<<"  ";
	cout<<endl;
	return 0;
}
           

運作結果和上面第一種方法一樣。