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

【数据结构】排序算法系列——选择排序（附源码+图解）

news 2025/6/23 11:27:06

选择排序

算法思想

选择排序的思想与插入排序其实有异曲同工之处，它们都会对数据进行比较和交换，但是它们也还是有很大的差别：插入排序是两两元素之间进行比较，而选择排序是将最值的元素同其他元素依次进行比较，从而按照最大（或最小）、第二大、第三大这样的顺序进行数组的重组。

它的大致步骤如下：

第一次从待排序的数据元素中选出**最小（或最大）**的一个元素，存放在序列的起始(末尾)位置
然后选出**次小(或次大)**的一个元素，存放在最大(最小)元素的下一个位置
重复这样的步骤直到全部待排序的数据元素排完

图解

请添加图片描述

C语言代码分析

//选择排序
void SelectSort1(int* a, int n);
void SelectSort2(int* a, int n);//1.只进行最小值或者最大值的交换
void SelectSort1(int* a, int n)
{int left = 0;int right = n - 1;while (left < right){int min = left;//指定目前最小值为第一个元素for (int i = left + 1; i <= right; i++){if (a[i] < a[min])//如果有比目前最小值更小的元素，就更新最小值，进行交换{min = i;}}if (min != left)//如果最小值不是第一个元素，就进行Swap交换{int temp = a[min];a[min] = a[left];a[left] = temp;}left++;//每完成一次交换，左指针向右移动一位，进行下一次交换}
}//2.最小值和最大值同时进行交换，优点是减少了交换次数，在一定程度上提高了效率
void SelectSort2(int* a, int n)//选择排序
{int left; int right = n - 1;//左右指针while (left < right){int min = left, max = right;//最小值和最大值的下标for(int i=left+1;i<=right;i++){if (a[i] < a[min])//找最小值min = i;if (a[i] > a[max])//找最大值max = i;}if (min != left){//进行一次Swap交换int temp = a[min];a[min] = a[left];a[left] = temp;}//如果最大值和最小值相等，说明最大值和最小值是同一个元素，只需要进行一次交换//如果继续交换max，就会将最小值交换到末尾位置。if (left = right){right = min;}left++;right--;}