vlambda博客
学习文章列表

• 属于  比较算法 ^[1]
• 英文简写： SEL
  

关注、评论、转发

定义

给定 N 个项目和 L = 0 的数组，选择排序将：

1. 在 [L ... N-1] 范围内找出最小项目 X 的位置，
2. 用第 L 项交换X
3. 将下限 L 增加1并重复步骤1直到 L = N-2。

我们也可以实现反向的选择排序：找到最大项目 Y 的位置并将其与最后一个项目交换。

// C++ 正向选择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 可能等于 L (无实际交换) }}

举个例子🌰：[29,3,10,14,5,37,14]
第一次选择：[3,29,10,14,5,37,14]
第二次选择：[3,5,10,14,29,37,14]
第三次选择：[3,5,10,14,29,37,14]
第四次选择：[3,5,10,14,14,37,29]
第五次选择：[3,5,10,14,14,29,37]

时间复杂度

跟冒泡排序类似，总时间= c * N *（N-1）/ 2 = O（N^2）

小测试

对数组[29, 10, 14, 37, 13] 用选择排序算法，需要交换几次？
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
答案：3 次。

参考资料