选择排序

选择排序（Selection Sort）是一种简单直观的排序算法。算法的处理过程是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到未排序序列的首部（也就是已排序序列末尾的下一个位置）。以此类推，直到处理完所有待排序的数据元素。可知选择排序是将序列前面部分变得有序，并且将有序的区间逐步扩大直到整个序列有序。

//选择排序：对数组的r[0]~r[n-1]区域排序（升序排序）
void SelectSort(int r[],int n){
	for(int i=0;i<n-1;i++){
		int k = i;		//k记录r[i]~r[n-1]最小值的下标 
		for(int j=i+1;j<n;j++){
			//新找到一个更符合条件的数据，更新记录最小值下标的变量k 
			if(r[j]<r[k]) k = j;
		}
		//新找到一个不是初始值i的下标k，交换r[i]和r[k] 
		if(k != i){
			int t = r[k];r[k] = r[i];r[i] = t;
		}
	}
}
//调用方法举例：SelectSort(a,10);
//调用方法举例：SelectSort(a,n);

仿照 sort 函数的写法，用两个指针作为函数参数来指定排序的区域：

//选择排序：对指针begin~end区域排序（升序排序，不包括end）
void SelectSort(int *begin,int *end){
    for(int *p = begin;p+1<end;p++){
        int *k = p;        //k记录 p ~ end-1 区域最小值的指针 
        for(int *q = p+1;q<end;q++){
            //新找到一个更符合条件的数据，更新记录最小值下标的指针k 
            if(*q < *k) k = q;
        }
        //新找到一个不是初始值p的指针k，交换 *p 和 *k 
        if(k != p){
            int t = *k;*k = *p;*p = t;
        }
    }
}
//调用方法举例：SelectSort(a,a+10);
//调用方法举例：SelectSort(a,a+n);
//调用方法举例：SelectSort(a+1,a+n+1);

选择排序的时间复杂度是 $O(n^2)$。如下图所示可知选择排序是不稳定的排序算法：

如图所示，选择排序结束后，第 1 个 6（红色文字标识）出现在第 2 个 6 的后面，可见选择排序是不稳定的。

这里仿照 sort 函数实现带自定义比较函数的选择排序函数，帮助大家理解 sort 函数是如何通过比较函数实现自定义排序的：

#include<iostream>
using namespace std;
const int N = 110;
int a[N]; 

//选择排序：对指针 begin~end 区间进行升序排序，不包含end 
void SelectSort(int *begin ,int *end){
    for(int *p = begin;p+1<end;p++){
        int *k = p;
        for(int *q = p+1;q<end;q++){
            if(*q < *k) k = q;
        }
        if(k != p){
            int t = *k;*k = *p;*p = t;
        }
    }
}

//选择排序：对指针 begin~end 区间进行排序，不包含end
//第三个参数cmpfun是排序比较函数，注意这个参数的类型是函数 
void SelectSort(int *begin ,int *end ,bool(*cmpfun)(int a ,int b) ){
    for(int *p = begin;p+1<end;p++){
        int *k = p;
        for(int *q = p+1;q<end;q++){
        	//调用比较函数cmpfun，由比较函数返回值决定是否更新k 
            if(cmpfun(*q,*k)) k = q;
        }
        if(k != p){
            int t = *k;*k = *p;*p = t;
        }
    }
}

//比较函数：降序排序
bool cmp(int a,int b){
	return a>b;
}

//比较函数：升序排序
bool cmp2(int a,int b){
	return a<b;
}

int main(){ 
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	
	//调用没有比较函数的SelectSort 
	SelectSort(a,a+n);
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	
	//调用有比较函数的SelectSort
	SelectSort(a,a+n,cmp);
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;

	//调用有比较函数的SelectSort
	SelectSort(a,a+n,cmp2);
	for(int i=0;i<n;i++){
		cout<<a[i]<<" ";
	}
	cout<<endl;
	
	return 0;
}