C++選択ソートアルゴリズムの実現と改善(筆記試験の面接問題を含む)

選択ソート(Selection sort)も最も簡単で直感的なソートアルゴリズムである.アルゴリズムステップ1)まず、ソートされていないシーケンスで最小(大)要素を見つけ、ソートされたシーケンスの開始位置2に格納します.次に、残りのソートされていない要素から最小(大)要素を探し続け、ソートされたシーケンスの最後に配置します.
3)すべての要素が並べ替えられるまで、手順2を繰り返します.
実装コード:2回の実装で、それぞれ異なるパラメータが入力され、1回の改善:毎回最大値と最小値を超えます.

/***************************************************************************
 *  @file       main.cpp
 *  @author     MISAYAONE
 *  @date       25  March 2017
 *  @remark     25  March 2017 
 *  @theme      Selection Sort 
 ***************************************************************************/

#include 
#include 
using namespace std;

void Sort_swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

//       ，       ，               
void Selection_sort(vector::iterator begin,vector::iterator end)
{
	for (auto p1 = begin; p1 != end; ++p1)
	{
		for (auto p2 = p1; p2 != end; ++p2)
		{
			if (*p1 > *p2)
			{
				int temp = *p1;
				*p1 = *p2;
				*p2 = temp;
			}
		}
	}
}

//           ，       ，               
void Selection_sort(int a[],size_t size)
{
	for (size_t i = 0; i < size/2; ++i)
	{
		int max_elem = size-1-i;
		int min_elem = i;
		for (size_t j = i+1; j < size-i; ++j)
		{
			if (a[j] < a[min_elem])
			{
				min_elem = j;
				continue;//         
			}
			if (a[j] > a[max_elem])
			{
				max_elem = j;
			}
		}
		Sort_swap(a[i],a[min_elem]);
		Sort_swap(a[size-1-i],a[max_elem]);	

		//   ：                ，      
		if((i==size-i-1&&min_elem==max_elem)||(i==max_elem&&size-i-1==min_elem))
		{  
			Sort_swap(a[i],a[min_elem]);//    
		}  
	}
}

int main(int argc, char **argv)
{
	int a[10] = {2,5,6,3,1,4,8,7,9,0};
	vector vec(a,a+10);

	Selection_sort(vec.begin(),vec.end());
	for (size_t i = 0; i < vec.size(); ++i)
	{
		cout<

選択ソートの交換操作は0～(n-1)回です.
選択ソートの比較操作はn(n−1)/2回である.
選択ソートの付与操作は0～3(n-1)回です.
比較回数O(n^2)、比較回数はキーワードの初期状態に関係なく、総比較回数N=(n-1)+(n-2)+...+1=n*(n-1)/2. 
交換回数O(n)、最良の場合は、すでに秩序化され、0回交換されている.最悪の場合,逆シーケンス,n−1回交換する. 
選択ソートの交換回数はバブルソートよりも少なく,交換に必要なCPU時間は比較に必要なCPU時間よりも多く,n値が小さいため,選択ソートはバブルソートよりも速い.
複雑度分析:
ベストタイム:O(n^2)
平均時間複雑度:O(n^2)
最悪時間:O(n^2)
特徴分析:In-place sort,不安定アルゴリズム(stable sort)
例題1:挿入と選択ソートで、初期データが基本順であれば挿入ソート(末尾まで)、初期データが基本逆であれば選択ソート
例題2:下記のいくつかの並べ替え方法の中で、平均検索長(ASL)が最も小さいのはAである.ソートBを挿入する.クイックソートC.集計ソートD.ソートの選択