腳本之家服務(wù)器常用軟件

快捷導(dǎo)航

C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(二)

更新時(shí)間：2021年12月17日 15:02:39 作者：知心寶貝

這篇文章住要介紹的是選擇類排序中的簡單、樹形和堆排序，歸并排序、分配類排序的基數(shù)排序，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以了解一下

一、前言

之前的排序總結(jié)（一）對(duì)插入類和交換類排序作了比較詳細(xì)的總結(jié)，對(duì)于直接插入、希爾排序、冒泡排序、快速排序要求熟練掌握

這篇排序全面總結(jié)(二)主要介紹選擇類排序中的簡單、樹形和堆排序，歸并排序、分配類排序的基數(shù)排序

二、選擇類排序

選擇類：每次從待排序的無序序列中，選擇一個(gè)最大或最小的數(shù)字，放到前面，數(shù)據(jù)元素為空時(shí)排序結(jié)束

1.簡單選擇排序

動(dòng)態(tài)演示：

算法講解：

首先通過n-1次比較，從n個(gè)記錄中找出最小值，將它與第一個(gè)元素交換
再通過n-2次比較，從剩余的n-1個(gè)記錄中找出次小的值，將它與第二個(gè)記錄交換
重復(fù)上述操作n-1，排序完成

代碼：

void SelectSort(RecordType r[], int length)
/*對(duì)記錄數(shù)組r做簡單選擇排序，length為數(shù)組的長度*/
{
	int i,j,k;	int n;	RecordType x;    n=length;
	for ( i=1 ; i<= n-1; ++i)  
	{
		k=i;
		for (j=i+1 ; j<= n ; ++j) 
			if (r[j].key < r[k].key ) k=j;
		if ( k!=i) 
		 { 
		     x= r[i];   r[i]= r[k];   r[k]=x;
		}
	}	
} /* SelectSort  */

特點(diǎn)：?

不穩(wěn)定排序

時(shí)間復(fù)雜度O(n*n), 空間復(fù)雜度O(1)

2.樹形選擇排序

靜態(tài)演示：

算法講解：

最下面一行21 25 49 25 16 08 63是給定需要從小到大排序的數(shù)字
相鄰的兩個(gè)選出一個(gè)最小的向上移一層，只有一個(gè)的補(bǔ)一個(gè)值無窮大的數(shù)
倒數(shù)第二層再次兩兩組合，直到最頂端
此時(shí)，最頂端08就是值最小的數(shù)，輸出08，把所有08至為無窮大
再次選出一個(gè)最小值，以此類推

特點(diǎn)：?

算法不作要求

穩(wěn)定排序, 增加額外的存儲(chǔ)空間

時(shí)間復(fù)雜度O（nlogn）,空間復(fù)雜度O(n-1)

3.堆選擇排序

動(dòng)態(tài)演示：

算法講解：

根結(jié)點(diǎn)值最大的叫大頂堆，根結(jié)點(diǎn)值最小的叫小頂堆，上圖就是一個(gè)構(gòu)造大頂堆的圖
從最后一層開始，如果孩子結(jié)點(diǎn)的值比父親結(jié)點(diǎn)大，那么就交換位置
一層層向上推，直到根結(jié)點(diǎn)值最大

建立初始堆：

void crt_heap(RecordType r[], int length )
/*對(duì)記錄數(shù)組r建堆，length為數(shù)組的長度*/
{
	int i,n;
    n= length;
	for ( i=n/2; i >= 1; --i) /* 自第[n/2]個(gè)記錄開始進(jìn)行篩選建堆 */ 
		sift(r,i,n);
}

調(diào)整堆：

