漫談經典排序算法:二、各種插入排序解析及性能比較

1、序言

這是《漫談經典排序算法系列》第二篇，解析了各種插入排序算法。主要包括：直接插入排序、折半插入排序、表插入排序、希爾插入排序。每一種算法的開頭都叙述了引出該算法的原因，然後給出代碼，最後分析算法效率及和其他插入排序相比，優劣在哪裡。

各種排序算法的解析請參考如下：

《漫談經典排序算法:一、從簡單選擇排序到堆排序的深度解析》

《漫談經典排序算法:二、各種插入排序解析及性能比較》

《漫談經典排序算法:三、冒泡排序 && 快速排序》

《漫談經典排序算法:四、歸并排序》

《漫談經典排序算法:五、線性時間排序(計數、基數、桶排序)》

《漫談經典排序算法:六、各種排序算法總結》

注：為了叙述友善，本文以及源代碼中均不考慮A[0],預設下标從1開始。

2、直接插入排序

2.1 引出

給定待排序序列A[ 1.....n ]，現假設A[1...i]已經有序，那麼我們取出A[i+1]插入到序列A[1...i].這樣有序序列記錄數就增加了1.如此重複上述操作，不斷取出記錄插入有序序列，直到A[n]插入到有序序列，排序完成。

2.2 代碼
//直接插入排序
void  straightInsertSort(int *a,int n)
{
	int i,j;
	int temp;
	//逐個記錄插入有序序列
	for(i=2;i<=n;i++){
		temp=a[i];
		//把a[i]插入有序序列
		for(j=i-1;j>=1;j--){
			if(temp<a[j]){
				a[j+1]=a[j];
			}else
				break;
		}
		a[j+1]=temp;
	}
}
           
2.3 效率分析
容易看出，要插入的記錄個數為n-1，其中關鍵字的比較次數和記錄移動次數是依賴于給出的待排序序列是否基本有序。在最佳情況下（待排序序列有序），比較次數和移動次數時間為o（1），是以時間複雜度為o（n）.在最壞情況下（待排序序列逆序）和平均時間均為o（n^2）.從上述分析中可以看出，直接插入排序适合記錄數比較少、給定序列基本有序的情況。熟悉了排序過程我們發現，直接插入排序是一種穩定的原地排序算法。

3、折半插入排序

3.1 引出
在直接插入排序過程中，我們是把一個記錄插入到有序序列中，至于要插入到有序序列中的哪個位置呢？采用的是順序查找确定插入的位置。顯然對于有序序列，折半查找的效率要高，是以在尋找插入位置時可以用折半查找。折半查找主要分為三步：1、查找要插入的位置 2、移位 3、把記錄插入相應的位置。
3.2 代碼
//折半查找
int binarySearch(int *a,int low,int high,int key)
{
	int mid=(low+high)/2;
	if(low>high)
		return low;
	if(a[mid]==key)
		return mid;
	else if(key<a[mid])
		return binarySearch(a,low,mid-1,key);
	else 
		return binarySearch(a,mid+1,high,key);
}

//折半插入排序
void binaryInsertSort(int *a,int n)
{
	int i,j,site,temp;
	for(i=2;i<=n;i++){
		//1.折半查找要插入的位置
        site=binarySearch(a,1,i,a[i]);
		temp=a[i];
		//2.移位
		for(j=i;j>site;j--)
			a[j]=a[j-1];
		//3.插入a[i]
		a[site]=temp;
	}
}
           
3.3 效率分析
折半插入排序是對直接插入排序的一種改進，這種改進隻考慮了關鍵字比較次數，并沒有減少移位次數，是以平均時間和最壞情況下（待排序序列逆序）時間複雜度o（n^2）,如果記錄數量很大的話，這兩種情況下是優于直接插入排序。再來看一下最佳情況（待排序序列有序），此時關鍵字比較次數并不為o（1），時間複雜度為o（n*log2n）。（其中折半查找時間複雜度o（log2n），這個在以後寫查找的時候再分析，這裡不做詳細講解。）。是以在記錄數較小、待排序序列基本有序情況下直接插入排序優于折半插入排序。此外，折半插入排序是不穩定的原地排序，實作起來也較複雜。

