還不會七大排序,是準備家裡蹲嗎!?

NO IMAGE

還不會七大排序,是準備家裡蹲嗎!?

思維導圖

還不會七大排序,是準備家裡蹲嗎!?

動圖轉載地址:www.cnblogs.com/fivestudy/p…

交換排序

冒泡排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

void sort() {
// 修剪枝葉的優化方法
// 基於原理:
// 每一趟完整的循環就對完成一個最大值或者最小值的放置
// 那每一趟都可以刪去枝葉,也就是最大值或者最小值的位置
// i的大小也同樣可以確定已經完成排序的數值的個數
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
swap(array[j], array[j+1]);
}
}
}
}

原理及其實現方式

代碼的效果正好和圖片相反,其實冒泡排序作為最簡單的排序方法之一,基於的是一個這樣的概念:兩兩交換,比較雙方數值大的放在高位,數值小的則放在低位。

而暴力雙重循環,就是他的實現方式。每一次都將最大的一位數放到了最後一位,或者反之,將最小的數放到了第一位。

快速排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

static void sort(int left, int right) {
if (left < right) {
// 通過split已經完成了左右分割,左邊數一定小於中線,右邊數一定大於中線
int mid = split(left, right);
// 對左右分區再以中線劃分
sort(mid+1, right);
sort(left, mid-1);
}
}
static int split(int left, int right) {
// 以當前範圍數組的第一個值作為中線
int temp = array[left];
while(left < right){
// 右指針出現了一個數比中線小,則與中線進行交換
while(left < right && temp < array[right]) right--;
array[left] = array[right];
// 左指針出現了一個數比中線大,則與中線進行交換
while(left < right && temp > array[left]) left++;
array[right] = array[left];
}
// 此時left == right,並無所謂是誰來進行交換
array[left] = temp;
return left;
}

原理及其實現方式

快速排序其實是冒泡排序的升級版,同樣的基於兩兩交換,但是引入了分治的思想。通過使用中線,對需要排序的區間進行了重新的一個劃分,而這內部剩下的性能還有一方面就是在於這個中線,因為數值的比較不再是全局,而是局部,從效率計算上來講一般情況可降到O(nlogn),當然極端情況就可能退化回我們的冒泡排序。

極端例子:5 -> 4 -> 3 -> 2 -> 1

也就是一個已經完成排序的數組,再經過快速排序,想要將數組排序,就將會造成快排的退化。而解決方案就是不再以首個數據作為中線的基準。

插入排序

直接插入排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

