package com.liuxing.sort;

import com.liuxing.util.Print;

/**

• @author liuxing007

• @ClassName MergeSort

• @Description 歸并排序（Merge Sort）

• 歸并排序的核心思想還是蠻簡單的。如果要排序一個(gè)數(shù)組，

• 我們先把數(shù)組從中間分成前后兩部分，然后對前后兩部分分別排序，

• 再將排好序的兩部分合并在一起，這樣整個(gè)數(shù)組就都有序了。

• 時(shí)間復(fù)雜度：O(nlogn)

• 空間復(fù)雜度：O(n)

• 不是原地排序算法

• @date 2020/9/17 15:04

*/

public class MergeSort {

public static void main(String[] args) {

int[] arr = new int[]{6,4,1,7,2,5,8,3};

int length = arr.length;

System.out.println(“排序前數(shù)組===========”);

Print.print(arr, length);

sort(arr, length);

System.out.println(“排序后數(shù)組===========”);

Print.print(arr, length);

}

/**

• 排序算法

• @param arr 數(shù)組

• @param l 數(shù)組長度

*/

private static void sort(int[] arr,int l){

sortMerge(arr,0,l-1);

}

/**

• 遞歸

• @param arr 數(shù)組

• @param p 開始位置下表

• @param r 結(jié)束位置下表

*/

private static void sortMerge(int[] arr,int p,int r){

if(p >= r){

return ;

}

//分治的下標(biāo)，這里我采用p到r的中間位置index。

int index = p + (r-p)/2;

//左側(cè)遞歸

sortMerge(arr,p,index);

//右側(cè)遞歸

sortMerge(arr, index + 1, r);

merge(arr, p, index,r);

System.out.println(“排序后數(shù)組===========”);

Print.print(arr, length);

}

/**

• 合并計(jì)算

• @param arr 原素組

• @param l 左側(cè)數(shù)組開始位置下標(biāo)

• @param index 左側(cè)數(shù)組結(jié)束位置下標(biāo)

• @param r 右側(cè)數(shù)組結(jié)束位置下標(biāo)

*/

private static void merge(int[] arr, int l,int index, int r) {

//臨時(shí)數(shù)組，這里可以優(yōu)化，數(shù)組的頻繁創(chuàng)建會降低程序運(yùn)行的效率，

// 所以這里可以將這個(gè)臨時(shí)數(shù)組改成參數(shù)傳遞進(jìn)來，在數(shù)量較大的時(shí)候執(zhí)行效率變化變焦顯著

int[] temp = new int[r-l+1];

//左側(cè)開始下標(biāo)

int i= l;

//右側(cè)開始下標(biāo)

int j = index+1;

//臨時(shí)數(shù)組下標(biāo)

int k=0;

// 左側(cè)數(shù)組與右側(cè)數(shù)組進(jìn)行對比，將小的元素放入臨時(shí)數(shù)組中

while(i<=index && j<=r){

if(arr[i]<arr[j]){

temp[k++] = arr[i++];

}else{

temp[k++] = arr[j++];

}

}

//對比完成之后，需要把兩側(cè)數(shù)組中還沒有對比的數(shù)據(jù)加入到臨時(shí)數(shù)組中

//把左邊剩余元素加入臨時(shí)數(shù)組中

while(i<=index){

temp[k++] = arr[i++];

}

//把右邊剩余元素加入臨時(shí)數(shù)組中

while(j<=r){

temp[k++] = arr[j++];

}

//將臨時(shí)數(shù)組的元素拷貝原數(shù)組中

for(int x=0;x<temp.length;x++){

arr[x+l] = temp[x];

}

}

}

package com.liuxing.util;

/**

• @author liuxing007

• @ClassName Print

• @Description 打印

• @date 2020/9/17 11:13

*/

public class Print {

/***

• 打印數(shù)據(jù)

• @param arr 數(shù)組

• @param length 數(shù)組長度

*/

public static void print(int[] arr, int length) {

for (int i = 0; i < length; ++i) {

System.out.print(arr[i] + " ");

}

System.out.println("");

}

}

排序前數(shù)組===========

6 4 1 7 2 5 8 3

合并后的數(shù)據(jù)

4 6 1 7 2 5 8 3

合并后的數(shù)據(jù)

4 6 1 7 2 5 8

《一線大廠Java面試題解析+后端開發(fā)學(xué)習(xí)筆記+最新架構(gòu)講解視頻+實(shí)戰(zhàn)項(xiàng)目源碼講義》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整內(nèi)容開源分享

3

合并后的數(shù)據(jù)

1 4 6 7 2 5 8 3

合并后的數(shù)據(jù)

1 4 6 7 2 5 8 3

合并后的數(shù)據(jù)

