当前位置：首页 > news >正文

八大排序之选择排序

news 来源：原创 2025/7/16 21:51:06

本篇文章将带你详细了解八大基本排序中的选择排序

（一）选择排序的时间复杂度和空间复杂度及稳定性分析

（二）代码实现

(三)输出结果

选择排序的基本原理是：每次从待排序的数组中找出最大值和最小值。具体流程是：每次找出最大值和最小值之后，把最大值和数组的右边界互换，把最小值和数组的左边界互换。这样，第一次找出的最大值和最小值就被放好了。然后由于数组的左右边界已经在正确的位置了，所以我们把左边界加1，右边界-1.这样新的数组仍然是待排序的数组，然后由此类推，直到左边界大于右边界为止。这里附上GIF动图。

（一）选择排序的时间复杂度和空间复杂度及稳定性分析

我们以每次选出最大值或最小值的简单选择排序来分析。

当数组有序时，选择排序仍要遍历整个数组，然后从中选出最值放在边界。这里的时间复杂度是O（N）。重复上述过程，整个排序的时间复杂度就是O（N方）了。
同理，当数组无序时，也同样是当数组有序时的处理，所以时间复杂度也是O（N方）

至于空间复杂度

整个排序没有多余的空间产生，所以空间复杂度是O(1)

稳定性分析

每次选出的最大值和最小值，并不能保持在相同大小的相对位置。所以选择排序是不稳定的排序

（二）代码实现

//选择排序的实现。我们每次选出最大值或最小值，分别与数组的两个边界互换。void Select(int* arr, int n)
{//形参列表的arr是待排序数组，n是数组的大小//开始的边界就是数组的左右边界int begin = 0;int end = n - 1;//n-1是数组最后一个元素的下标while (begin < end){//进入循环//找到最大值和最小值int maxi = begin;int mini = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;  }if (arr[i] < arr[mini]){mini = i;}}//找到最大值和最小值后，与数组边界交换//这里注意的是当待排序数组只有两个时，并且最大值是下标是前一个，最小值的下标是后一个时//交换了2次就等同于没有变。//所以我们得防止这样的情况if (maxi == begin){maxi = mini;}//我们写一个下标交换函数    Swap(&arr[begin]. &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}   
}int main()
{//产生无序数组int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);//n是数组的大小Select(arr, n);}

（一）选择排序的时间复杂度和空间复杂度及稳定性分析

（二）代码实现

(三)输出结果

相关文章：