4、表插入排序

4.1 引出
折半插入排序相對于直接插入排序來說減少了比較次數。那麼我們可不可以減少移動次數呢，答案是可以的。于是就有了表插入排序，用一個靜态連結清單來存儲待排序序列，其他操作和直接插入排序很像。主要步驟：1、初始化連結清單 2、取出要插入的記錄 3、周遊連結清單尋找插入位置 4、記錄插傳入連結表中。
4.2 代碼
//靜态連結清單
typedef struct
{
	int key;//關鍵字
	int next;//指向下一個關鍵字的下标
}Node,*PNode;

//表插入排序
void tableInsertSort(PNode list,int n)
{
	int p,head;
	int i;
	//初始化
	list[0].next=1;
	list[1].next=0;
   
    //逐個插入
	for(i=2;i<=n;i++){
		head=0;
		p=list[0].next;
		//周遊連結清單，尋找插入位置
		while(p!=0 && list[p].key<=list[i].key){
			head=p;
			p=list[p].next;
		}
		if(p==0){//插入的值是最大值
     		list[i].next=p;
	     	list[head].next=i;
		}else{
			list[i].next=p;
			list[head].next=i;
		}

	}
}
           
4.3 效率分析
表插入排序也是對直接插入排序的一種改進，這種改進隻減少了移動次數，并沒有減少關鍵字比較次數，是以平均時間和最壞情況下（待排序序列逆序）時間複雜度o（n^2）,如果記錄數量很大的話，這兩種情況下是優于直接插入排序。再來看一下最佳情況（待排序序列有序），關鍵字比較次數并為o（1），時間複雜度為o（n）。此時和直接插入排序時間複雜度一樣。此外，表插入排序改變了記錄的存儲結構，無法順序通路，是一種穩定的排序算法，實作起來也較複雜。

5、希爾插入排序

5.1 引出
上述兩種排序都是隻考慮減少關鍵字比較次數或者隻考慮減少關鍵字移動次數。有沒有别的改進辦法呢？我們注意到，直接插入排序适合于記錄數較少、基本有序的情況。于是我們可以先将整個待排序序列分割成若幹子序列分别進行直接插入排序，整個序列基本有序時，再對序列進行一次直接插入排序。這就是希爾排序。
5.2 代碼
//一趟增量為dk的希爾插入排序
void  shellInsert(int *a,int n,int dk)
{
	int i,j,temp;
	for(i=dk+1;i<=n;i+=dk){
		temp=a[i];
		for(j=i-dk;j>=0;j-=dk)
			if(a[j]>temp)
				a[j+dk]=a[j];
			else
				break;
		a[j+dk]=temp;
	}
}

//希爾排序
void shellSort(int *a,int n)
{
	int i;
	int dk[]={5,4,3,2,1};
	for(i=0;i<5;i++)
		shellInsert(a,6,dk[i]);
}
           
5.3 效率分析
當給定序列記錄量較大時，希爾排序性能優于直接插入排序。再希爾排序的過程中，關鍵字是跳躍式移動的，這樣就減少了移動次數。希爾排序性能的分析是一個複雜的問題，時間與所取的增量有關。增量選取的不好可能會大大降低排序效率。

6、附錄

附錄一、參考書籍

《資料結構》嚴蔚敏版

附錄二、所有源代碼

#include<stdio.h>

//直接插入排序
void  straightInsertSort(int *a,int n)
{
	int i,j;
	int temp;
	//逐個記錄插入有序序列
	for(i=2;i<=n;i++){
		temp=a[i];
		//把a[i]插入有序序列
		for(j=i-1;j>=1;j--){
			if(temp<a[j]){
				a[j+1]=a[j];
			}else
				break;
		}
		a[j+1]=temp;
	}
}


