【数据结构】——直接选择排序

本文主要是介绍【数据结构】——直接选择排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言：在之前文章当中，我们了解过了堆排序，而堆排序是属于选择排序的一种，下面我们将继续了解直接选择排序。

堆排序的链接：堆排序以及向上、向下调整算法的时间复杂度推导及实现（超详细）-CSDN博客

选择排序

选择排序的基本思想：每⼀次从待排序的数据元素中选出最小（或最大）的⼀个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

直接选择排序

1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(小)的数据元素

2. 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换

3. 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

下面是直接选择排序的动态示意图

//方法一
void SelectSort(int* arr, int n)
{for (int i = 0; i < n; i++){int mini = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[mini]){mini = j;}}Swap(&arr[i], &arr[mini]);}
}//方法二优化之后
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}if (maxi == begin){maxi = mini;}Swap(&arr[mini], &arr[begin]);Swap(&arr[maxi], &arr[end]);++begin;--end;}
}

方法一类似于冒泡排序，所以运行效率相对来说很低。