C# 选择排序

栏目总目录

---

概念

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（或最大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

原理

选择排序的基本思想是：第1趟，在待排序记录r1 ~ rn中选出最小的记录，将它与r1交换；第2趟，在剩下的记录r2 ~ rn中选出最小的记录，将它与r2交换；以此类推，第i趟在剩下的记录ri ~ rn中选出最小的记录，将它与ri交换，直到整个序列有序。

好处与不足

好处

1. 稳定性：虽然选择排序本身不是稳定的（因为交换元素时可能破坏相等元素的相对顺序），但在某些特定实现中可以通过记录索引来保证稳定性，尽管这会增加实现的复杂度。
2. 简单直观：算法逻辑清晰，容易理解和实现。
3. 对输入数据不敏感：无论输入数据是否部分有序，选择排序的时间复杂度都是固定的。

不足

1. 效率低：选择排序的时间复杂度为O(n^2)，在处理大数据集时效率较低。
2. 数据移动：选择排序在找到最小（或最大）元素后需要进行交换，这可能会涉及到大量数据的移动。

应用场景

选择排序由于其简单性，在数据量不大或对数据稳定性要求不高的情况下可以使用。然而，在数据量较大或对数据排序效率有较高要求时，通常不会选择选择排序。

示例代码

基本实现

public void SelectionSort(int[] arr)
{int n = arr.Length;for (int i = 0; i < n - 1; i++){// 找到[i, n)区间里的最小值的索引int minIndex = i;for (int j = i + 1; j < n; j++){if (arr[j] < arr[minIndex]){minIndex = j;}}// 将找到的最小值交换到前面int temp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = temp;}
}

泛型实现

为了增加代码的复用性，我们可以使用泛型来实现选择排序，使其能够排序任何实现了IComparable<T>接口的类型。

public void SelectionSort<T>(IList<T> list) where T : IComparable<T>
{int n = list.Count;for (int i = 0; i < n - 1; i++){int minIndex = i;for (int j = i + 1; j < n; j++){if (list[j].CompareTo(list[minIndex]) < 0){minIndex = j;}}T temp = list[minIndex];list[minIndex] = list[i];list[i] = temp;}
}

总结

选择排序是一种简单直观的排序算法，它通过不断选择剩余元素中的最小（或最大）元素来逐步构建有序序列。尽管其时间复杂度较高，但在数据量不大或对排序效率要求不高的情况下，选择排序仍然是一个可行的选择。通过理解选择排序的原理和特性，我们可以更好地选择和使用适合特定场景的排序算法。