【排序算法】什么是选择排序？

mac2022-06-30 36

文章目录

一：定义二：原理三：动态图演示四：C# 代码实现五：选择排序和冒泡排序的对比六：为什么要用选择排序？七：多种编程语言实现选择排序（参考）1：Java2：JavaScript3：Python4：PHP5：GO

一：定义

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度，所以用到它的时候，数据规模越小越好。

二：原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复第二步，直到所有元素均排序完毕。

三：动态图演示

四：C# 代码实现

namespace AlgorithmTest { class Program { static void Main(string[] args) { // 定义一个长度为12的数组 int[] array = new[]{ 3, 8, 15, 48, 2, 14, 21, 13, 56, 32, 33, 16 }; SelectSort(array); Console.ReadKey(); } static void SelectSort(int[] array) { for (int i = 0; i < array.Length-1; i++) { int minIndex = i; // 最小元素的下标 for (int j = i+1; j < array.Length; j++) { //记录最小值下标 minIndex = array[minIndex] < array[j] ? minIndex : j; } // 交换位置 int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } // 打印结果 foreach (var item in array) { Console.Write(item + " "); } } } }

控制台输出结果如下所示由以上代码我们可知

外层循环控制执行轮数，循环的轮数等于元素的个数 - 1。每一轮中找出无序区域的最小元素，并且把这个最小元素和无序区域的第一个元素交换。

五：选择排序和冒泡排序的对比

1）交换次数的对比

以 { 3, 8, 15, 48, 2, 14, 21, 13, 56, 32, 33, 16 } 这组数据来说，选择排序和冒泡排序分别交换了多少次呢？这里我另外补充了代码用来显示执行结果，如下所示可见，就该数组而言，选择排序要比冒泡排序交换次数要少，是不是就说明选择排序要比冒泡排序的效率更高呢？

答案是否定的，其实不管是排序算法还是其它，都有其"存在即合理"的说法，只不过我们自己要根据不同的场景，选择合适的才是最好的。

2）稳定性对比

冒泡排序虽然存在一定的性能缺陷，但却是一个稳定的排序。

反观选择排序，虽然性能会好点，但是排序具有不稳定性，为什么这样说呢？当数列包含多个值相等的元素时，选择排序有可能打乱它们的原有顺序。

接下来举一个例子说明，如下图所示上图中，绿色的5 原本排在橙色的5 之前，但是随着第一轮元素3 和绿色5 的交换，使得后续操作中，绿色的5 排在了橙色的5 之后，所以说选择排序具有不稳定性。

六：为什么要用选择排序？

举个简单的实际例子

假设现在有10个人，每个人的身高不一样，需要你按身高从低到高，自左向右排序。

思路一：冒泡排序如果你用冒泡排序，假设左边第一个人的身高是最高的，但你还是要先让他和他右边的人交换位置，然后依次类推，一直让他排到最右边，如果现实中你这样做，恐怕脑子真的是冒泡了。所以此时选择冒泡排序是不合适的。

思路二：选择排序针对上述情况，如果用选择排序，我们只需要在每一次中找到个子最高的那个人，直接交换到队伍的最右边，这样一来，只需要很少的交换次数就可以完成队伍的排序。

选择排序最大的优势就是省去了多余的元素交换、

七：多种编程语言实现选择排序（参考）

1：Java

public class SelectionSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 总共要经过 N-1 轮比较 for (int i = 0; i < arr.length - 1; i++) { int min = i; // 每轮需要比较的次数 N-i for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } return arr; } }

2：JavaScript

3：Python

def selectionSort(arr): for i in range(len(arr) - 1): # 记录最小数的索引 minIndex = i for j in range(i + 1, len(arr)): if arr[j] < arr[minIndex]: minIndex = j # i 不是最小数时，将 i 和最小数进行交换 if i != minIndex: arr[i], arr[minIndex] = arr[minIndex], arr[i] return arr

4：PHP

5：GO

func selectionSort(arr []int) []int { length := len(arr) for i := 0; i < length-1; i++ { min := i for j := i + 1; j < length; j++ { if arr[min] > arr[j] { min = j } } arr[i], arr[min] = arr[min], arr[i] } return arr }

声明：一：博文中用到的动态效果图，录取自 vx 公众号《五分钟学算法》以及《程序员小灰》，对算法感兴趣的可以关注下。二：文章思路开源项目地址，整理人 hustcc

结束语

如果这篇博客有幸帮到了您，欢迎点击下方链接，和更多志同道合的伙伴一起交流，一起进步。

最新回复(0)

【排序算法】什么是选择排序 ？