常用的选择排序方法有直接选择排序和堆排序。
直接选择排序(Straight Selection Sort)
1、直接选择排序的基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
2、直接选择排序的过程
不太清楚原理最好看看：进行直接选择排序的过程【参见动画演示】
直接选择排序代码如下：
#include <iostream>
using namespace std;
void SelectSort(int arr[], int n);
void main()
{
int ar[]={1,4,5,3,7,8,2};
SelectSort(ar,7);
system("pause");
}
void SelectSort(int arr[], int n)
{
/*
三参数：i，min,k,
i,j，k 开始都指向 第一个元素
i： 循环完一次，加1
min：比较移动，指向最小元素
k： 一直循环的变量
*/
int i,j,k;
for (i = 1; i< n; i++)
{
int min = i;
for (j = i+1; j<n; j++)
{
if (arr[j]<arr[min])
{
min = j;
}
if (j != i)
{
swap(arr[i],arr[min]);
}
}
cout<<"*********排序"<< i <<"次的结果为"<<endl;
for (int g = 0; g < n; g++)
{
cout<<arr[g];
cout<<",";
}
cout<<""<<endl;
}
}
运行效果如下：
