Sorting
Java for AP CS A Lesson 14 1:56 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Selection sort works by finding the smallest value in the unsorted part and swapping it to the front.
选择排序的做法，是在还没排好的那部分里找出最小的值，把它换到最前面。
Start with seven, three, nine, two, five.
从 7、3、9、2、5 开始。
Smallest is two, so swap it to the front.
最小的是 2，就把它换到最前面。
Then the smallest of what is left, then the next.
然后是剩下部分里最小的，再下一个。
Watch the green grow from the left.
看绿色从左边一点点长出来。
The key property: after each pass, one more item is in its final place and will never move again.
关键性质是：每一轮之后， 就多一个元素落到了它"最终"的位置上，再也不会动了。
Insertion sort works the other way round.
插入排序反过来做。
Take the next item and slide it back through the sorted part until it fits.
拿下一个元素，让它在已经排好的那一段里往回滑，直到位置合适。
Three slides back past seven.
3 往回滑，越过 7。
Nine is already bigger, so it stays.
9 本来就更大，所以留在原地。
Two slides all the way to the front.
2 一路滑到最前面。
Five slides back past nine and seven.
5 往回滑，越过 9 和 7。
The green part on the left was sorted all along — it just gets one longer each pass.
左边那段绿色一直都是有序的—— 只是每一轮变长一个。
Both end up sorted, but the exam asks what the array looks like AFTER a given pass, and there the two differ.
两种最后都排好了， 但考试问的是"某一轮之后数组长什么样"， 而在这一点上两者是不同的。
With selection sort, the first k items are in their final places.
选择排序做完 k 轮，前 k 个元素在它们的"最终"位置上。
With insertion sort, the first k items are sorted among themselves, but a later item may still move into that region.
插入排序做完 k 轮，前 k 个元素彼此之间有序， 但后面的元素还可能挤进这一段里来。
Both are slow on big arrays; merge sort splits the array in half, sorts each half and merges them, which is far faster.
两种在大数组上都慢； 归并排序把数组对半分开，各自排好再合并，那要快得多。
Four things to take with you.
带走四点。
One: selection sort puts one item in its final place per pass.
第一：选择排序每一轮把一个元素放到最终位置。
Two: insertion sort grows a sorted prefix.
第二：插入排序让有序的前缀不断变长。
Three: the exam asks for the array after a given pass.
第三：考试问的是某一轮之后的数组。
Four: merge sort splits, sorts and merges, and beats both.
第四：归并排序先分、再排、再合并，比这两种都快。
Now trace the sorts in the tasks below.
现在去下面的题里把这两种排序追踪一遍。