如何進行C語言數據結構與算法中的排序總結

蝸牛 互聯網技術資訊 2021-12-17 63 0

這篇文章將為大家詳細講解有關如何進行C語言數據結構與算法中的排序總結,文章內容質量較高,因此小編分享給大家做個參考,希望大家閱讀完這篇文章后對相關知識有一定的了解。

    一、前言

    學習目標:

    排序和查找密不可分,將待處理的數據按關鍵值大小有序排列后,查找更加快速準確

    理解各種排序算法的定義和特點,并能將代碼靈活運用

    掌握各種排序方法時間復雜度與空間復雜度

    理解排序穩定和不穩定的概念? ? ? ? ? ? ? ??

    重點和難點: 希爾、快速、堆、歸并排序這幾種快速排序

    二、基本概念

    1.排序

    定義:將一個無序的數據元素任意序列,重新排列成有序的過程

    代碼:

    typedef?struct{??
    ???????int?key;???//假設關鍵字為int型
    ???????OtherType??other_data;
    }?RecordType;

    2.排序方法的穩定性

    0 1 2 3 4 5 6 7 8 9
    5 4 10 11 22 8 10 76 1 2

    解讀:如上個表格這樣的一個無序數組,想要將它按照從小到大排序。上圖下標2和6對應的數字都是10,排序后假如紅色的10任然在黑色的10前面,那這種排序方法就是穩定的,否則排序方法不穩定。

    3.內部和外部排序

    • 內部排序:整個排序過程在內存中

    • 外部排序:需要排序的數過大,需要借助外部設備

    三、插入類排序

    插入類:在一個有序序列插入一個新的記錄,使之仍然有序

    1.直接插入排序

    動態演示:

    如何進行C語言數據結構與算法中的排序總結  c語言 第1張

    算法講解:?

    1. 上面的動態圖可以很好的表達直接插入的過程,只是動態圖有點長

    2. 首先將0作為監視哨,用一個指針從前往后找后面的數字比前面數字小的,找到了放到0

    3. 指針開始向前移動,如果指向的值比監視哨里的值大,數字向后移

    4. 如果指向的值比監視哨里的值小,那把監視哨里的值存入這個元素之后

    5. 以此類推

    代碼:

    void?InsSort(RecordType??r[],??int?length)
    /*?對記錄數組r做直接插入排序,length為數組中待排序記錄的數目*/
    {?
    	int?i,j;
    	for?(i=2;??i<=length;??i++)?
    	{
    		r[0]=r[i];??????/*將待插入記錄存放到監視哨r[0]中*/
    		j=i-1;	?????????
    		while?(r[0].key<?r[j].key?)?????/*?尋找插入位置?*/
    		{
    			r[j+1]=?r[j];?
    			j=j-1;
    		}
    		r[j+1]=r[0];	/*將待插入記錄插入到已排序的序列中*/
    	}
    }?/*??InsSort??*/

    特點:?

    穩定排序

    時間復雜度O(n*n), 空間復雜度O(1)

    2.折半插入排序

    如何進行C語言數據結構與算法中的排序總結  c語言 第2張

    算法講解:

    1. 動態圖沒找到,只能用上面這張圖片了

    2. 折半插入和折半查找思想差不多,對于一個有序的數組,將一個數字插入之后任然有序

    3. k=要插入的值? low=1, high=length , mid=(low+high)+1? ?mid對應的值比k大, high=low-1,否則 low=mid+1,

    4. 當low >high ,low后面就是k插入的位置

    代碼:

    void?BinSort?(RecordType??r[],??int?length)
    /*對記錄數組r進行折半插入排序,length為數組的長度*/
    {
    	int?i,j;
    ????RecordType?x;	
    ????int?low,high,mid;
    	for?(i=2;?i<=length?;?++i?)?
    	{
    		x=?r[i];??low=1;??high=i-1;
    		while?(low<=high?)??????????????????/*?確定插入位置*/?
    		{
    			mid=(low+high)?/?2;
    			if?(?x.key<?r[mid].key)?high=mid-1;
    			else?	low=mid+1;
    		}
    		for?(?j=i-1?;?j>=?low;?--j?)???r[j+1]=?r[j];????/*??記錄依次向后移動?*/?
    		r[low]=x;???/*?插入記錄?*/?
    	}
    }/*BinSort*/

    特點:?

    穩定排序

    時間復雜度O(n*n), 空間復雜度O(1)

    3.希爾排序

    動態演示:

    如何進行C語言數據結構與算法中的排序總結  c語言 第3張

    算法講解:?

    1. 對于希爾排序來說取增量 d (d一般為奇數,并且逐次遞減)

    2. 上圖第一次排序d等于5,將第一個作為起始點,下標+5取下一個值,一直到最后,將去到的值從小到達排序,然后將第二個作為起始點,3 4 5依次作為起始點排序

    3. 第二次是d等于3

    4. 第三次是d等于1

    代碼:

    void??ShellInsert(RecordType?r[],?int?length,??int??delta)
    /*對記錄數組r做一趟希爾插入排序,length為數組的長度,delta?為增量*/
    {	int?i,j;
    	for(i=1+delta;i<=?length;?i++)?????/*?1+delta為第一個子序列的第二個元素的下標?*/
    		if(r[i].key?<?r[i-delta].key)
    		{
    			r[0]=?r[i];??????????/*??備份r[i]??(不做監視哨)?*/
    			for(j=i-delta;?j>0?&&r[0].key?<?r[j].key;?j-=delta)
    				r[j+delta]=?r[j];
    				r[j+delta]=?r[0];
    		}
    }/*ShellInsert*/

    特點:

    不穩定排序方法

    增量序列的d取值無除1之外的公因子,最后一個增量值必須為1

    時間復雜度O(nlogn)? 空間復雜度O(1)

    四、交換類排序

    1.冒泡排序

    動態演示:

    如何進行C語言數據結構與算法中的排序總結  c語言 第4張

    算法講解:?

    1. 設立兩個指針,i,j

    2. 每一次排序都會把最大的一個數放到后面,依次類推,假設執行2次以后,那么最后2個數就不需要比較了

    3. 執行n-1次排序,結果完成

    代碼:

    void??BubbleSort(RecordType?r[],?int?length?)
    /*對記錄數組r做冒泡排序,length為數組的長度*/
    {	int?n,i,j;?nt?change;?RecordType?x;?n=length;??change=TRUE;
    		for?(?i=1?;?i<=?n-1?&&?change?;++i?)?
    		{	change=FALSE;
    				for?(?j=1?;?j<=?n-i?;?++j)?
    					if?(r[j].key?>?r[j+1].key?)??
    					{
    						x=?r[j];
    						r[j]=?r[j+1];
    						r[j+1]=?x;
    						change=TRUE;
    					}?
    		}
    }?/*??BubbleSort

    特點:

    穩定排序

    時間復雜度O(n*n), 空間復雜度O(1)

    2.快速排序

    動態演示:

    如何進行C語言數據結構與算法中的排序總結  c語言 第5張

    算法講解:

    1. 快速排序講起來稍微有點復雜,其實就是劃分區域

    2. 建立兩個指針low high 分別指向第一個和第二個元素,把第一個元素的值賦給x變量

    3. high向前移動,假如high指向的值小于x,則high指向的值與x互換

    4. low向后移動,假如low指向的值大于x,則low指向的值與x互換

    5. 重復3 4兩步,知道high==low,第一次結束

    6. 將low指向第二個元素,把第二個元素的值賦給x變量

    7. 重復操作,知道元素有序

    代碼:

    1.遞歸算法:

    void?QKSort(RecordType?r[],int?low,?int?high?)
    /*對記錄數組r[low..high]用快速排序算法進行排序*/
    {
    	int?pos;
    	if(low<high)
    	{
    		pos=QKPass(r,?low,?high);??/*調用一趟快速排序,將樞軸元素為界劃分兩個子表*/
    		QKSort(r,?low,?pos-1);?????/*對左部子表快速排序*/
    		QKSort(r,?pos+1,?high);?/*對右部子表快速排序*/
    		
    	}
    }

    2.非遞歸算法:

    int?QKPass(RecordType?r[],int?left,int?right)
    /*對記錄數組r?中的r[left]至r[right]部分進行一趟排序,并得到基準的位置,使得排序后的結果滿足其之后(前)的記錄的關鍵字均不小于(大于)于基準記錄*/
    {?
    	RecordType?x;	int?low,high;
    	x=?r[left];?????????????/*?選擇基準記錄*/?
    	low=left;??	high=right;
    	while?(?low<high?)
    	{
    		while?(low<?high?&&?r[high].key>=x.key?)???/*?high從右到左找小于x.key的記錄?*/
    			high--;
    		if?(?low?<high?)?{r[low]=?r[high];??low++;}??/*?找到小于x.key的記錄,則進行交換*/
    		while?(low<high?&&?r[low].key<x.key??)???/*?low從左到右找大于x.key的記錄?*/
    			low++;?
    		if?(??low<high??){?r[high]=?r[low];?high--;?}?/*?找到大于x.key的記錄,則交換*/
    	}
    	r[low]=x;?????????????????????/*將基準記錄保存到low=high的位置*/
    	return?low;?????????????????????/*返回基準記錄的位置*/
    }?/*?QKPass?*/

    特點:

    不穩定排序,但內部排序中公認效率最好的一種

    時間復雜度O(nlogn)? 空間復雜度O(logn)

    五、總結比較

    如何進行C語言數據結構與算法中的排序總結  c語言 第6張

    關于如何進行C語言數據結構與算法中的排序總結就分享到這里了,希望以上內容可以對大家有一定的幫助,可以學到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。

    免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:niceseo99@gmail.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

    評論

    日本韩欧美一级A片在线观看