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

选择排序（C语言实现）

news 2024/9/24 2:30:49

1.基本思想

2.代码实现

代码思路

代码实现

代码测试

3.复杂度分析

1）时间复杂度

2）空间复杂度

4.特性总结

1.基本思想

选择排序是一种简单直观的比较排序算法。该算法的基本思想是在每一轮中选出当前未排序部分的最小（或最大）元素，然后将其放置到未排序序列的起始位置，这个过程一直重复直至整个数组被排序。

2.代码实现

代码思路

★ 从数组的当前未排序部分选择最小（或最大）的一个元素。
★ 将这个最小（或最大）元素与未排序序列的第一个元素交换位置。
★ 然后从剩余未排序的元素中继续这个过程，将每一次找到的最小（或最大）元素放到未排序序列的开始。
★ 这个过程一直进行到整个数组的所有元素都被排为有序状态。

代码实现

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){//找最大和最小下标进行交换int min = begin;int max = begin;for (int i = begin; i <= end; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}//如果最大最初的在首位，那么交换后，就改变了max的位置，无法使end位置为最大Swap(&a[begin], &a[min]);if (max == begin){max = min;}Swap(&a[end], &a[max]);begin++;end--;}}

代码测试

3.复杂度分析

1）时间复杂度

无论数组的初始顺序如何，选择排序都需要比较所有未排序的元素来找到最小（或最大）的元素，并执行这个过程 n-1 次（对于 n 个元素的数组）。每次选择操作需要比较的次数从 n-1 次减少到 1 次，总共的比较次数是 (n-1) + (n-2) + … + 1 = n(n-1)/2，这是一个二次函数，因此时间复杂度为 O(n^2)。