各種排序算法總結(jié)

各種排序算法總結(jié)排序算法是最基本最常用的算法，不同的排序算法在不同的場(chǎng)景或應(yīng)用中會(huì)有不同的表現(xiàn)，我們需要對(duì)各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢(shì)。今天，來(lái)總結(jié)下各種排序算法。下面這個(gè)表格總結(jié)了各種排序算法的復(fù)雜度與穩(wěn)定性：各種排序算法復(fù)雜度比較.png冒泡排序冒泡排序可謂是最經(jīng)典的排序算法了，它是基于比較的排序算法時(shí)間復(fù)雜度為O(n^2),其優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單,n較小時(shí)性能較好。算法原理相鄰的數(shù)據(jù)進(jìn)行兩兩比較，小數(shù)放在前面，大數(shù)放在后面，這樣一趟下來(lái)，最小的數(shù)就被排在了第一位，第二趟也是如此，如此類推，直到所有的數(shù)據(jù)排序完成C++代碼實(shí)現(xiàn)voidbubble_sort(intarr[],intlen)for(inti=0;i<len-1;i++)for(intj=len-1;j>=i;j--)4.if4.if(arr[j]<arr[j-1])5.inttemp=arr[j];6.arr[j]=arr[j-1];7.arr[j-1]=temp;選擇排序?算法原理先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。?C++代碼實(shí)現(xiàn)voidselect_sort(intarr[],intlen)for(inti=0;i<len;i++)3.intindex=i;for(intj=i+1;j<len;j++)if(arr[j]<arr[index])index=j;if(index!=i)inttemp=arr[i];arr[i]=arr[index];arr[index]=temp;插入排序?算法原理將數(shù)據(jù)分為兩部分，有序部分與無(wú)序部分，一開始有序部分包含第1個(gè)元素，依次將無(wú)序的元素插入到有序部分，直到所有元素有序。插入排序又分為直接插入排序、二分插入排序、鏈表插入等，這里只討論直接插入排序。它是穩(wěn)定的排序算法，時(shí)間復(fù)雜度為O(n^2)?C++代碼實(shí)現(xiàn)1.voidinsert_sort(intarr[],intlen)2.for(inti=1;i<len;i++)3.intj=i-1;4.intk=arr[i];5.while(j>-1&&k<arr[j])6.arr[j+1]=arr[j];7.j--;8.arr[j+1]=k;快速排序?算法原理快速排序是目前在實(shí)踐中非常高效的一種排序算法，它不是穩(wěn)定的排序算法，平均時(shí)間復(fù)雜度為O(nlogn)，最差情

..9.101112131415況下復(fù)雜度為O(n^2)。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。C++代碼實(shí)現(xiàn)voidquick_sort(intarr[],intleft,intright)if(left<right)inti=left,j=right,target=arr[left];while(i<j)while(i<j&&arr[j]>target)j--;if(i<j)arr[i++]=arr[j];while(i<j&&arr[i]< target).i++;.if(i<j).arr[j]=arr[i];. arr[i]=target;. quiCk_sort(arr,left,i -1);. quiCk_sort(arr,i+1, right);

歸并排序?算法原理歸并排序具體工作原理如下(假設(shè)序列共有n個(gè)元素)：將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作(merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素重復(fù)步驟2，直到所有元素排序完畢歸并排序是穩(wěn)定的排序算法，其時(shí)間復(fù)雜度為O(nlogn)，如果是使用鏈表的實(shí)現(xiàn)的話，空間復(fù)雜度可以達(dá)到O(1)，但如果是使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)的話，在歸并的過程中，需要臨時(shí)空間來(lái)存儲(chǔ)歸并好的數(shù)據(jù)所以空間復(fù)雜度為O(n)?C++代碼實(shí)現(xiàn)1.voidmerge(intarr[],inttemp_arr[],intstart_index,intmid_index,intend_index)2.inti=start_index,j=mid_index+1;3.int3.intk=0;while(i<mid_index+1&&j<end_index+1)if(arr[i]>arr[j])

