對數器
時間複雜度
是指常數操作的數量級，以冒泡排序為例：
- 第一次在0 - n-1 範圍内找一個最小的數和0位置的數交換，這個過程需要找n次，每次都需要執行取數、比較和交換三個常數操作，是以常數操作需要進行n次
- 第二次在1 - n-1 範圍内找一個最小的數和1位置的數交換，這個過程需要找n-1次，每次都需要執行取數、比較和交換三個常數操作，是以常數操作需要進行n-1次
- 重複上述過程
- 那麼最後常數操作的次數是(n + n-1 + n-2 + … + 1)，這是等差數列，結果為：(n^2/2 + n/2)，注意這是常數操作的次數，而常數操作的時間是O(1)，是以總的時間複雜度是： (n^2/2 + n/2) * O(1)。
遞歸複雜度計算
基于比較的排序
選擇排序
思想：
- 從0 - n-1 位置選一個最小的數放到0位置
- 從1 - n-1 位置選一個最小的數放在1位置
- 直到範圍縮小到n-1
插入排序
思想：
- 想象你在玩撲克牌，剛拿了第一張牌，那麼它自然是有序的
- 現在拿抽第二張牌，你要判斷是否比第一張牌小，若比第一張牌小就将它和第一張牌的順序交換，到目前為止你手中的牌仍然是有序的
- 第三張牌，判斷是否比第二張小，若是則交換它和第二張牌的位置，接着再比較和第一張牌的大小關系，若比第一張牌小就繼續交換，至此已經排好了三張牌
- 重複上述過程
歸并排序
使用master公式來求它的時間複雜度，總的資料量是N，把母問題劃分為兩個子問題，每個執行一次，是以是2 * T(N/2)，除了劃分子問題外，merge的過程時間複雜度為O(N)，故總的時間複雜度為T(N) = 2T(N/2) + O(N)，用master公式，a=2，b=2，d=1 -> O(NlogN)
歸并排序快的實質
冒泡排序、選擇排序等方法一次隻能将一個元素排好位置，但下次排序時沒有利用上次的比較資訊，導緻了重複的比較。
而歸并排序兩個小組合并為大組時進行了比較，但大組和更大的組合并時沒有進行組内的比較，而是組間的比較。
代碼：
public class MergeSort {
public static void mergeSort(int[] arr, int L, int R) {
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
mergeSort(arr, L, mid);
mergeSort(arr,mid+1, R);
merge(arr, L, mid, R);
}
private static void merge(int[] arr, int L, int mid, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int l = L;
int r = mid + 1;
while (l <= mid && r <= R) {
help[i++] = arr[l] <= arr[r] ? arr[l++]: arr[r++];
}
while (l <= mid) {
help[i++] = arr[l++];
}
while (r <= R) {
help[i++] = arr[r++];
}
for (int j = 0; j < help.length; j++) {
arr[L+j] = help[j];
}
}
public static void main(String[] args) {
int[] arr = {4, 1, 5, 3, 9, 6};
MergeSort.mergeSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
}
練習題
https://www.bilibili.com/video/BV16K4y157vm?p=2，62min左右
小和問題可以用歸并排序來求解，大緻思想是：
- 由于歸并排序是将左右兩個排好序的數組merge，在這個過程中，我們看看左邊數組目前的數是否比右邊的數小，若是，說明對于目前的數，右邊數組從第一個比它大的數開始，直到數組末尾都比這個數大，是以通過下标的加加減減可以直接得出右邊數組有多少個數比目前左邊元素大。
- 一個例子：假設進行到某一步時，左邊數組是: [1, 4, 5, 8]，右邊數組是: [2, 3, 7, 15]，那麼對于左邊數組的1，由于右邊數組的2比1大，是以從2到15全都比1大（因為左右數組已經分别排好序)，是以可以直接得出1是右邊4個數的其中一個小和。
- 要注意的是，merge過程和經典歸并有不同的地方，當左面的數和右面的數相同時，先拷貝右面的數到數組中，否則會丢失左面的數比右面的數小的情況，如下圖所示，如果右面的1不先拷貝，而是先拷貝左面的1，那麼會丢失左面的4個1比右面的2、6、7小的情況。
https://www.bilibili.com/video/BV16K4y157vm?p=2，82min左右
與小和問題相似，在merge的過程中，看看右邊數組有哪些元素比左邊的小。
或許我們可以讓歸并排序降序排列，這樣如果左側有一個數大于右側的某個數，那麼它一定大于右側這個數後面的所有數。
一個求中值的小技巧
之前求中值的時候總時用mid = (start + end)/2，但這樣容易溢出，是以可以用這種方式：
-
mid = start + (end - start)/2
此外，對于/2操作，可以進一步優化（右移一位代表除以2）：
- mid = start + (end - start) >> 1
快速排序
問題引入 荷蘭國旗問題
對于一個數組，給出一個數，使小于這個數的數字排在數組左面，等于它的放到中間，大于它的放在右邊。
代碼如下，傳回值是等于給定值的若幹元素的起始和末尾下标：
public static void main(String[] args) {
int[] a = {3, 5, 7, 4, 5, 6, 1};
int[] res = Helan.fun(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
System.out.println("res: " + Arrays.toString(res));
}
private static int[] fun(int[] arr, int L, int R) {
int num = 5; // 假設給定的數就是5
int left = L - 1;
int right = R + 1;
int index = L;
while (index < right) {
if (arr[index] < num) {
swap(arr, ++left, index++);
}else if(arr[index] > num) {
swap(arr, index, --right);
}else {
index++;
}
}
return new int[] {left+1, right-1};
}
結果：
[3, 1, 4, 5, 5, 6, 7]
res: [3, 4]
經典快排
将一個數組的最後一個元素作為參考點，可以記為X，進行partition，結果是小于等于這個數的放在數組左面，大于的放在右面，X放在中間，也就是說一次搞定一個數。
使用荷蘭國旗問題優化快排
将一個數組的最後一個元素作為參考點，進行partition，結果是小于這個數的放在數組左面，等于的放在中間，大于的放在右面，如荷蘭國旗所述。通過這種方式可以一次将多個元素完成排序，而不是隻将一個元素完成排序。
快排存在的問題
由于經典快排是将數組的最後一個數作為參考點進行劃分，這麼做有時會導緻O(n^2)的時間複雜度。考慮這種情況：一個數組的最後一個數已經是數組中最大的，那麼選中這個數作為參考點X，劃分的結果就是小于X的全都在數組的左面。X自己位于數組最後一位，然後進行遞歸，遞歸的範圍是從0 - n-1，然後又選最後一個作為參考點，這個參考點仍然是0 - n-1範圍内最大的，那麼劃分的結果仍然是它位于整個數組的倒數第二位，重複這個過程我們發現：對于每一個參考點都要進行一次劃分，由于數組共有n個元素，是以要進行n次劃分，而每次劃分的時間複雜度是O(n)，是以快排最壞情況的時間複雜度是O(n^2)。此外，對于空間複雜度，上面舉的反例也同樣适用，每次選擇數組的最後一個元素(也就是最大元素)，那麼劃分完畢後得到的劃分點也是這個元素，一共有n個元素，是以劃分點也為n，是以最壞情況下空間複雜度也為O(n)。
改進快排
快排時間複雜度在數組已經有序的情況下最高，是以在選擇參考點時可以不一直選擇最後一個作為參考點，而是随機選擇一個數，再将這個數與最後一個數交換，之後再進行劃分。這麼做雖然還會存在随機選擇到的數是數組中最大或最小數的情況，但已經變成了機率問題，這時時間複雜度是由期望算出來的，為O(n*logn)。
對于空間複雜度，從長期的期望來看，改進後的快排每次都将劃分點選在數組中間，是以對于一個長度為n的數組，一共能選logn個劃分點，是以空間複雜度為O(logn)，可以借助下圖來了解：
說明(圖中的數字代表下标，不是數組元素)：
- 數組長度為8，我們假設第一次partition後的劃分點在3位置，是以需要一個數存儲這個劃分點3，然後會進行遞歸，這裡為了便于說明，我們省略左側(0 - 2)的遞歸過程，直接看右面(4 - 7)的遞歸過程。
- 劃分點3找到後，會将(4, 7)進行右側遞歸，繼續partition，假設這次的劃分點是5位置，那麼使用(6, 7)進行下一次的遞歸。
- 對于(6, 7)範圍，假設劃分點選擇的是6，那麼開始下一次的遞歸，這時由于6的左側不滿足遞歸條件，右側(7, 7)也不滿足，是以直接傳回。
- 當函數傳回到劃分點3所在的那一層時整個程式結束，數組的長度是8，而一共有3個劃分點，是以空間複雜度是O(logn)，這個空間複雜度也是長期期望值，當最壞情況出現時，仍然是O(n)
代碼如下：
public int[] MySort (int[] arr) {
// write code here
if (arr == null || arr.length == 0) return arr;
quickSort(arr, 0, arr.length-1);
return arr;
}
private void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int)(Math.random() * (r-l+1)), r);
int[] p = core(arr, l, r);
quickSort(arr, l, p[0]-1);
quickSort(arr, p[1]+1, r);
}
}
private int[] core(int[] arr, int l, int r) {
int more = r;
int less = l-1;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
}else if (arr[l] > arr[r]) {
swap(arr, --more, l);
}else {
l++;
}
}
swap(arr, r, more);
return new int[]{less+1, more};
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
堆排序
https://www.bilibili.com/video/BV16K4y157vm?p=3
完全二叉樹是可以用數組表示的。
- 若一個節點的下标為i，那麼其父節點的下标為 (i-1)/2。
- 若一個節點的下标為i，那麼其子節點的下标為 2i + 1 和 2i + 2
大根堆
在完全二叉樹中，任何一課子樹的最大值都位于子樹的頭部。
建立大根堆 heapInsert
給定一個數組，如何将其變成大根堆？圖畫的醜，将就看哈。
上述過程的代碼如下：
public class Heap {
public static void main(String[] args) {
}
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) return;
for (int i = 0; i <arr.length; i++) {
heapInsert(arr, i);
}
}
private static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index-1)/2]) {
swap(arr, index, (index-1)/2);
index = (index-1) / 2;
}
}
}
建立大根堆複雜度分析
注意，建立大根堆有兩種方式，第一種是使用者一個數一個數給你，這時建立大根堆的複雜度是O(nlogn)；另一種方式是使用者把所有的資料直接給你，這時建立大根堆的複雜度是O(n)。https://www.bilibili.com/video/BV16K4y157vm?p=3，大約70min有詳細講解。
下面說一下O(ologn)的情況：假設已經周遊完了數組的i個元素，且恰好構成了一棵滿二叉樹，那麼這時開始周遊第i+1個元素，由于它隻和父元素比較，是以父元素的數量就是比較的次數，父元素有多少個？是數的深度，也就是logi，是以對于一個元素的插入操作，時間複雜度是O(logi)，即樹的深度。
是以，對于第2個節點，需要的時間複雜度是log2，第三個節點是log3，…，到第n個節點所需的複雜度是log(n-1)，是以總的時間複雜度是将他們加起來。即log1 + log2 + log3 + … + logn => O(n*log(n))
堆的調整 heapify過程
若目前堆中某個元素變小了，怎樣才能保證這個堆仍然是個大根堆？
先由和子節點的索引關系找到兩個子節點，然後和兩個子節點中較大的做交換，更新其索引到被交換的子節點索引值，繼續比較子節點的大小，重複上述過程知直到沒有子節點為止。
heapSize指的是目前堆的大小，如果整個數組都構成了堆，那麼它的大小就等于數組的大小。
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1; // 值改變的節點的左孩子
while (left < heapSize) { // 如果左孩子在索引範圍内
int largest = left + 1 < heapSize && arr[left + 1] > arr[left] // largest存儲的是左右孩子中較大的哪那個
? left + 1: left;
largest = arr[largest] > arr[index]? largest: index; // 看看變小的元素變小後和左右孩子誰大
if (largest == index) { // 如果該元素變小後仍然最大就退出
break;
}
swap(arr, index, largest); // largest不等于index。将二者交換，更新index的下标
index = largest;
left = index * 2 + 1; // 左孩子的下标也要更新。
}
}
我們可以借助下圖分析，假設堆頂元素7變成了1，調整堆使其依然是大根堆：
彈出堆頂元素後使其仍然為大根堆
和上一小節相似，當彈出堆頂元素後，把目前堆的最後一個元素放到對頂的位置，然後進行上面說的heapify過程即可重新得到一個大根堆，注意heapSize-1。
小根堆
在完全二叉樹中，任何一課子樹的最小值都位于子樹的頭部。
來看一道堆的題目
https://www.bilibili.com/video/BV1Uf4y1X7XC?p=2
穩定性分析
穩定的排序：
- 冒泡，以數組[5, 4, 5, 3]為例，冒泡排序是每次找最大的數放到末尾，第一個數是5，第二個數是4，5比4大，是以交換5和4，變成：[4, 5, 5, 3]，繼續，第三個數還是5，由于第二個數交換後也是5，他倆相等，是以不讓第二個5和第三個5交換，也就保持了穩定性，第一趟比較後數組為：[4, 5, 3, 5]，後面就不用細說了。
- 插入，以[2, 3, 2]為例，開第一個2和自己交換，然後到3，3比第一個2大，是以不必交換，然後到第二個2，它比3小，是以交換，此時數組為：[2, 2, 3]，第二個2前面的數是第一個2，此時不讓他們交換，就保持了穩定性。
- 歸并，具體例子見下圖，假設現在要進行merge操作，當left和right有相同的數字時，我們讓left先填進去，然後再填right，如圖中的數字5。
各種排序算法及複雜度、穩定性(左神算法班) - 桶排序思想下的排序(基數排序和計數排序)也是穩定的，因為他們是基于桶的，先進桶的肯定先出桶。
不穩定的排序：
- 選擇，至于為什麼不穩定，可以看下圖，選擇排序是每次在數組中選擇最小的元素，然後和數組前面的元素交換。那麼對于本例來說，第一次選擇的最小的數是1，它要和第一位4交換，是以4的相對位置被改變了。
各種排序算法及複雜度、穩定性(左神算法班) - 快排，有這樣一個數組[4, 4, 4, 3]，設劃分過程以3為基準，小于3的放左面，那麼當周遊到3時，它會和第一個4互換位置，破壞了穩定性。或[6, 7, 6, 6, 3, 5]，從第一個6到第三個6經過的數都比5大，是以不做任何操作，到3時發現小于5，是以要和小于區域(此時為-1)的下一個元素(6)交換，數組變為: [3, 7, 6, 6, 6, 5]，此時第一個6已經跑到原始數組中第三個6後面去了，是以不穩定。
- 堆，例子如下，
各種排序算法及複雜度、穩定性(左神算法班)
穩定性的意義
為什麼需要保證穩定性？假設我們要對某次考試的成績進行排序，對于一個學年來說有若幹個班級，是以如果按成績從低到高排序的話，成績單可能是這樣的：
現在想統計各個班級的成績情況。1班的排在一起，2班的排在一起，成績自然也要從低到高。如果使用的是不穩定的排序，那麼對于1班來說喬巴很可能就排在了路飛的前面，這可能不是我們想要的。
使用各種排序方法的情況
- 當樣本量較少時（小于60），使用插入排序，因為它的常數操作非常少，雖然複雜度是O(n^2)，但在樣本量少的時候展現不出來劣勢。是以當使用遞歸的排序方法時，一旦某次遞歸過程發現要處理的子數組長度小于60，那麼就使用插入排序。
- 如果要排序的都是基礎類型，那麼用快排。雖然快排是不穩定的，但對于基礎資料類型來說，穩定性是沒有任何意義的。
- 如果要排序的都是複雜類型，就用歸并排序，因為要保證穩定性。
穩定性總結
排序的補充
關于題1：把歸并排序空間複雜度降為O(1)之後就不穩定了，那為啥不用堆排序呢？還有的“原地歸并”也可以讓空間複雜度變為O(1)，但時間複雜度又是O(n^2)了，那為啥不用插入呢？
關于題2：快排有穩定性之後，空間複雜度又變為O(n)了，那為啥不用歸并呢？
關于題3：把奇數放左面，偶數放右面，相對次序不變，額外空間複雜度還得是O(1)，時間複雜度是O(n)，做不到。
因為經典快排的partition将小于等于的放左面，大于的放右面這是01标準，換成奇數偶數也同樣是01标準，而快排的劃分做不到(或者說很難做到)相對次序不變，是以題3要求奇偶也做不到(很難做到)。
非基于比較的排序
桶排序
計數排序
給你一組數，這組數的特點是範圍變化不大，如年齡。那麼可以準備一個可以容納所有這些數範圍的數組，然後周遊題目所給的資料，在周遊時統計每個數字出現的次數，儲存到你準備的數組中。
基數排序
給你一組數，先找到位數最多的那個(例如這組數有1位的，2位的，…，6位的，那麼為數最多的就是6位的)，然後在其他的數前面補0，直到所有數的位數都為位數最多的數量。然後按照從個位到最高位的順序分别放入對應的桶中(10進制就10個桶，2進制就2個桶)。此種排序要求待排序資料一定要有進制。
https://www.bilibili.com/video/BV16K4y157vm?p=3，118min左右
視訊中的代碼比較難了解，這裡記錄一下。
假設有一數組arr[013, 021, 011, 052, 062]，定義一個count數組長度為進制數，在本例中是10進制，是以count數組的長度也為10。我們開始周遊題目給出的數組，剛開始是013，個位是3，那麼就在count數組中下标為3位置記為1，即count[3]=1，然後周遊到021，個位是1，那麼count[1]=1，再到011，那麼count[1]=2，再到052，那麼count[2]=1，最後到062，那麼count[2]=2。
此時count數組為：[0, 2, 2, 1, 0, 0, …]，現在将count數組第一位與第二位相加，第二位與第三位相加，以此類推，相加之後的zount數組為：[0, 2, 4, 5, 5, 5, …]，此時count數組每一位的意義是arr中，個位數小于等于該位的數有幾個，例如count[1]=2，那就表示在arr中個位數小于等于1的有兩個(021, 011)，而count[2]=4代表個位數小于等于2的有四個(021, 011, 052, 062)。
再準備一個備用數組，長度和arr相同。
重點來了： 現在從右到左周遊arr，第一個碰見的數是062，也就是說062是個位數為2的所有數中最後一個入2号桶的，那麼他肯定也是最後一個出2号桶的，那麼一共多少個數的個位數小于等于2呢？有4個，是以我們将062放到備用數組的3位置，就代表062是所有個位數小于等于2的數中的最後一個出桶的，之後将count[2]減1，現在count[2]=3；第二個碰見的數是052，此時count[2]=3，說明個位數小于等于3的還有3個，而052就是這3個中的最後一個，是以将052放入備用數組的2位置，之後将count[2]減1，現在count[2]=2。對其他的數重複上述過程，結束後備用數組中的數就是基數排序中個位數入桶再出桶的順序，然後對十位、百位、千位…依次處理即可。
練習題