void main()
{
	int i;
	int a[7]={0,3,5,8,9,1,2};//不考慮a[0]
	straightInsertSort(a,6);
	for(i=1;i<=6;i++)
		printf("%-4d",a[i]);
	printf("\n");
}

#include<stdio.h>

//折半查找
int binarySearch(int *a,int low,int high,int key)
{
	int mid=(low+high)/2;
	if(low>high)
		return low;
	if(a[mid]==key)
		return mid;
	else if(key<a[mid])
		return binarySearch(a,low,mid-1,key);
	else 
		return binarySearch(a,mid+1,high,key);
}

//折半插入排序
void binaryInsertSort(int *a,int n)
{
	int i,j,site,temp;
	for(i=2;i<=n;i++){
		//1.折半查找要插入的位置
        site=binarySearch(a,1,i,a[i]);
		temp=a[i];
		//2.移位
		for(j=i;j>site;j--)
			a[j]=a[j-1];
		//3.插入a[i]
		a[site]=temp;
	}
}

void main()
{
	int i;
	int a[7]={0,3,5,8,9,1,2};//不考慮a[0]
	binaryInsertSort(a,6);
	for(i=1;i<=6;i++)
		printf("%-4d",a[i]);
	printf("\n");
}

#include<stdio.h>
#define MAX 10000

//靜态連結清單
typedef struct
{
	int key;//關鍵字
	int next;//指向下一個關鍵字的下标
}Node,*PNode;

//表插入排序
void tableInsertSort(PNode list,int n)
{
	int p,head;
	int i;
	//初始化
	list[0].next=1;
	list[1].next=0;
   
    //逐個插入
	for(i=2;i<=n;i++){
		head=0;
		p=list[0].next;
		//周遊連結清單，尋找插入位置
		while(p!=0 && list[p].key<=list[i].key){
			head=p;
			p=list[p].next;
		}
		if(p==0){//插入的值是最大值
     		list[i].next=p;
	     	list[head].next=i;
		}else{
			list[i].next=p;
			list[head].next=i;
		}

	}
}

void main()
{
	int p;
	Node list[7]={MAX,0,3,0,5,0,8,0,9,0,1,0,2,0};
    tableInsertSort(list,6);
	p=list[0].next;
    while(p!=0){
		printf("%-4d",list[p].key);
		p=list[p].next;
	}
	printf("\n");
}

#include<stdio.h>

//一趟增量為dk的希爾插入排序
void  shellInsert(int *a,int n,int dk)
{
	int i,j,temp;
	for(i=dk+1;i<=n;i+=dk){
		temp=a[i];
		for(j=i-dk;j>=0;j-=dk)
			if(a[j]>temp)
				a[j+dk]=a[j];
			else
				break;
		a[j+dk]=temp;
	}
}

//希爾排序
void shellSort(int *a,int n)
{
	int i;
	int dk[]={5,4,3,2,1};
	for(i=0;i<5;i++)
		shellInsert(a,6,dk[i]);
}

void main()
{
	int i;
	int a[7]={0,3,5,8,9,1,2};//不考慮a[0]
	shellSort(a,6);
	for(i=1;i<=6;i++)
		printf("%-4d",a[i]);
	printf("\n");
}

漫談經典排序算法:二、各種插入排序解析及性能比較

1、序言

2、直接插入排序

2.1 引出

2.2 代碼

2.3 效率分析

3、折半插入排序

3.1 引出

3.2 代碼

3.3 效率分析

4、表插入排序

4.1 引出

4.2 代碼

4.3 效率分析

5、希爾插入排序

5.1 引出

5.2 代碼

5.3 效率分析

6、附錄

附錄一、參考書籍

附錄二、所有源代碼

繼續閱讀

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

【資料結構】醫院選址

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

[轉]ISUP信令的IAM消息詳細内容

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希