选择排序以及对它的优化

2019-11-06 06:49:14

字体：大中小

来源：转载

供稿：网友

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

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

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）。

上一篇：leetcode:5. Longest Palindromic Substring

下一篇：mysql常用的sql语句