【算法】选择排序和快速排序

假设：你的电脑里存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。

将这个列表安播放次数从多到少顺序排列？

选择排序

一种办法是遍历这个列表，1)找出作品播放次数最多的乐队，并将其添加到一个新列表中；2)继续这样做，找出播放次数第二多的乐队；3)一直重复这个步骤，知道得到一个有序的列表。
那么这个方法需要多长的时间呢？需要的总时间为O(n ² )。
第一次需要检查n个元素，随后依次为n-1,n-2···2和1.平均每次检查的元素为1/2xn，因此运行时间为O(nx1/2xn)。但是大O表示法省略常数，因此需要的总时间为O(n ² )。

选择排序是一种比较容易理解的算法，但是速度并不快。快速排序使一种更快的算法，接下来让我们看一看。

-------------------------------------- 未完待续 --------------------------------------