选择排序以及对它的优化

3/8/2017来源:ASP.NET技巧人气:1646

选择排序 八大排序算法之一的选择排序,它的原理是比较容易理解的。 每一趟遍历都在后面元素中找到最小的元素(升序),记录它的下标,一趟走完后,如果记录的元素下标不等于这组元素第一个元素则进行交换。 我们可以配合图来看: 这里写图片描述

还另外加了升序和降序的仿函数,这样可以更加实用一些 下面是实现代码:

template<class T> struct Less { bool Operator()(const T& s, const T& l) { return s < l; } }; template<class T> struct Greater { bool operator()(const T&s, const T& l) { return s > l; } }; using namespace std; template<class T = int, class Compare = Greater<T>> void SelectSort(T* arr,int size) { Compare com; for (int i = 0; i < size - 1; i++) { int k = i; for (int j = i + 1; j < size; j++) { if (com(arr[k], arr[j])) k = j; } if (k != i) std::swap(arr[i], arr[k]); } } void SelectTest() { int arr[] = { 3, 4, 1, 5, 2 }; SelectSort(arr, sizeof(arr) / sizeof(arr[0])); } 这样最基本的选择排序就出来了,但是仔细想想我们一次选一个最小的数进行交换,那我们为什么不能每趟遍历选出最大和最小的,最大的和最后交换,最小的和前面交换,这样效率会更高一些,这样想,于是对代码进行优化改良,就有了下面优化版本的选择排序。

2. 选择排序优化

using namespace std; template<class T> struct Less { bool operator()(const T& s, const T& l) { return s < l; } }; template<class T> struct Greater { bool operator()(ctonst T&s, const T& l) { return s > l; } }; template<class T = int, class Compare = Greater<T>> void SelectSort(T* arr, int size) { Compare com; int left = 0; int right = size - 1; for (; left <= right;left++,right--) { int min = left; int max = right; for (int i = left; i <= right; i++) { if (com(arr[min],arr[i])) min = i; if (com(arr[i],arr[max])) max = i; } swap(arr[max], arr[right]); if (min == right) min = max; swap(arr[min], arr[left]); } } void SelectTest() { int arr[] = { 3, 4, 1, 5, 2 }; SelectSort(arr, sizeof(arr) / sizeof(arr[0])); }

最后,分析一下选择排序的时间复杂度,选择排序的时间复杂度是O(n^2)。 因为需要选择,所以无论什么情况都是要把为排序序列完整的遍历一遍才可以,所以选择排序的时间复杂度最好的时候也是O(n^2)。