选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。
下面，以对 3 2 4 1 进行选择排序说明排序过程，使用min_index 记录当前最小的数所在的位置。 第1轮 排序过程 （寻找第1小的数所在的位置） 3 2 4 1（最初， min_index=1） 3 2 4 1（3 > 2， 所以min_index=2） 3 2 4 1（2 < 4， 所以 min_index=2） 3 2 4 1（2 > 1， 所以 min_index=4， 这时候确定了第1小的数在位置4） 1 2 4 3 （第1轮结果，将3和1交换，也就是位置1和位置4交换） 第2轮 排序过程 （寻找第2小的数所在的位置） 1 2 4 3（第1轮结果， min_index=2，只需要从位置2开始寻找） 1 2 4 3（4 > 2， 所以min_index=2） 1 2 4 3（3 > 2， 所以 min_index=2） 1 2 4 3（第2轮结果，因为min_index位置刚好在第2个位置，无需交换） 第3轮 排序过程 （寻找第3小的数所在的位置） 1 2 4 3（第2轮结果， min_index=3，只需要从位置2开始寻找） 1 2 4 3（4 > 3， 所以min_index=4） 1 2 3 4（第3轮结果，将3和4交换，也就是位置4和位置3交换） 至此，排序完毕。
代码如下：
#include<iostream> using namespace std; void selectSort(int arr[],int len) { int temp; if (len == 0 || len == 1) { return; } for (int i = 0; i < len - 1; i++) { int min = i; for (int j = i + 1; j < len; j++) { if (arr[j]<arr[min]) { min = j; } } if (min != i) { temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } } int main() { int arr[] = { 2, 1, 3, 5, 4, 6, 7 }; int len = sizeof(arr) / sizeof(arr[0]); selectSort(arr,len); for (int i = 0; i < len; i++) { cout << arr[i]; } system("pause"); } 选择排序优化：最大最小值同时找出来放到相应的位置
代码如下：
#include<iostream> using namespace std; void selectSort(int arr[], int len) { int min, i, max, left, right; int temp; for (left = 0, right = len - 1; left < right; left++, right--) { min = left; max = right; for (i = left; i <=right; i++) { if (arr[i] < arr[min]) { min = i; } else if (arr[i]>arr[max]) { max = i; } } if (min != left) { temp = arr[left]; arr[left] = arr[min]; arr[min] = temp; //注意！！！，因为此时下标不变，仅仅值交换，如果最大值在最左边， //肯定要被移走，此时最大值的下标变成了min if (max ==left) { max = min; } } if (max != right) { temp = arr[right]; arr[right] = arr[max]; arr[max] = temp; } } } int main() { int arr[] = {0, 3, 4, 1, 2, 8, 6, 5, 1,0 }; int len = sizeof(arr) / sizeof(arr[0]); selectSort(arr, len); for (int i = 0; i < len; i++) { cout << arr[i] << endl; } system("pause"); }