1 4 6 7 2 5 3 8

合并后的數(shù)據(jù)

1 4 6 7 2 3 5 8

合并后的數(shù)據(jù)

1 2 3 4 5 6 7 8

排序后數(shù)組===========

1 2 3 4 5 6 7 8

Process finished with exit code 0

---

3.時(shí)間空間復(fù)雜度分析

---

我們假設(shè)對 n 個(gè)元素進(jìn)行歸并排序需要的時(shí)間是 T(n)，那分解成兩個(gè)子數(shù)組排序的時(shí)間都是 T(n/2)。我們知道，merge() 函數(shù)合并兩個(gè)有序子數(shù)組的時(shí)間復(fù)雜度是 O(n)。所以，套用前面的公式，歸并排序的時(shí)間復(fù)雜度的計(jì)算公式就是：

T(1) = C； n=1時(shí)，只需要常量級的執(zhí)行時(shí)間，所以表示為C。

T(n) = 2*T(n/2) + n； n>1

通過這個(gè)公式，如何來求解 T(n) 呢？還不夠直觀？那我們再進(jìn)一步分解一下計(jì)算過程。

T(n) = 2*T(n/2) + n

= 2*(2T(n/4) + n/2) + n = 4T(n/4) + 2*n

= 4*(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n

= 8*(2T(n/16) + n/8) + 3n= 16T(n/16) + 4n

…

= 2^k * T(n/2^k) + k * n

…

通過這樣一步一步分解推導(dǎo)，我們可以得到 T(n) = 2 k 2^k 2k T(n/ 2 k 2^k 2k)+kn。當(dāng) T( n / 2 k n/2^k n/2k)=T(1) 時(shí)，也就是 2 k 2^k 2k=1，我們得到 k= l o g 2 n log_2n log2?n 。我們將 k 值代入上面的公式，得到 T(n)=Cn+ l o g 2 n log_2n log2?n 。如果我們用大 O 標(biāo)記法來表示的話，T(n) 就等于 O(nlogn)。所以歸并排序的時(shí)間復(fù)雜度是 O(nlogn)。從我們的原理分析和偽代碼可以看出，歸并排序的執(zhí)行效率與要排序的原始數(shù)組的有序程度無關(guān)，所以其時(shí)間復(fù)雜度是非常穩(wěn)定的，不管是最好情況、最壞情況，還是平均情況，時(shí)間復(fù)雜度都是 O(nlogn)-----摘自-極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法-王爭

歸并排序的時(shí)間復(fù)雜度已經(jīng)很優(yōu)秀了，但為什么我們在日常開發(fā)中卻很少看到他的身影呢？我們先來分析一下歸并排序的空間復(fù)雜度。

我們需要注意的是合并方法，這個(gè)方法中我們使用了一個(gè)臨時(shí)數(shù)組用來存儲數(shù)據(jù)，但是合并之后這個(gè)臨時(shí)數(shù)組就會釋放，又因?yàn)榕R時(shí)數(shù)組的最大長度不會超過原始數(shù)組長度n，所以歸并排序的空間復(fù)雜度為：O(n)

為什么開發(fā)中很少人使用到歸并排序呢？原因很簡單，因?yàn)樗皇且粋€(gè)原地排序算法，這個(gè)時(shí)候你可能會有疑惑了，什么是原地排序算法？簡單來說：不通過其他空間來完成的排序，我們稱它為原地排序算法，但歸并排序很明顯借用了一個(gè)臨時(shí)數(shù)組，所以它不是一個(gè)原地排序算法，即使它的時(shí)間復(fù)雜都很穩(wěn)定，使用的人也比較少。

---

三、快速排序

=====================================================================

1.什么是快速排序

---

如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)， 我們選擇 p 到 r 之間的任意一個(gè)數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）。我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊， 將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過這一步驟之后， 數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，后面的 q+1 到 r 之間是大于 pivot 的.根據(jù)分治、遞歸的處理思想，我們可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r 之間的數(shù)據(jù)，直到區(qū)間縮小為 1，就說明所有的數(shù)據(jù)都有序了。（摘自-極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法-王爭）

快速排序的思想和歸并排序有點(diǎn)類似，都是通過分治的思想，利用遞歸實(shí)現(xiàn)排序，只不過實(shí)現(xiàn)的細(xì)節(jié)有所不同，快排（快速排序）需要一個(gè)分區(qū)點(diǎn)，可以在數(shù)組中隨便去一個(gè)元素作為分區(qū)點(diǎn)即可，后面就是前面講到的概念了，歸并的核心在于合并，而快排的核心在于分區(qū)點(diǎn)，所以我們就一起來看看在獲取分區(qū)點(diǎn)的時(shí)候快排都干了些啥？

