排序的概念

外部排序很難，后面都是內部排序?

插入排序

直接插入排序

理解

這個排序第一輪是從第二個元素開始的

然后是從后往前一個一個比的

然后我們看i=5的情況，會出現比較次數和移動次數的概念，這里97動了

然后i=8時，49最好放在相同的后面，這樣就可以穩定了

這個算法會有n-1趟

然后第n趟會有n+1個有序，比如第二趟i=3時會有3個元素有序

這是最壞情況，可以看見第一趟移動和比較都是1次，第二趟2次，第三趟3次

也就是這么多次移動和比較

折半插入排序

理解

前面不是已經是有序的嗎，所以用折半多爽啊

直接是從后往前比，而折半是折半查找比，這里查找順序是65，49，38

題目

d

希爾排序

理解

下面增量d=5

然后每組之間排序?也可以直接豎著寫，這樣更快

然后是增量為3

然后豎著寫，這樣更快，結果：

那增量怎么取？

沒錯，最后一個是增量是d=1就行

這就是傳說中的

?鏈表不太行啊

題目

1

2

我們先看d=3行不行

一會升序一會降序，所以不是3

然后看d=5可以發現每一組都是有序的，而且必須每一組都是有序的，所以一定要豎著寫下來

然后根據第一趟看第二趟的就行了

d

交換排序

冒泡排序

理解

怎么去做呢，看好了

49 和 27 比，小的在上，大的在下，很好，過

27 和 13 比，小的在上，大的在下，很好，過

13 和 76 比，小的在下，大的在上，不好，交換！

。。。就這樣一直比下去就行，就是1輪

第一輪比較了n-1次，并且13已經確定好了

第二輪比較了n-2次，并且27已經確定好了

。。。

然后會有這個規律

然后注意

最好情況就比較了1次

快速排序

理解

這是規矩

快排的目的是小的放左邊，大的放右邊

這里6作為樞軸（pivot），從7往左比較

然后比較一下7，沒問題，是大于6的，太好了，很舒服，不錯，繼續保持，加油

然后比較一下4，wait，wait，wait，what the HELLLLL！WAAZZZAAAA！是小于6的

然后會發生很多事情

4先到樞軸上去，6往后找比它大的，找到了9

然后把9放到4那里，9的地方就存儲6

然后神奇的事情發生了，6變成了我們想要的樣子，左邊小于6，右邊大于6，6這個位置已經確定了

然后就是算法大師最喜歡的分治法

左右兩邊都處理是第二趟，左右兩邊都進行快排

先看左邊

，這里4是樞軸，然后從5開始往右

5沒事

1有事，小于4，先把1到樞軸，然后樞軸的指針往后移動開始找比它大的數，最后發現與右指針相遇，于是只能把4放到那里

再看右邊

這里8是樞軸，然后從7開始往右

7有事，小于8，先把7到樞軸，然后樞軸的指針往后移動開始找比它大的數，發現個9，9到7那里，8插入到里面來

然后不用第三趟了，因為左右兩邊就1個元素

然后每次會有logn趟，每趟是n

所以時間復雜度Onlogn

最差情況下是有序的情況，時間復雜度達到On^2

比如這里，1要找比它小的，找了n-1次，沒找到，向右的指針會到1這里，1確定了，然后樞軸指針往后移動變成2，再來一次，找了n-2次，就這樣，當然別固化死了，這里樞軸不一定要是第一個，也可以是中間的4，但說到底只有一個樞軸。

鏈表還是不行

做題

1

d 不解釋?

2

?

?這里是樞軸產生的三種情況，可以注意到d選項，

12如果是第一趟的樞軸，那應該左右兩邊都有才對，然而并不是左右，這里只有一個32

?

?然后我們看看A選項

這里我們那72當第一趟，那28作為下一趟就合理了

3

這里，最少最少得有2個樞軸，而C選項只有1個9

B選項是9和2是樞軸

c