选择排序【详解】

2024/10/27 14:42:49 来源：https://blog.csdn.net/m0_66769266/article/details/141460442 浏览: 次关键词：选择排序【详解】

在这里插入图片描述

本期介绍🍖
主要介绍：排序中的选择排序。

文章目录

1. 前言
2. 选择排序
3. 优化选择排序

1. 前言

相信只要接触过C语言的同学都或多或少了解排序问题，其中最基本，且最为人所熟知的排序是：选择排序。下面我会带着大家重新把这种排序方法走一遍，使你能够透彻的理解这两种算法的原理，能把它们清晰的区分开，并且分别实现这两种排序的算法优化。

2. 选择排序

在这里插入图片描述

选择排序的原理：每趟都从剩余待排序的数组元素种选出最小（或最大）的一个元素，交换存放在这一趟序列的起始位置。选择排序的趟数是由元素个数来决定的，若现在有n个元素要对其进行排序，那只需要进行n-1趟就好了。实现代码如下所示：

//实现选择排序:每次遍历找出数组中最大或最小的值#include<stdio.h>void print(int arr[], int num)
{int i = 0;for (i = 0; i < num; i++){printf("%d ", arr[i]);}
}void select_sort(int arr[], int num)
{//趟数int i = 0;for (i = 0; i < num - 1; i++){//每趟找到最大值的下标int j = 0;int Max = i;int tmp = 0;for (j = i + 1; j < num; j++){if (arr[Max] < arr[j]){Max = j;}}//将最大值放入最前面tmp = arr[i];arr[i] = arr[Max];arr[Max] = tmp;}
}int main()
{int arr[] = { 0,1,2,3,4,5,6,7,8,9 };int sz = sizeof(arr) / sizeof(arr[0]);select_sort(arr, sz);print(arr, sz);return 0;
}

在这里插入图片描述

3. 优化选择排序

选择排序的优化思路一般是在一趟遍历中，同时找出最大值与最小值，放到数组两端，这样就能将遍历的趟数减少一半。过程如下：
在这里插入图片描述

这样每次找出最大值与最小值放到数组两端后，left和right会靠的越来越近。如果还像上边那样执行（n-1）趟的话left和right必然会交错，但这里完全没有必要执行（n-1）趟，因为把left<right的所有情况走完数组就已经有序排列了，完全没有必要把后面left>=right的情况再走一遍。程序如下：

#include<stdio.h>void Swap(int* arr, int x, int y)
{int tmp = arr[x];arr[x] = arr[y];arr[y] = tmp;
}void sel_sort(int* arr, int num)
{int left = 0;int right = num - 1;while (left < right){//先假设最左侧元素的下标未为最小元素的下标，最右侧元素的下标为最大元素的下标。int min = left;int max = right;int i = 0;for (i = left; i <= right; i++){if (arr[i] < arr[min]){min = i;}if (arr[i] > arr[max]){max = i;}}//最大值放在最右端Swap(arr, max, right);//由于上一步把下标（right）和（max）上的数据进行了交换//所以得考虑最小值（arr[min]）在位置（right）的情况，即：此时的 min = right；if (min == right){min = max;}//最小值放在最左端Swap(arr, min, left);//每趟遍历，元素总个数减少2，左右端各减少1，left和right索引分别向内移动1left++;right--;}
}int main()
{int i = 0;int arr[] = { 3,5,9,2,4,7 };int sz = sizeof(arr) / sizeof(arr[0]);//计算数组元素个数sel_sort(arr, sz);//选择排序for (i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}