數(shù)據(jù)結(jié)構(gòu)

7大排序算法總結(jié)：
首先排序分為內(nèi)排序和外排序：
內(nèi)排序是指待排序的記錄放置在內(nèi)存，而外排序是指排序的過程中需要對(duì)內(nèi)存進(jìn)行訪問。其中穩(wěn)定的排序有“插冒歸”，即插入排序、冒泡排序、歸并排序。
1.冒泡排序
算法原理：
①初始時(shí)有序區(qū)為空，即全部記錄為無序區(qū)；
②在無序區(qū)中從后往前依次比較相鄰記錄，如果是逆序，則交換
③每趟排序時(shí)，無序區(qū)關(guān)鍵字最小的記錄被逐漸交換到有序區(qū)的第一位，即加入到有序區(qū)
④如果一趟排序時(shí)沒有發(fā)生過交換，則提前結(jié)束
代碼實(shí)現(xiàn)：

void BubbleSort(ElemType L[],int n){
	int i,j;
	bool exchange;//記錄是否發(fā)生交換的標(biāo)志
	ElemType tem;
	for(i=0;i<n-1;i++){//最多進(jìn)行n-1趟冒泡排序
		exchange=false;
		for(j=n-1;j>i;j--){//一趟冒泡排序
			if(L[j]<L[j-1]){//前大后小，即逆序就交換
				tem=L[j];
				L[j]=L[j-1];
				L[j-1]=tem;
				//交換過之后就改變exchange的值
				exchange=true;
			}
			if(exchange==false){
				return;
			}
		}
	}
}

冒泡排序的算法評(píng)價(jià)：
1>待排序序列為正序：比較次數(shù)n-1，交換次數(shù)為0；
2>待排序序列為逆序：比較次數(shù)為 n(n-1)/2,交換次數(shù)為 n(n-1)/2
2.快速排序
每趟排序使一個(gè)元素放入其最終位置，這一個(gè)元素稱為樞軸，通常選排序的第一個(gè)元素。
樞軸把整個(gè)序列劃分為兩個(gè)子序列，利用遞歸分別對(duì)子序列重復(fù)上述相同過程，直至子序列長度為0或1為止。
劃分方法：
選待排序列的第一個(gè)元素作為樞軸x
設(shè)置變量：
low指向序列的前端
high指向序列的后端
high和low依次從序列的兩端交替向序列中央掃描，將小于x的元素移到樞軸的左邊，將大于或等于x的元素移到樞軸的右邊
代碼實(shí)現(xiàn)

void QuickSort(ElemType L[],int s,int e){
	int low=s,high=e;//本次劃分范圍
	ElemType x = L[s];//序列第一個(gè)元素作為樞軸
	whlie(low<high){//內(nèi)循環(huán)①從右到左查找比樞軸小的元素
		while(low<high&&L[high]>=x){
			high--;
		}
		L[low]=L[high];//將小數(shù)放在左側(cè)小數(shù)序列中，內(nèi)循環(huán)②從左到右查找比樞軸大或相等的元素
		while(low<high&&L[low]<x){
			low++;
		}
		L[high]=L[low];//將大數(shù)放在右側(cè)大數(shù)序列中
	}//循壞結(jié)束時(shí)low、high重合
	L[low]=x;//確定樞軸的最終存放位置
	if(s<low-1) QuickSort(L,s,low-1);//對(duì)左側(cè)小數(shù)序列進(jìn)行遞歸劃分
	if(high+1<e) QuickSort();//對(duì)右側(cè)大數(shù)序列進(jìn)行遞歸劃分
}

