选择排序
选择排序(selection sort)是一种原地(in-place)排序算法，适用于数据量较少的情况。由于选择操作是基于键值的且交换操作只在需要时才执行，所以选择排序长用于数值较大和键值较小的文件。
思想：对一个数组进行排序，从未排序的部分反复找到最小的元素，并将其放在开头。
给定 N 个项目和 L = 0 的数组，选择排序将：
- 寻找序列中的最小值。在 [L ... N-1] 范围内找出最小项目 X 的位置，
- 用当前位置的值交换最小值。第 L 项交换X，
- 对所有元素重复上述过程，直到整个序列排序完成。将下限 L 增加1并重复步骤1直到 L = N-2。
伪代码：
void selectionSort(int a[], int N) { for (int L = 0; L <= N-2; ++L) { // O(N) int X = min_element(a+L, a+N) - a; // O(N) swap(a[X], a[L]); // O(1), X may be equal to L (no actual swap) }}
动画演示
Go 代码实现
package mainimport "fmt"func main() { unsorted := []int{40, 13, 20, 8, 12, 10, 27} length := len(unsorted) selectionSort(unsorted, length) for i := 0; i < length; i++ { fmt.Printf("%d\t", unsorted[i]) }}func selectionSort(nums []int, length int) { var minIdx int // 被选择的最小的值的位置 for i := 0; i < length-1; i++ { minIdx = i // 每次循环的第一个元素为最小值保存 var minValue = nums[minIdx] for j := i; j < length-1; j++ { if minValue > nums[j+1] { minValue = nums[j+1] minIdx = j + 1 } } // 如果最小值的位置改变，将当前的最小值位置保存 if i != minIdx { var temp = nums[i] nums[i] = nums[minIdx] nums[minIdx] = temp } }}
运行结果：
[Running] go run "e:\Coding Workspaces\LearningGoTheEasiestWay\Go 数据结构\选择排序\main.go"8 10 12 13 20 27 40
总结
选择排序的优点：
- 易于实现，原地排序(不需要额外的存储空间)
缺点：扩展性较差，时间复杂度为
评论（0）