【算法】选择排序法

一、介绍

1.选择排序法是将序列分为两段，有序前列和无序后列，每次查找无序后列中最大元素，将其插入到有序前列的最末尾处，直至无序后列最后一个元素，最终排序后的序列为降序序列

2.适用于包括数组和向量在内的序列

3.选择排序与冒泡排序的区别是选择排序每次遍历时会记住最大元素的位置，只进行一次交换，而冒泡排序每次遍历时会交换两个顺序不合法的元素

二、思想

1.将序列分为两段，有序前列[0,r)和无序后列[r,n-1]

2.在无序后列中查找最大元素s=A[m]，记住其所在位置

3.将无序后列中的最大元素与无序前列的首位元素进行交换

4.循环停止标识：无序后列只剩余最后一个元素

三、程序

1.算法程序

#include "stdafx.h"
#include<iostream>

using namespace std;

void SelectSort(int A[],int n)
{
	for(int i = 0;i < n;i++ )
	{
		int max =i;
		for(int j = i+1;j < n;j++) //查找最大元素所在位置
		{
			if (A[j] > A[max])
			max =j;
		}
		int temp = A[max];  //交换无序后列中首元素与最大元素的位置
		A[max] = A[i];
		A[i] = temp;
	}
}

2.测试用例

void TestSelectSort()
{
	int A[] = {1,4,26,33,19,6,12,14,45,26,13};
	int n = 11;
	std ::cout << "排序前的数组：" ;
	for (int i = 0 ;i < n ; i++)
	{
		std ::cout << A[i]<<" " ;
	}
	SelectSort( A,n);
	std ::cout << "排序后的数组：" ;
	for (int i = 0 ;i < n ; i++)
	{
		std ::cout  << A[i]<<" " ;
	}
}

3.测试结果

四、复杂度

T（n）= O（n^2）