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

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

一、前言

學習目標：

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

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

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

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

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

二、基本概念

1.排序

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

代碼：

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

2.排序方法的穩定性

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

3.內部和外部排序

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

• 外部排序：需要排序的數過大，需要借助外部設備

三、插入類排序

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

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.折半插入排序

算法講解：

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.希爾排序

動態演示：

算法講解： 

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.冒泡排序

動態演示：

算法講解： 

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.快速排序

動態演示：

算法講解：

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語言數據結構與算法中的排序總結就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。