关于选择排序并去重的几种算法分析
说在前面
选择排序是选考VB算法中最重要的排序算法之一（另一个是冒泡排序），它不仅出现在选择题中，还经常出现在大题目中。从备考复习的角度来说，我们不仅要求学生掌握选择排序的基本算法思想和代码结构，还要融会贯通，理解它的一些变例拓展。
选择排序并去重，是其典型变例，代码实现复杂多变，值得细细研究。本文是笔者近段时间的专题复习内容，整理归纳后分享给大家，希望能对你有所启发。由于笔者水平有限，表述难免存在不严谨之处，还请各位老师批评指教。
经典例题：
算法分析：
（一） 夯实基础
经典选择排序算法代码实现及说明
Private SubCommand1_Click() ‘算法1
Dim i As Integer, j As Integer, k AsInteger, t As Integer
For i = 1 To n - 1
k = i
For j = i + 1 To n 'k记录当前最小值的位置
If a(j) < a(k) Then k = j
Next j
If i <> k Then '将最小值与a(i)交换
t = a(k): a(k) = a(i): a(i) = t
End If
Next i
End Sub
经典选择排序算法为长度为n的数组a排序时，总共需要排序n-1趟（只剩下一个元素时无需再排序），外层循环变量i既可以表示排序的趟数，也可以理解成待排序区间的左边界。本算法的巧妙之处在于派出了一个侦察兵k（也可以理解成变量i的替身），联合内层循环变量j，通过扫描待排序区间，找到最小元素的位置，并用k指向它；内层循环结束后，比较i和k的值，若不相等，则交换a(k)和a(i)，即把最小元素交换到待排序区间的最左端。这样每排序一趟，最多交换次数为1，效率较高。
2.低效选择排序算法代码实现及分析
Private SubCommand2_Click() ‘算法2
Dim i As Integer, j As Integer, t AsInteger
For i = 1 To n - 1
For j = i + 1 To n
If a(j) < a(i) Then '将当前遇到的更小值与a(i)交换
t = a(i): a(i) = a(j): a(j) = t
End If
Next j
Next i
End Sub
与经典选择排序算法相比，低效选择排序算法省略了变量k，代码更为简短。但正是因为缺少了侦察兵k的帮助，幕后主使i只能亲自出马，直接与内层循环变量j接触，并且步步为营，只要找到一个比a(i)小的a(j)，就马上交换二者的值，以确保左边界值最小。这样每排序一趟，都有可能发生多次交换，效率较低。
（二） 例题剖析
本题采用低效选择排序算法对数组a进行排序并去重工作。其中第②空所在代码段用于排序，第③空所在代码段用于去重，每当遇到a(j)与a(i)相等，则删除a(j)，因为无需保持元素之间的相对位置不变，程序直接使用尾元素a(bottom)来覆盖a(j)，以实现删除a(j)的目的，同时让bottom减一。
需要说明的是本题中外层循环使用for语句是不够妥当的，因为bottom的值在程序运行过程中发生了变化，但是VB语言中for循环语句的终值在第一次执行的时候就已经计算出来了，之后即使bottom的值发生变化，但是for循环执行的次数是不会改变的；到了后面有可能出现i>=bottom，但是循环依然还在执行——当然由于此时内层循环条件不满足，内层循环不再执行，所以不会影响程序结果，但有可能给考生带来困惑，最好是把for循环语句改成do循环语句，可读性更强。
答案：(1)B；(2)① Int(Rnd*20) + 1；② a(i) > a(j)；③ a(j) = a(bottom)。
（三） 同类拓展
我们也可以采用经典选择排序算法对数组a进行排序并去重工作，为了增强程序的可读性，我们把外层循环写成do循环语句的形式。
Private SubCommand3_Click() ‘算法3
Dim i As Integer, j As Integer, k AsInteger, t As Integer
Dim bottom As Integer
bottom = n: i = 1
Do While i < bottom
k = i
For j = bottom To i + 1 Step -1
If a(j) < a(k) Then
k = j
ElseIf a(j) = a(i) Then
a(j) = a(bottom)
If k = bottom Then k = j
bottom = bottom - 1
End If
Next j
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
Else '为什么只有当a(i)恰好为最小值时才执行i=i+1
i = i + 1
End If
Loop
End Sub
在算法3中，我们引入了侦察兵k，让k指向最小元素的下标。当a(j)与a(i)相等时，我们使用a(bottom)来覆盖a(j)的值，同时让bottom减一。需要注意的一种特殊情况是，当k 恰好指向bottom时，若用a(bottom)覆盖了a(j)，则需将k指向j，确保k总是指向当前的最小值。内层循环结束后，若k <> i，则交换a(k)和a(i)的值，并保持i的值不变；否则说明a(i)本来就是最小值，可以令i增一。
当然我们也可以从左向右扫描待排序区间进行排序并去重工作，这样保证k<=j，则在用a(bottom)覆盖a(j)时，不用考虑更新k的值；但由于需要重新处理a(j)，故必须保持j原地不动。
Private SubCommand4_Click() ‘算法4
Dim i As Integer, j As Integer, k AsInteger, t As Integer
Dim bottom As Integer
bottom = n: i = 1
Do While i < bottom
k = i: j = i + 1
Do While j <= bottom
If a(j) < a(k) Then
k = j
ElseIf a(j) = a(i) Then
a(j) = a(bottom)
bottom = bottom - 1
j = j - 1 '想想为什么？
End If
j = j + 1
Loop
If k <> i Then
t = a(k): a(k) = a(i): a(i) = t
Else
i = i + 1
End If
Loop
End Sub
算法3和算法4目的都是删除与a(i)相等的元素，共同点是只有当a(i)恰好为最小值时才执行i=i+1；不同点是扫描方向不同，需要考虑的问题也不一样。
除了删除与a(i)相等的元素，我们也可以删除与a(k)相等的元素，这样确保每趟扫描过后，最小元素都只剩下一个，将其交换到最左端以后，可以放心地让i增一。
同样的，我们在内层循环有向左扫描和向右扫描两种方式，代码分别如下：
Private SubCommand5_Click() ‘算法5
Dim i As Integer, j As Integer, k AsInteger, t As Integer
Dim bottom As Integer
bottom = n: i = 1
Do While i < bottom
k = i
For j = bottom To i + 1 Step -1
If a(j) < a(k) Then
k = j
ElseIf a(j) = a(k) Then
a(j) = a(bottom)
If k = bottom Then k = j
bottom = bottom - 1
End If
Next j
If k <> i Then t = a(k): a(k) =a(i): a(i) = t
i = i + 1
Loop
End Sub
Private SubCommand6_Click() ‘算法6
Dim i As Integer, j As Integer, k AsInteger, t As Integer
Dim bottom As Integer
bottom = n: i = 1
Do While i < bottom
k = i: j = i + 1
Do While j <= bottom
If a(j) < a(k) Then
k = j
ElseIf a(j) = a(k) Then
a(j) = a(bottom)
bottom = bottom - 1
j = j - 1
End If
j = j + 1
Loop
If k <> i Then t = a(k): a(k) =a(i): a(i) = t
i = i + 1
Loop
End Sub
综合比较上述选择排序并去重的算法实现，例题所用的算法在排序方面效率较低，但去重效率高（一趟扫描下来能将所有小于a(i)的元素全部去重）；算法3和算法4采用经典选择排序算法，排序效率较高，但每次只能将与a(i)相等的元素去重，去重效率较低；算法5和算法6是笔者推荐的算法，它们的排序效率和去重效率均高于前者，综合得分最高。
（四） 拓展思考
除了选择排序，冒泡排序也是选考VB算法中要求熟练掌握的算法，那么冒泡排序并去重的代码该怎么写呢？
请模仿上述代码，根据经典冒泡排序算法的代码结构，写出一段冒泡排序并去重的代码实现。
（五） 拓展思考答案
Private SubCommand7_Click() ‘算法7
Dim i As Integer, j As Integer, t AsInteger
Dim k As Integer, bottom As Integer
bottom = n: i = 1
Do While i <= bottom - 1
For j = bottom To i + 1 Step -1
If a(j) < a(j - 1) Then
t = a(j): a(j) = a(j - 1): a(j- 1) = t
ElseIf a(j) = a(j - 1) Then
a(j) = a(bottom)
bottom = bottom - 1
End If
Next j
i = i + 1
Loop
End Sub
为了保证解析的原创性和思维的独特性，我都是独立解题后，先不看答案(除非题目不会做)，直接把解析写好，再去看答案。
当然，如果发现参考答案有更好的思路，我还是很乐于学习和借鉴的。同时，由于本人水平有限，解析中难免出现疏漏甚至错误之处，敬请谅解。
无论是赞同还是反对我的看法，都请你给我留言。如果你有新的想法，千万不要憋在心里，请发出来大家一起讨论。让我们相互学习，共同进步！
需要本文word版的，可以加入“选考VB算法解析”知识星球参与讨论和下载文件，“选考VB算法解析”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注选考VB算法，感兴趣就一起来！
相关优秀文章：