Sorting
C Programming Lesson 13 2:29 English narration · English + 中文 subtitles burned in
Chapters
Transcript
Every sort in this lesson is built on one small move: exchanging two items.
这一课里的每一种排序，都建立在一个小动作上：交换两个元素。
And you cannot do it in two lines, because a box only holds one thing.
而你不能用两行做到，因为一个盒子只装得下一个东西。
You have to save one of them somewhere first — that is the temporary.
你必须先把其中一个存到别处——那就是临时变量。
Skip the temporary and watch what happens.
去掉临时变量，看看会发生什么。
The first line copies the second value over the first, and the value you were about to move is gone.
第一行把第二个值盖到第一个上， 而你正要搬走的那个值没了。
Now the array holds the same value twice.
现在数组里同一个值出现了两次。
Bubble sort only ever looks at neighbours.
冒泡排序永远只看相邻的两个。
Compare the first two: five and two are the wrong way round, so swap them.
比较头两个：5 和 2 顺序反了，交换。
Move along to the next pair.
往前挪到下一对。
Five and eight are already fine, so leave them.
5 和 8 已经没问题，放着不动。
Then eight and one — swap.
然后是 8 和 1——交换。
Watch what that did to the eight: it was compared, moved, compared again, and carried to the end of the array.
注意这一路对 8 做了什么：它被比较、被移动、又被比较， 最后被一直带到了数组的末尾。
One pass always parks the largest value in its final place.
一趟下来，最大的值总会停在它最终的位置上。
Repeat the pass and the next largest follows.
再来一趟，第二大的也就跟着到位了。
Insertion sort works the way people sort cards in their hand.
插入排序的做法，就是人整理手里扑克牌的做法。
Treat the left part of the array as already in order — at the start that is just the first item, which trivially is.
把数组左边那一段当作已经有序的—— 一开始它就是第一个元素，那当然是有序的。
Then take the next one and call it the key.
然后取下一个，把它叫做“key”。
Shift the bigger ones in the sorted part to the right, one at a time, until you find the gap where the key belongs, and drop it in.
把有序部分里比它大的元素依次往右挪一格， 直到找到 key 该待的空位，把它放进去。
The sorted part has grown by one, and you repeat.
有序部分长了一格，然后重复。
Before you run the checker, test your own sort on four arrays.
在跑检查器之前，先拿四种数组测试你自己的排序。
An ordinary jumble, obviously.
一个普通的乱序数组，这是当然的。
An array that is already sorted — a bad loop bound often reverses one of those.
一个已经排好序的数组——循环边界写错时，常常会把它弄反。
Negative numbers, because a comparison written the wrong way round still looks right on positives.
带负数的，因为比较写反了，在全是正数时看着仍然是对的。
And one with the same value twice, to be sure neither copy disappears.
还有一个含有重复值的，确认两份都没有消失。
That is exactly the set the checker uses.
检查器用的正是这一组。
Four things to take with you.
带走四点。
One: a swap needs a temporary, or a value is lost.
第一：交换需要一个临时变量，否则会丢值。
Two: bubble sort compares neighbours, pass after pass.
第二：冒泡排序比较相邻元素，一趟接一趟。
Three: insertion sort grows a sorted left-hand side.
第三：插入排序让左边的有序部分不断变长。
Four: all three of these are n squared, so they are fine for a class exercise and far too slow for a million items.
第四：这三种都是 O(n²)， 所以拿来做课堂练习没问题，处理一百万个元素就太慢了。
Now write the swap, then build both sorts on top of it.
现在先写交换，再在它上面搭出两种排序。