.1011121314151617181920temp_arr[k++]=arr[j++];elsetemp_arr[k++]=arr[i++];while(i<mid_index+1)temp_arr[k++]=arr[i++];while(j<end_index+1)temp_arr[k++]=arr[j++];for(i=0,j=start_index;j<end_index+1;i++,j++)arr[j]=temp_arr[i];voidmerge_sort(intarr[],inttemp_arr[],intstart_index,intend_index)if(start_index<end_index)intmid_index=(start_index+end_index)/2;merge_sort(arr,temp_arr,start_index,mid_index);merge_sort(arr,temp_arr,mid_index+1,end_index);merge(arr,temp_arr,start_index,mid_index,end_index);堆排序

二叉堆二叉堆是完全二叉樹或者近似完全二叉樹，滿足兩個(gè)特性?父結(jié)點(diǎn)的鍵值總是大于或等于(小于或等于)任何一個(gè)子節(jié)點(diǎn)的鍵值?每個(gè)結(jié)點(diǎn)的左子樹與右子樹都是一個(gè)二叉堆當(dāng)父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最大堆。當(dāng)父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值時(shí)為最小堆。一般二叉樹簡(jiǎn)稱為堆。堆的存儲(chǔ)一般都是數(shù)組來(lái)存儲(chǔ)堆，i結(jié)點(diǎn)的父結(jié)點(diǎn)下標(biāo)就為(i-1)/2。它的左右子結(jié)點(diǎn)下標(biāo)分別為2*i+1與2*i+2。如第0個(gè)結(jié)點(diǎn)左右子結(jié)點(diǎn)下標(biāo)分別為1與2。存儲(chǔ)結(jié)構(gòu)如圖所示：堆結(jié)構(gòu).png堆排序原理堆排序的時(shí)間復(fù)雜度為O(nlogn)?算法原理(以最大堆為例)o先將初始數(shù)據(jù)R[1??n]建成一個(gè)最大堆，此堆為初始的無(wú)序區(qū)

..9.101112再將關(guān)鍵字最大的記錄R[1]（即堆頂）與無(wú)序區(qū)的最后一個(gè)記錄R[n]交換，由此得到新的無(wú)序區(qū)R[1??n-1]與有序區(qū)R[n],且滿足R[1?.n-1].keysWR[n]?key由于交換后新的根R[1]可能違反堆性質(zhì)，故應(yīng)將當(dāng)前無(wú)序區(qū)R[1??n-1]調(diào)整為堆。重復(fù)2、3步驟，直到無(wú)序區(qū)只有一個(gè)元素為止。C++代碼實(shí)現(xiàn)*將數(shù)組arr構(gòu)建大根堆@paramarr待調(diào)整的數(shù)組@parami待調(diào)整的數(shù)組元素的下標(biāo)@paramlen數(shù)組的長(zhǎng)度voidheap_adjust(intarr[],inti,intlen)intChild;inttemp;for(;2*i+1<len;i=Child)Child=2*i+1;//子結(jié)點(diǎn)的位置=2*父結(jié)點(diǎn)的位置+1. //得到子結(jié)點(diǎn)中鍵值較大的結(jié)點(diǎn).if(Child<len-1&&arr[Child+1]>arr[Child])Child++;

131415161718192021222324252627282930//如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng)，替換它的父結(jié)點(diǎn)if(arr[i]<arr[child])temp=arr[i];arr[i]=arr[child];arr[child]=temp;else>break;*堆排序算法voidheap_sort(intarr[],intlen)inti;//調(diào)整序列的前半部分元素，調(diào)整完之后第一個(gè)元素是序列的最大的元素for(inti=len/2-1;i>=0;i--)heap_adjust(arr,i,len);for(i=len-1;i>0;i--)//將第1個(gè)元素與當(dāng)前最后一個(gè)元素交換，保證當(dāng)前的最后一個(gè)位置的元素都是現(xiàn)在的這個(gè)序列中最大的in