之前說過，快排選擇一個(gè)分區(qū)點(diǎn)（pivot）之后，將小于分區(qū)點(diǎn)（pivot）的元素放左邊，分區(qū)點(diǎn)（pivot）放中間，大于分區(qū)點(diǎn)（pivot）的放右邊，這個(gè)一看就很好解決嘛，和歸并排序一樣，我先申請兩個(gè)臨時(shí)數(shù)組，一個(gè)存放小于分區(qū)點(diǎn)元素的數(shù)組，一個(gè)存放大于分區(qū)點(diǎn)元素的數(shù)組，這樣，就能完美的解決了，非常簡單，但是這個(gè)就和歸并排序面臨這同一樣的一個(gè)問題：它不是一個(gè)原地排序算法，那如果我希望快排是一個(gè)原地排序算法呢？我們應(yīng)該如何實(shí)現(xiàn)呢？其實(shí)也不難，我們可以參考一下選擇排序：【數(shù)據(jù)結(jié)構(gòu)與算法】常見的三種排序（冒泡排序、插入排序、選擇排序）

我們定義一個(gè)游標(biāo) i (數(shù)組下標(biāo)) 把數(shù)組a[p-(r-1)]分成兩部分，A[p-(i-1)]都是小于分區(qū)點(diǎn)（pivot）的，我們叫他“已排序區(qū)間”。a[(i+1) - (r-1)]都是大于分區(qū)點(diǎn)（pivot）元素的，我們叫他“未排序區(qū)間”，只要從未排序區(qū)間去值與分區(qū)點(diǎn)（pivot）進(jìn)行比較，如果小于分區(qū)點(diǎn)（pivot），那么將此元素追加到已排序區(qū)間中（a[i]），否者不需要變動(dòng)。

我還是準(zhǔn)備了一張圖給大家參考，也許大家就能明白了。

這是一次分區(qū)交換的結(jié)果，當(dāng)把所有分區(qū)都交換完成之后，整個(gè)數(shù)組也就有序了，既然快速排序的思想已經(jīng)講的差不多了，下面我們一起來看看代碼怎么實(shí)現(xiàn)

快排代碼實(shí)現(xiàn)

package com.liuxing.sort;

import com.liuxing.util.DataUtil;

import com.liuxing.util.Print;

/**

• @author liuxing007

• @ClassName Quicksort

• @Description 快速排序

• 如果要排序數(shù)組中下標(biāo)從 p 到 r 之間的一組數(shù)據(jù)，

• 我們選擇 p 到 r 之間的任意一個(gè)數(shù)據(jù)作為 pivot（分區(qū)點(diǎn)）。

• 我們遍歷 p 到 r 之間的數(shù)據(jù)，將小于 pivot 的放到左邊，

• 將大于 pivot 的放到右邊，將 pivot 放到中間。經(jīng)過這一步驟之后，

• 數(shù)組 p 到 r 之間的數(shù)據(jù)就被分成了三個(gè)部分，

• 前面 p 到 q-1 之間都是小于 pivot 的，中間是 pivot，

• 后面的 q+1 到 r 之間是大于 pivot 的.

• 根據(jù)分治、遞歸的處理思想，

• 我們可以用遞歸排序下標(biāo)從 p 到 q-1 之間的數(shù)據(jù)和下標(biāo)從 q+1 到 r 之間的數(shù)據(jù)，

• 直到區(qū)間縮小為 1，就說明所有的數(shù)據(jù)都有序了（摘自-極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)與算法-王爭）

• 時(shí)間復(fù)雜度：O(nlogn)

• 空間復(fù)雜度：O(1)

• 原地排序算法，但不是穩(wěn)點(diǎn)排序算法

• @date 2020/9/18 10:22

*/

public class Quicksort {

public static void main(String[] args) {

int[] arr = new int[]{6, 5, 4, 3, 2, 1};

// int[] arr = DataUtil.createIntArrData();

int length = arr.length;

System.out.println(“排序前數(shù)組===========”);

Print.print(arr, length);

sort(arr, length);

System.out.println(“排序后數(shù)組===========”);

Print.print(arr, length);

}

/**

• 排序算法

• @param arr 數(shù)組

• @param l 數(shù)組長度

*/

private static void sort(int[] arr,int l){

sortRec(arr,0,l-1);

}

/**

• 遞歸

• @param arr

• @param p

• @param r

*/

private static void sortRec(int[] arr, int p, int r) {

//遞歸終止條件

if (p >= r){

return;

}

//獲取分區(qū)點(diǎn)

int q = partition(arr, p, r);

總結(jié)

以上是生活随笔為你收集整理的入秋的第一篇数据结构算法：看看归并与快排的风采，三面蚂蚁金服成功拿到offer的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。