阿夢的程式設計天地

選擇排序法實際執行狀況如下(假設需要將資料由小排到大):

將"已排序"的資料擺在資料序列的前端，並且將"未排序"的資料擺在資料序列的後端。(如果沒有已排序的資料，則全部的資料視為未排序)

假設要將n筆資料由小排到大，一開始的時候的n筆資料是"未排序"的。這個時候就將n筆"未排序"的資料中取出最小值，並且將其放到"已排序"資料的最後端，也就是說將其和第一筆資料進行交換。

接下來在從n-1筆"未排序"的資料中取出最小值，一樣的放入到"已排序"的資料的最後端(和第2筆資料進行交換，因為弟1筆資料是已排序的第一筆資料，而第2筆資料是目前未排序資料當中的第一筆);再從剩下的n-2筆"未排序"資料取出最大值，加入到"已排序"資料的最後端(與第三筆資料進行交換)

依此類推，一直到沒有任何"未排序"的資料時停止。

範例:排序 3 7 1 2 9 4 

3 7 1 2 9 4 (已排序: 未排序:3 7 1 2 9 4  行為:發現1為未排序中最小值，將1和3交換)
1 7 3 2 9 4 (已排序: 1未排序:7 3 2 9 4  行為:發現2為未排序中最小值將2和7交換)
1 2 3 7 9 4 (已排序:1 2  未排序:3 7 9 4 行為:發現3為未排序中最小值，但也剛好在已排序資料的後端，故將其加入到已排序)
1 2 3 7 9 4 (已排序:1 2 3  未排序:7 9 4  行為:發現4為未排序中最小值，將4和7交換)
1 2 3 4 9 7 (已排序:1 2 3 4  未排序:9 7 行為:發現7為未排序中最小值，將7和9交換)
1 2 3 4 7 9 (已排序:1 2 3 4 7未排序:9 行為:發現9為未排序中最小值，但也剛好在已排序資料的後端，故將其加入到已排序)
1 2 3 4 7 9(已排序:1 2 3 4 7 9  未排序: 行為:)

時間複雜度如下:

最佳時間複雜度：O(n^2) 

平均時間複雜度：O(n^2)

最差時間複雜度：O(n^2)

說明:無論資料順序如何，都會執行兩個迴圈。

PseudoCode 大致如下:

template < typename T > //整數或浮點數皆可使用

void selection_sort( T arr [], int len ) {
	 int i , j , min ;
	 for ( i = 0 ; i < len - 1 ; i ++ ) {
		 min = i ;
		 for ( j = i + 1 ; j < len ; j ++ )
			 if ( arr [ min ] > arr [ j ])
				 min = j ;
		 swap ( arr [ i ], arr [ min ]);
	 }
 }

void swap(int array_1, int array_2)
{
	int temp = 0;

	temp = array_1;
	array_1 = array_2;
	array_2 = temp;
}

完整程式碼如下: 本次以 "Pass by reference"的方式實作

#include <iostream>
#include <iomanip>
using namespace std;

void selectionSort(int*const, const int);
void swap(int *const,int*const);

int main() {
	int size = 0;
	int *ptr;

	cout << "請輸入陣列空間:" << endl;
	cin >> size;

	ptr = new int[size];//動態記憶體配置陣列

	cout << "請輸入陣列資料:";

	for (int i = 0; i < size; i++)
	{
		cin >> ptr[i];// ptr[i]等價於 *(ptr+i)
	}

	cout << "原本的陣列資料:" << endl;

	for (int i = 0; i < size; i++)
	{
		cout<< ptr[i]<<" ";// ptr[i]等價於 *(ptr+i)
	}

	cout << endl;

	selectionSort(ptr,size);

	cout << "排序後的資料:" << endl;

	for (int i = 0; i < size; i++)
	{
		cout << ptr[i]<<" ";// ptr[i]等價於 *(ptr+i)
	}

	cout << endl;


	system("pause");
	return 0;
}

void selectionSort(int*const array, const int arraysize)
{
	int smallest = 0;//宣告未排序序列中最小值

	for (int i = 0 ;i <arraysize;i++)
	{
		smallest = i;

		for (int j = i + 1; j < arraysize;j++)
		{
			if (array[j] < array[smallest])
			{
				smallest = j;//尋找未排序序列中最小值
			}
		}

		swap(&array[i],&array[smallest]);//將未排序序列中的最小值加入到已排序序列中的最後端
	}

}
void swap(int *const array_1, int*const array_2)
{
	int temp = 0;

	temp = *array_1;
	*array_1 = *array_2;
	*array_2 = temp;
}

執行結果如下:

有夢最美 築夢踏實

活在當下 認真過每一天

我是阿夢 也是Ace