Question

选择排序与快速排序

Answer 1

假设你记录了你的听歌次数，你想要排序，看看自己最喜欢哪个乐队

选择排序的方法，就是遍历你的列表。找出次数最多的那条记录，然后添加到新列表中。

看看需要多长时间 ：O(n)时间意味着查看列表中的每个元素一次，例如，对乐队列表进行简单查找时，意味着每个乐队都要查看一次。

快速排序是一种常用的排序算法，比选择排序快得多。例如，C语言标准库中的函数qsort实现的就是快速排序。快速排序也使用了 D&C 。

首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。接下来，找出比基准值小的元素以及比基准值大的元素。

于是，我们现在有

再将子数组进行快速排序，最终可以得到结果。
快速排序的独特之处在于，其速度取决于选择的基准值。（ 不同的基准值会有不同的排序过程，选择合适的基准值也很重要 ）