void sort() {
// 修建枝葉的方法雖然可以用,但是效果微乎其微
// 因為這只是根據數學方法推算,可以得知變量i=0時,是不需要工作的,也就刪去的一小部分的工作
for (int i = 1; i < array.length; i++) {
int j = i;
int temp = array[i];
// 如果當前已完成排序數組中,下標數值大於當前數值
// 就把這個數值往後進行移動
while (j > 0 && temp < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
if (j != i) array[j] = temp;
}
}

原理及其實現方式

插入排序,顧名思義,就是把數字放到合適的位置。原理上講就是將一個無須數組拆分成了兩個部分,一塊有序,一塊無序。不斷的刪去無須隊列中的數值,放到有序隊列中,最後也就成為了有序隊列。

第一趟排序:(5) -> 3 -> 4 -> 7 -> 2 
第二趟排序:(3 -> 5 )-> 4 -> 7 -> 2 
第三趟排序:(3 -> 4 -> 5 )-> 7 -> 2 
。。。。以此類推

希爾排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

static void sort() {
// gap也就相當於組別
for (int gap = array.length >> 1; gap > 0; gap /= 2) {
for (int i = gap; i < array.length; i++) {
int j = i;
while (j - gap >= 0 && array[j] < array[j - gap]) {
swap(array[j], array[j - gap]);
j -= gap;
}
}
}
}

原理及其實現方法

先對代碼做一個解釋:
(1)gap:也就是是我說的組別,分成兩個部分
(2)array[j]:右半邊需要交換的序列
(3)array[j - gap]:左半邊交換的序列
(4)j -= gap:是為了保障最後一位被遺忘的數據被處理。

原序列:4 -> 3 -> 2 -> 5 -> 1
第一趟過程1:(2) -> 3 -> (4) -> 5 ->1
第一趟過程2:2 -> (3) -> 4 -> (5) ->1
第一趟過程3:(1) -> 3 ->(2)-> 5 ->(4)

選擇排序

簡單選擇排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

void sort() {
// 修剪枝葉的優化方法
// 基於原理:和冒泡排序完全一致。
for (int i = 0; i < array.length; i++) {
// 用於標示最小值下標
int min = i;
// 循環方式找到最小值
for (int j = i+1; j < array.length ; j++) {
if (array[j] < array[min]) min = j;
}
swap(array[min], array[i]);
}
}

原理及其實現方式

和冒泡排序簡單程度同級的排序,基於這樣一個概念:每次找到在維護的數組內部最小個的值,並將它放到對應範圍的第一位。

實現方案同樣還是暴力的雙重循環進行一個求解過程。

堆排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

static void sort(){
int len = arr.length;
// 構建大頂堆
for (int i = (arr.length - 1) / 2; i >= 0; i--)
heapSort(i, arr.length - 1);
for (int i = arr.length - 1; i > 0; i--) {
// 交換0,最後號位,也就把最大值放到了最後
swap(0, i);
// len減1,保證了最後一位數並不會處理
// 也就完成了倒數的大數的排序
len--;
heapSort(0, len);
}
}
static void heapSort(int i, int len) {
if (i > len) return;
int maxIdx = i;
int firPosition = i * 2 + 1;
int secPosition = i * 2 + 2;
// 左右大小比較,左邊為大
if (firPosition < len && arr[firPosition] > arr[maxIdx]) maxIdx = firPosition;
if (secPosition < len && arr[secPosition] > arr[maxIdx]) maxIdx = secPosition;
if (maxIdx != i) {
swap(maxIdx, i);
heapSort(maxIdx, len);
}
}

原理及其實現方式

堆排序,其實你也可以理解為一種樹形排序,雖然沒有把這個數組轉化成樹,但是基於的原理就是一種樹形的概念。

(1)大頂堆(數組升序):arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

(2)小頂堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

總結出來就是樹形,而遍歷方式就是一種層次形遍歷比較:

原序列:4 -> 3 -> 2 -> 5 -> 1
構建大頂堆,樹形對應數組的一份: 
4        2無子樹       4                    5    maxId變化    5
/     \     不處理。    /    \               /    \   處理4    /   \
3       2     ===>     5        2   ===>    4      2   ===>   4     2 
/ \           處理3    / \           處理4  /  \               / \
5   1                  3   1                3    1            3   1

我們發現一旦出現值的變化,那就需要對子樹進行最初相應的改變,但為什麼這一步只是說完成樹的構建呢? 因為她並不會去比較,左右子樹的大小,他唯一能保證的就是一個節點的值一定大於左右子樹,並且確定下跟節點的值。所以引出了我們的第二步就是真正的排序。

構建完大頂堆後的序列:5 -> 4 -> 2 -> 3 -> 1
進行完交換後:
5         交換         1    
/     \     0和4號位    /    \        回到上述的樹形建立
4       2     ===>     4        2  ===>
/ \                    / \              只是去除了4號位 
3   1                  3   5          

歸併排序

還不會七大排序,是準備家裡蹲嗎!?

對應代碼

static void sort(int L, int R) {
if(L == R) {
return;
}
int mid = ((L + R) >> 1);
// 不斷的對數組直接進行對半的拆分
// 遞歸調用迴歸順序
// 先把左半邊全部合併,再把右半邊全部合併
// 兩兩數組合並
sort(array, L, mid);
sort(array, mid + 1, R);
merge(array, L, mid, R);
}
static void merge(int L, int mid, int R) {
int[] temp = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
// 比較左右兩部分的元素,哪個小,把那個元素填入temp中
while(p1 <= mid && p2 <= R) {
temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
// 上面的循環退出後,把剩餘的元素依次填入到temp中
while(p1 <= mid) {
temp[i++] = array[p1++];
}
while(p2 <= R) {
temp[i++] = array[p2++];
}
// 把最終的排序的結果複製給原數組
for(i = 0; i < temp.length; i++) {
array[L + i] = temp[i];
}
}

原理及其實現方式

從圖中已經知道了,歸併排序和快排的思路正好相反,為什麼這麼說呢,快排在拆分的時候其實是拆分的時候通過中線分割,而歸併是在是先把整個數組直接做一個對半拆分再對比合並。

拆分不是難事,但是合併真的很麻煩。如果只有兩個數據比較,那麼只用判斷a > b,再來一個swap(a, b)。但是兩個數組的比較呢?

原序列:4 -> 3 -> 2 -> 5 -> 1
左半邊序列迴歸的時候需要進行的比較,經過推算肯定是第一次兩個數組合並是:
4 -> 3的比較,這個時候具體merge(0, 0, 1);
歸併的做法是創建一個新的數組空間來存放。
(1)兩個數組 {[4], [3]},這裡會將數組小的一個個塞進新數組temp中。
while(p1 <= mid && p2 <= R) {
temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
}
(2)而下方的自加策略是對未運算完的數據全部數據一股腦塞進temp中。
仔細觀察可以發現其實只完成了對數組[3]的賦值,就跳出了這一重循環。
while(p1 <= mid) {
temp[i++] = array[p1++];
}
while(p2 <= R) {
temp[i++] = array[p2++];
}

總結

因為算法的使用肯定考慮到使用場景,所以知道時空複雜度,是使用使用算法的前提。但是已經不再提倡選擇和冒泡排序了,因為效率實在太差。

還不會七大排序,是準備家裡蹲嗎!?

以上就是我的學習成果,如果有什麼我沒有思考到的地方或是文章內存在錯誤,歡迎與我分享。


相關文章推薦:

面試中的HashMap、ConcurrentHashMap和Hashtable,你知道多少?

手撕Handler

手撕ButterKnife

相關文章

前端如何實現整套視頻直播技術流程

輕鬆理解JS中的面向對象,順便搞懂prototype和__proto__

MyBatis源碼解析(三)—緩存篇

Android主流三方庫源碼分析(六、深入理解Leakcanary源碼)