核心思想:將一個(gè)數(shù)組進(jìn)行排序,可以先(遞歸)將他分成兩半分別排序,然后把結(jié)果合并起來(lái).若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并
即:將數(shù)組分成兩部分,左邊部分,和右邊部分分別遞歸再次分成兩部分知道每個(gè)數(shù)組里面只有一個(gè)元素.然后調(diào)用合并函數(shù),將兩個(gè)數(shù)組進(jìn)行排好序.每次排序的時(shí)候會(huì)使用同一個(gè)臨時(shí)緩存,儲(chǔ)存排好序的元素.最后的排序結(jié)果是 依次把 左半邊的 數(shù)組 兩兩排序合并,遞歸再把合并的數(shù)組繼續(xù)兩兩合并,最后左邊的數(shù)組全部合并;接下來(lái)對(duì)右半部分的數(shù)組兩兩排序合并,重復(fù)左邊的類似動(dòng)作,把右邊的數(shù)組排序成一個(gè)數(shù)組;最后進(jìn)行左右兩個(gè)有序數(shù)組合并,組成最終有序數(shù)組.
歸并排序的時(shí)間復(fù)雜度是NlogN,缺點(diǎn)是所需要的額外輔助空間和N成正比(需要分配一個(gè)與N長(zhǎng)度一致的臨時(shí)存儲(chǔ)空間).
2.2.1原地歸并的抽象方法:
因?yàn)榭紤]到直接歸并算法每次合并需使用一個(gè)臨時(shí)空間,所以考慮在原始數(shù)組上直接進(jìn)行排序,先對(duì)前半部分排序,在對(duì)后半部分排序.但是相對(duì)二路歸并的復(fù)雜度高.
2.2.2二路歸并具體的算法思路:(是一種自頂向下的mergesort)
1.判斷需要進(jìn)入遞歸操作的邊界值.(一般 left<right)
2.把數(shù)組分成兩半. Mid =(left+right)/2
3.進(jìn)行左半邊數(shù)組遞歸調(diào)用.直到 left=right ,不在遞歸.此時(shí)提取出數(shù)組的第一個(gè)元素
4.進(jìn)行右半邊數(shù)組遞歸調(diào)用.
5.調(diào)用merge方法,把兩個(gè)有序數(shù)組合并.合并的時(shí)候會(huì)使用一個(gè)臨時(shí)數(shù)組.合并的思路是從兩個(gè)有序的數(shù)組第一個(gè)元素開(kāi)始,依次比較,把數(shù)據(jù)按從小到大的順序存放到臨時(shí)temp;遇到某一個(gè)數(shù)組完成了,剩下一個(gè)數(shù)組還沒(méi)比較完,則把剩下的數(shù)組復(fù)制到temp尾部.最后把temp數(shù)組讀取,替換實(shí)際數(shù)組中.
步驟如下圖:
要把a(bǔ)[]分成a[lo...hi]兩部分,進(jìn)行分別對(duì) a[lo...mid] ,a[mid+1...hi]進(jìn)行遞歸調(diào)用,直到調(diào)用的數(shù)組lo和hi相同時(shí)跳出,繼而進(jìn)行和右邊部分合并排序.
代碼如下:
public class Mergesort{
public static int [] temp;
public void sort(int[] arr){
if(arr==null||arr.lenth==0){
return;}
temp=new int[arr.lenth];
mergesort(arr,0,arr.lenth-1);
}
private void mergsort(int[] arr,int low,int high){
if(low>=high){return;}
int mid=(low+high)/2;
mergesort(arr,low,mid);
mergesort(mid+1,high);
merge(arr,low,mid,high);
}
private void merge(int[] arr,int low,int mid,int high){
int leftIndex=low;
int rightIndex=mid+1;
int tempIndex=0;
while(leftIndex<=mid&&rightIndex<=high){
if(arr[leftIndex]<arr[rightIndex]){
temp[tempIndex++]=arr[leftIndex++];
}else{
temp[tempIndex++]=arr[rightIndex++];
}
//已經(jīng)比較完了,接下來(lái)如果發(fā)現(xiàn)左邊 或者右邊還有沒(méi)到最后的部分,則把那一部分直接添加到temp尾部
while(leftIndex<=mid){
temp[tempIndex++]=arr[leftIndex++];
}
while(rightIndex<=high){
temp[tempIndex++]=arr[rightIndex++];
}
//把temp 合并到arr中
int t=0;
while(low<=high){
arr[low++]=temp[t++];
}
}
}
}
時(shí)間復(fù)雜度計(jì)算:
因?yàn)檫f歸算法的時(shí)間復(fù)雜度可以表示為T(mén)(n)=2T(n/2)+O(n).
這是一個(gè)每次分一半的遞歸,總共執(zhí)行排序的步驟可以畫(huà)成一棵類似的樹(shù).
因?yàn)槊恳粚拥淖訂?wèn)題時(shí)間代價(jià)為cn,一共有l(wèi)og2N+1 層,所以所有的時(shí)間=cn(lgN+1)=cnlnN+cn 時(shí)間復(fù)雜度
O(NlgN).
命題F:
對(duì)于長(zhǎng)度為N的任意數(shù)組,自頂向下歸并排序的需要 ?NlgN ≤O≤ NlgN次比較.
命題G:
對(duì)于長(zhǎng)度為N的任意數(shù)組,自頂向下歸并排序最多要訪問(wèn)數(shù)組6NlgN次.
證明:
每次歸并最多需要訪問(wèn)數(shù)組6N次(2N 復(fù)制,2N用來(lái)將排好序的數(shù)組復(fù)制過(guò)去,2N次進(jìn)行合并),根據(jù)命題F,可知需要有NlgN次比較,所以訪問(wèn)數(shù)組為6NlgN.
2.2.3對(duì)自定向下的歸并排序的優(yōu)化
1.對(duì)小規(guī)模的數(shù)組使用插入排序.(具體設(shè)置的閥值7) 一般插入排序處理小規(guī)模排序(例如15)可以將歸并縮短時(shí)間10%~15%
2.測(cè)試數(shù)組是否已經(jīng)有序.在merge之前添加一個(gè)方法判斷arr[mid]≤arr[mid+1],如果是的話說(shuō)明這個(gè)從lo ...high的數(shù)組已經(jīng)是有序了
3.在merge的時(shí)候不進(jìn)行多次復(fù)制.(不把數(shù)組復(fù)制到臨時(shí)數(shù)組,然后又進(jìn)行把臨時(shí)數(shù)組的數(shù)據(jù)copy到src中,這里面至少要經(jīng)過(guò)2次重復(fù)操作)優(yōu)化對(duì)臨時(shí)數(shù)組的空間上面還是保持不變,主要在與減少時(shí)間.
代碼如下:
public class MergeSort{
private static final int OFF_CUT=7;
public void sort(int[] src){
int[] org=src.clone();
mergeSort(org,src,0,org.length-1);
}
private void mergeSort(int[] src,int[] dst,int lo,int hi){
//進(jìn)行閥值判斷
if(hi<lo+OFF_CUT){
insertSort(dst,lo,hi);
return ;
}
int mid=(lo+hi)/2;
mergeSort(dst,src,lo,mid);
mergeSort(dst,src,mid+1,hi);
//如果src已經(jīng)有序,那么直接復(fù)制到dst即可
if(src[mid+1]>=src[mid]){
System.arrayCopy(src,lo,dst,lo,hi-lo+1);
}
merge(src,dst,lo,mid,hi);
}
private void insertSort(int[] arr,int lo,int hi){
for(int i=lo+1;i<=hi;i++){
int temp=arr[i];
int j=i;
while(j>lo&&temp<arr[j-1];j--){
arr[j]=arr[j-1];
}
arr[j]=temp;
}
}
private void merge(int[] src,int[] dst,int low,int mid,int hi){
int lowIndex=low;
int hiIndex=mid+1;
for(int i=low;i<=hi;i++){
if(lowIndex>mid){
dst[i]=src[hiIndex++];
}else if(hiIndex>hi){
dst[i]=src[lowIndex++];
}else if (src[lowIndex]<src[hiIndex]) {
dst[i]=src[lowIndex++];
}else{
dst[i]=src[hiIndex++];
}
}
}
}
2.2.4自底向上的歸并排序
使用歸并排序的另一種方法是 先歸并那些微型數(shù)組,然后在歸并得到的子數(shù)組,反復(fù);直到我們得到整個(gè)數(shù)組并歸并一起.這樣比標(biāo)準(zhǔn)遞歸方法需要的代碼更少.
[手搖算法,又稱三次反轉(zhuǎn)]
用于反轉(zhuǎn)字符串包括里面有不服順序改變,可以將空間復(fù)雜度降低至O(1).
具體做法.例子:
題目要求部分反轉(zhuǎn)數(shù)組叙淌。比如說(shuō)1市咆，2汉操，3，4蒙兰，5 翻轉(zhuǎn)后是3磷瘤，4，5搜变，1采缚，2
class Reverse{
private void reverse(int[] a, int low, int hi) {
while (low < hi) {
swap(a, low, hi);
low++;
hi--;
}
}
//這里也用到內(nèi)存反轉(zhuǎn)3次 進(jìn)行交換兩個(gè)數(shù) ,采用 ^操作
private void swap(int[] a, int left, int right) {
a[left] ^= a[right];
a[right] ^= a[left];
a[left] ^= a[right];
}
public static void main(String[] args) {
int[] test = {1, 2, 3, 4, 5};
Reversel rev=new Reverse();
rev.reverse(test, 0, 1);
rev.reverse(test, 2, test.length - 1);
rev.reverse(test, 0, test.length - 1);
for (int i = 0; i < test.length; i++) {
System.out.print(test[i]);
}
}
}
自底向上,的歸并排序的思路是
- 先分割成前半部分為1,后半部分的數(shù)組, 劃分成 N/2 段.
- 然后接著以分成前半部分為2,后半部分為2的數(shù)組.
- 然后接著以分成前半部分為3,后半部分為3的數(shù)組.
… - 直到每部分的步長(zhǎng)接近N 或者超過(guò)N.
/**
* Created by leon on 18-1-24.
* 這里是采用自底向上的算法
*/
public class MergeSortBottom2Up {
public void sort(int[] arr) {
System.out.println("自底向上遞歸前:" + Arrays.toString(arr));
int num = arr.length;
//翻倍遞增
for (int i = 1; i < num; i = i + i) {
for (int j = 0; j < num; j++) {
int low = Math.min(j, num - 1);
j = j + i + i - 1;/*往后移動(dòng)步長(zhǎng)*/
int high = Math.min(j, num - 1);
int mid = (low + high) / 2;
merge(arr, low, mid, high);
}
}
System.out.println("自底向上遞歸后:" + Arrays.toString(arr));
}
/**
* 進(jìn)行在一個(gè)數(shù)組里面for循環(huán),發(fā)現(xiàn)lowIndex下標(biāo)超過(guò)mid 或者 highIndex 超過(guò)high進(jìn)行切換
* 比較的思路:
* 1.lowIndex=lo,midIndex,highIndex=mid+1
* 1.從lowIndex 開(kāi)始 ++,比較src[lowIndex] 和 src[highIndex]的值,直到 src[lowIndex]>src[highIndex]停止
* 2.用midIndex 定位到highIndex
* 3.從highIndex++,直到src[highIdex]>src[lowIndex],停
* 此刻說(shuō)明從 midIndex~highIndex-1的數(shù)比lowIndex的小,需要插入到lowIndex之前.
* 利用內(nèi)存3次反轉(zhuǎn)(手搖技術(shù))反轉(zhuǎn)內(nèi)存,達(dá)到把midIndex~highIndex-1部分插入到lowIndex之前
* ____________________
* |1|3|4|5|9|10|2|6|7|
* `^``````````^`^``````
* l h =>初始 l,m,h=m+1
* ____________________
* |1|3|4|5|9|10|2|6|7|
* ```^````````^`^````
* l h =>移動(dòng)l,arr[l]>arr[h]
* ____________________
* |1|3|4|5|9|10|2|6|7|
* ```l``````````m`h``` =>把m->h位置,h++,直到arr[h]>arr[l]
*此時(shí)說(shuō)明 arr[m]~arr[h-1]的數(shù)小于 arr[l],需要進(jìn)行3次內(nèi)存反轉(zhuǎn),
*達(dá)到把a(bǔ)rr[m]~arr[h-1]排到arr[lowIndex]前面
* ____________________
* |1|3|4|5|9|10|2|6|7|
*
* ____________________
* |1|10|9|5|4|3|2|6|7|==> 反轉(zhuǎn)左邊
^ ^ ^
* ____________________
* |1|10|9|5|4|3|2|6|7|==>反轉(zhuǎn)右邊 只有一個(gè) 2
* ^ ^ ^
* ____________________
* |1|2|3|4|5|9|10|6|7|==>反轉(zhuǎn)兩部分
* ^ ^ ^
*完成一次排序,
* lowIndex=lowIndex+i+i-1;繼續(xù)下一次排序
*
* @param src
* @param lo
* @param mid
* @param hi
*/
private void merge(int[] src, int lo, int mid, int hi) {
int lowIndex = lo;
int highIndex = mid + 1;
//當(dāng) lowIndex 與highIndex 重疊時(shí).或者h(yuǎn)ighIndex超出了最外層結(jié)束
while (lowIndex < highIndex && highIndex <= hi) {
while (lowIndex < highIndex && src[lowIndex] <= src[highIndex]) {
lowIndex++;
}
int midIndex = highIndex;
//這里的邊界值很關(guān)鍵
while (highIndex <= hi && src[highIndex] < src[lowIndex]) {
highIndex++;
}
Convert(src, lowIndex, midIndex - 1, highIndex - 1);
//完成一次排序
lowIndex += highIndex - midIndex;
}
}
void Convert(int a[], int low, int M, int high) {
//反轉(zhuǎn) low...middle
reverse(a, low, M);
//反轉(zhuǎn)middle+1 high
reverse(a, M + 1, high);
//反轉(zhuǎn)low...high
reverse(a, low, high);
}
private void reverse(int[] a, int low, int hi) {
while (low < hi) {
swap(a, low, hi);
low++;
hi--;
}
}
private void swap(int[] a, int left, int right) {
a[left] ^= a[right];
a[right] ^= a[left];
a[left] ^= a[right];
}
}
2.2.5 排序算法的復(fù)雜度
研究復(fù)雜度的第一步是建立模型.一般來(lái)說(shuō)尋找與問(wèn)題相關(guān)的最簡(jiǎn)單的模型.排序算法,是基于主鍵的比較決定的.
命題I:
沒(méi)有任何基于比較的算法能夠保證使用少于lg(N!)~NlogN次比較將長(zhǎng)度為N的數(shù)組排序.
這個(gè)結(jié)論告訴我們?cè)谠O(shè)計(jì)排序時(shí)能達(dá)到的最佳效果.
命題J:
歸并排序是一種漸進(jìn)最優(yōu)的基于比較的排序算法.更準(zhǔn)確的說(shuō).歸并排序在最壞情況下的比較次數(shù)和其他基于比較的任意算法的最少時(shí)間都是~NlogN.
