二分及快速排序

CopyRightbyCDD2017年11月28日二分及排序2021/5/91二分查找2021/5/92二分查找2021/5/932021/5/94二分查找2021/5/95二分查找2021/5/962021/5/97快速排序2021/5/98快速排序2021/5/99快速排序2021/5/910基準(zhǔn)只是一個(gè)比較數(shù)字，可以隨機(jī)使用，它在排序中也共同參與排序，沒(méi)有特殊化。參考程序代碼2021/5/9112021/5/912歸并排序歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（DivideandConquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱(chēng)為二路歸并。例如有8個(gè)數(shù)據(jù)需要排序：104638257歸并排序主要分兩大步：分解、合并。合并過(guò)程為：比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個(gè)有序表中的元素a[i]復(fù)制到r[k]中，并令i和k分別加上1；否則將第二個(gè)有序表中的元素a[j]復(fù)制到r[k]中，并令j和k分別加上1，如此循環(huán)下去，直到其中一個(gè)有序表取完，然后再將另一個(gè)有序表中剩余的元素復(fù)制到r中從下標(biāo)k到下標(biāo)t的單元。歸并排序的算法我們通常用遞歸實(shí)現(xiàn)，先把待排序區(qū)間[s,t]以中點(diǎn)二分，接著把左邊子區(qū)間排序，再把右邊子區(qū)間排序，最后把左區(qū)間和右區(qū)間用一次歸并操作合并成有序的區(qū)間[s,t]。2021/5/913歸并排序動(dòng)態(tài)圖示2021/5/914【程序?qū)崿F(xiàn)】voidmsort(ints,intt){if(s==t)return;//如果只有一個(gè)數(shù)字則返回，無(wú)須排序

intmid=(s+t)/2;msort(s,mid);//分解左序列

msort(mid+1,t);//分解右序列

inti=s,j=mid+1,k=s;//接下來(lái)合并while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[i];k++;i++;}else{r[k]=a[j];k++;j++;}}while(i<=mid)//復(fù)制左邊子序列剩余{r[k]=a[i];k++;i++;}while(j<=t)//復(fù)制右邊子序列剩余{r[k]=a[j];k++;j++;}for(inti=s;i<=t;i++)a[i]=r[i];return0;}歸并排序的時(shí)間復(fù)雜度是O(nlogn)，速度快。同時(shí)，歸并排序是穩(wěn)定的排序。即相等的元素的順序不會(huì)改變。如輸入記錄1(1)3(2)2(3)2(4)5(5)(括號(hào)中是記錄的關(guān)鍵字)時(shí)輸出的1(1)2(3)2(4)3(2)5(5)中的2和2