5.排序算法之二：选择排序

选择排序（select sort）

在无序列表中，把无序列表分成有序区（刚开始有序区元素个数为0）和无序区（刚开始无序区元素个数为n），循环n-1趟，每一趟找到最小或最大的那个元素，并把最小或最大的那个元素放在有序区，此时有序区元素个数加1，无序区元素个数减1，直到循环n-1趟后，列表都已排序好，此时，有序区的元素个数为n，无序区元素个数为0。

代码关键点分析：

总趟数（n-1）

无序列表：arr[n] = {val0, val1, ..., val(n-1)};

1. n = 1时，即无序列表只有1个元素，只要进行比较0趟

2. n = 2 时，即无序列表有2个元素，只要进行比较1趟

3. n = 3 时，即无序列表有3个元素，只要进行比较2趟

4. n = n 时，即无序列表有n个元素，只要进行比较 n - 1 趟

每一趟下标最大值为(n-1)

代码：

#include <iostream>using namespace std;template<typename T>
void select_sort(T *arr, int n)
{int min_key;T temp;for (int i = 0; i < n-1; i++) //总趟数n-1{min_key = i;    for (int j = i+1; j < n; j++) //每一趟下标的最大值为n-1{if (arr[j] < arr[min_key])min_key = j;}if (min_key != i){temp = arr[i];arr[i] = arr[min_key];arr[min_key] = temp;}}
}int main(int argc, char *argv[])
{int arr[] = {3,5,2,1,4};int n = sizeof(arr)/sizeof(*arr);cout << "---before select sort---" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;select_sort(arr, n);cout << "---after select sort---" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

结果：

时间复杂度：O()

选择排序算法，外循环对总趟数进行循环，内循环对每一趟进行循环，所以，算法时间复杂度为：O()

算法稳定性：不稳定

选择排序算法是不稳定的排序算法，因为每次都是在未排序的元素列中，找到最小的那个元素，放到已排序的元素列的末尾，可能会调换两个相等元素的先后位置，那么原序列中两个相等元素的先后顺序就破坏了，所以选择排序算法是不稳定的排序算法。比如{3,3,1,2}，第一趟排序中，首位置的3和第3个位置的1进行互换，得到的{1,3,3,2}，最开始的首位置的3和第2位置的3的先后位置就破坏了。