算法原理：所谓选择排序经过 n-1 次选择，当进行第 i 次选择时，是从第1个元素到第 n-i+1 的元素中选择最大的元素和第 n-i+1 个位置的元素交换，这样做比如第1次选择使得最大的元素到了数组的最后一个位置。注意哦，在选择排序中每次选择时只进行一次数据的交换。
算法代码：
#include <iostream> using namespace std; void swap(int &x,int &y) { int tmp = x; x = y; y = tmp; } void select_sort(int *arr,int n) { int i,j; for(i = n-1 ; i > 0 ; --i) { int tmp = 0; for(j = 1 ; j <= i ; ++j) { if(arr[j] >= arr[tmp])//这里的“=”是保证选择排序稳定的关键 { tmp = j; } } swap(arr[i],arr[tmp]); } } int main() { int arr[] = {2,1,4,3,8,7,5,6}; select_sort(arr, 8); for(int i = 0 ; i < 8 ; ++i) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
小结：选择排序的思路非常的简单，实现起来也不难。时间复杂度是O(n^2)，选择排序也是稳定的排序，并且也是原地排序。选择排序的时间基本不受数据的影响，因为不管怎样都要进行n-1次选择排序。