算法性能分析：
時(shí)間復(fù)雜度：最好情況，每次都選到的是中間值作為樞軸O(nlog${}_2$n)；最壞情況，每次總是選到最小或最大元素作樞軸O(n²)
空間復(fù)雜度：需要?？臻g實(shí)現(xiàn)遞歸
3.歸并排序
歸并排序?qū)蓚€(gè)或多個(gè)有序序列合并為一個(gè)新的有序序列的過程，最簡單的歸并排序就是將兩個(gè)有序序列合并為一個(gè)有序序列的過程，稱為二路歸并排序。
注意：只含有一個(gè)記錄的序列顯然是有序序列，將一個(gè)長度為n的無序序列看成是由n個(gè)長度為1的有序子序列組成。
把有些子序列中相鄰的子序列兩兩歸并，得到n/2個(gè)長度為2的有序子序列。
再把這些子序列兩兩歸并，如此重復(fù)，直至形成一個(gè)長度為n的有序序列。
算法性能分析：
時(shí)間復(fù)雜度：O(nlog${}_2$n)，每一趟歸并的時(shí)間復(fù)雜度為O(n)，總共需要進(jìn)行l(wèi)og${}_2$n趟
4.直接插入排序
序列分為有序區(qū)和無序區(qū)。每次取無序區(qū)的第一個(gè)元素按其關(guān)鍵字大小插入到有序區(qū)的適當(dāng)位置。
初始時(shí)，指定待排序的第一個(gè)元素構(gòu)成有序區(qū)。其余元素構(gòu)成無序區(qū)。
每趟排序時(shí)，待插入元素為無序區(qū)的第一個(gè)元素。
從后向前比較，當(dāng)前元素如大于待插入元素，則向后移動(dòng)。
每次插入后，有序區(qū)增加一個(gè)元素，無序區(qū)減少一個(gè)元素
無序區(qū)為空時(shí)，排序結(jié)束。
性能分析：
基本操作：比較和移動(dòng)的次數(shù)，決定了排序的時(shí)間性能。
待排序列為“正序”時(shí)，比較和移動(dòng)的次數(shù)最少；
待排序列為“逆序”時(shí)，比較和移動(dòng)的次數(shù)最多。
5.簡單選擇排序
序列分為有序區(qū)和無序區(qū)。每次從無序區(qū)選出關(guān)鍵字最小的元素與無序區(qū)的第一個(gè)元素交換，此時(shí)有序區(qū)多一個(gè)元素。
要點(diǎn)：
初始時(shí)，有序區(qū)為空，全部元素位于無序區(qū)
每趟排序時(shí)，選擇無序區(qū)關(guān)鍵字最小的元素與無序區(qū)的第一個(gè)元素交換
每次選擇并交換后，有序區(qū)增加一個(gè)元素，無序區(qū)減少一個(gè)元素
當(dāng)無序區(qū)剩下最后一個(gè)元素時(shí)，排序即可結(jié)束。
6.希爾排序
本質(zhì)上是在插入排序算法的基礎(chǔ)上進(jìn)行的改進(jìn)，就是先將待排序列分割成若干子序列分別進(jìn)行插入排序，待整個(gè)序列中的記錄“基本有序“時(shí)，再對(duì)全體記錄進(jìn)行一次直接插入排序
首先選擇一個(gè)增量序列t1,t2……tk.令tk=1
按增量序列個(gè)數(shù)k，對(duì)序列進(jìn)行k趟排序
每趟排序，根據(jù)對(duì)應(yīng)的增量ti，將待排序列分割成若干長度為m的子序列，分別對(duì)各子表進(jìn)行直接插入排序。僅增量因子為1時(shí)，整個(gè)序列作為一個(gè)表來處理，表長度即為整個(gè)序列的長度。
7.堆排序
即要滿足堆積的性質(zhì)，即子結(jié)點(diǎn)的鍵值一定大于或小于其父結(jié)點(diǎn)（根節(jié)點(diǎn)），其中每個(gè)結(jié)點(diǎn)的值大于等于其左右孩子結(jié)點(diǎn)的值，稱為大根堆（大頂堆），反之，若每個(gè)結(jié)點(diǎn)的值都小于等于其左右孩子結(jié)點(diǎn)的值，稱為小根堆（小頂堆）。
原理：
1.將初始待排關(guān)鍵字序列（R1，R2…………Rn）構(gòu)建成大頂堆，此堆為初始的無序區(qū)；
2.將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無序區(qū)（R1，R2…………Rn-1）和新的有序區(qū)（Rn）,且滿足R[1,2，……n-1]<=R[n].
3.由于交換后新的堆頂R[1]可能會(huì)違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無序區(qū)調(diào)整為新堆，然后再次將R[1]與無序區(qū)最后一個(gè)元素交換，得到新的無序區(qū)和新的有序區(qū)。不斷重復(fù)此過程直到有序區(qū)的元素個(gè)數(shù)為n-1，則排序完。文章來源地址http://www.zghlxwxcb.cn/news/detail-617032.html

到了這里，關(guān)于408復(fù)試day2(7大排序算法)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！