假设：你的电脑里存储了很多乐曲。对于每个乐队，你都记录了其作品被播放的次数。
| 乐队名称 | 播放次数 |
|---|---|
| PADIOHEAD | 156 |
| KISHORE KUMAR | 141 |
| THE BLACK KEYS | 35 |
| NEUTRAL MILK HOTEL | 94 |
| BECK | 88 |
| THE STROKES | 61 |
| WILCO | 111 |
将这个列表安播放次数从多到少顺序排列？
选择排序
一种办法是遍历这个列表，1)找出作品播放次数最多的乐队，并将其添加到一个新列表中；2)继续这样做，找出播放次数第二多的乐队；3)一直重复这个步骤，知道得到一个有序的列表。
那么这个方法需要多长的时间呢？需要的总时间为O(n 2 )。
第一次需要检查n个元素，随后依次为n-1,n-2···2和1.平均每次检查的元素为1/2xn，因此运行时间为O(nx1/2xn)。但是大O表示法省略常数，因此需要的总时间为O(n 2 )。
选择排序是一种比较容易理解的算法，但是速度并不快。快速排序使一种更快的算法，接下来让我们看一看。
-------------------------------------- 未完待续 --------------------------------------
网友评论