void  sift(RecordType  r[],  int k, int m)
/* 假設(shè)ｒ[k..m]是以ｒ[k]為根的完全二叉樹，且分別以ｒ[2k]和ｒ[2k+1]為根的左、右子樹為大根堆，調(diào)整r[k]，使整個(gè)序列r[k..m]滿足堆的性質(zhì) */
{	RecordType t;	int i,j;	int x;	int finished;
	t= r[k];          /* 暫存"根"記錄r[k] */ 	
     x=r[k].key;	i=k;	j=2*i;
	finished=FALSE;
	while( j<=m && !finished  ) 
		{     
		     if (j<m  && r[j].key< r[j+1].key )  j=j+1;   /* 若存在右子樹，
                                                     且右子樹 根的關(guān)鍵字大，則沿右分支"篩選" */
		     if ( x>= r[j].key)	finished=TRUE;            /*  篩選完畢  */ 
		     else 
		     {   r[i] = r[j];  i=j;  j=2*i;	}    /* 繼續(xù)篩選 */ 
		}
		r[i] =t;          /* r[k]填入到恰當(dāng)?shù)奈恢?*/ 
}

堆排序：

void  HeapSort(RecordType  r[],int length)
/* 對(duì)r[1..n]進(jìn)行堆排序，執(zhí)行本算法后，r中記錄按關(guān)鍵字由大到小有序排列 */ 
{
	int i,n;	RecordType b;
	crt_heap(r, length);	n= length;
	for (  i=n ; i>= 2; --i) 
	{
		b=r[1];     /* 將堆頂記錄和堆中的最后一個(gè)記錄互換 */ 
		r[1]= r[i];
		r[i]=b; 
		sift(r,1,i-1);  /* 進(jìn)行調(diào)整，使r[1..i-1]變成堆 */ 
	}
} /* HeapSort */

特點(diǎn)：?

堆選擇是樹形的改進(jìn)，空間占用較小

不穩(wěn)定排序，適合n值較大的排序

時(shí)間復(fù)雜度O(n*logn)，空間復(fù)雜度O(1)

三、歸并排序

法一：

將整體數(shù)字一分為二，逐層細(xì)分

細(xì)分完成后，每一塊進(jìn)行排序，直到整體有序

法二：

將一串序列，相鄰的兩個(gè)歸并到一起排序，再次把相鄰兩個(gè)有序的歸并塊再次排序，直到最后有序（優(yōu)先推薦這種算法）

代碼：

void MergeSort ( RecordType  r[], int n) /* 對(duì)記錄數(shù)組r[1..n]做歸并排序 */ 
{
	MSort ( r, 1, n, r);
}
void   MSort(RecordType  r1[],  int  low,  int  high,  RecordType  r3[])
/* r1[low..high]經(jīng)過排序后放在r3[low..high]中，r2[low..high]為輔助空間 */ 
{
	int mid;   RecordType  r2[20];
	if (low==high)   r3[low]=r1[low];
	else
	{
		mid=(low+high)/2;
        MSort(r1,low, mid, r2);
        MSort(r1,mid+1,high, r2);
        Merge (r2,low,mid,high, r3);
     }
} /*   MSort  */

特點(diǎn)：?

穩(wěn)定排序

時(shí)間復(fù)雜度O(nlogn)，空間復(fù)雜度O(n)

附加空間比較大，很少用于內(nèi)部排序，主要是外部排序

四、分配類排序

1.多關(guān)鍵字排序

高位優(yōu)先：按照花色大小分成四類，在每一類中按照面值進(jìn)行排序

低位優(yōu)先：按照面值大小分成13類，將相同面值的不同花色進(jìn)行排序

2.鏈?zhǔn)交鶖?shù)排序

算法講解：

對(duì)于上面的9個(gè)三位數(shù)，第一步我們按照個(gè)位數(shù)從小到大排序
接著第一步的結(jié)果，按照十位數(shù)從小到達(dá)排序
最后借助第二步的結(jié)果，按照百位數(shù)從小到大排序
同樣的，對(duì)于4位 5 位方法一樣

特點(diǎn)：

時(shí)間復(fù)雜度O(d*n)，d是關(guān)鍵字?jǐn)?shù)，n是記錄數(shù)

穩(wěn)定的排序

空間復(fù)雜度=2個(gè)隊(duì)列指針+n個(gè)指針域

五、總結(jié)歸納

到此這篇關(guān)于C語言數(shù)據(jù)結(jié)構(gòu)與算法之排序總結(jié)(二)的文章就介紹到這了,更多相關(guān)C語言數(shù)據(jù)結(jié)構(gòu) 排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: