直接插入排序，折半插入排序和冒泡排序思想以及实现（c语言）

末蓝、 2023-05-30 09:18 52阅读 0赞

## 直接插入排序 ##

**算法思想：**  
直接插入排序的基本操作是将第 i 个记录插入到前面 i-1 个已经排好序的记录中。

具体过程为：将第 i 个记录的关键字 K 依次与前面排好序的关键字比较，如果比较的关键字大于 K ，则将该关键字后移一位，直至遇到小于 K 的关键字或到序列头部，然后将 K 插入到该关键字后面或序列头部（之前比较过的已经后移一位，所以会留有一个空位置供 K 插入）。

**算法描述：**

> void InSort(RecordType r\[\],int length)  
> //length 为数组中待排序记录的数目  
> \{  
> 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\];//将待插入记录插入到已排序的序列中  
> \}  
> \}

*完整代码：*

#include<stdio.h>
    void insSort(int a[],int lengh){ 
    	int i = 1;//i从数组的第二个位置开始，前面只有一个数，所以是排好序的
    	for(;i<lengh;i++){ 
    		int x = a[i];//x为监视哨，记录待插入的关键字值
    		int j = i-1;//j = j-1 --> 要和关键字x比较的是 i 之前的序列
    		while(x<a[j]){ 
    			a[j+1] = a[j];//大于x就后移
    			j--;
    		}
    		a[j+1] = x;//将关键字插入到空位置
    	}
    }
    int main()
    { 
    	int a[] = { 48,62,35,77,55,14,35,98};//可以改为输入序列，此处只是为了方便快速理解
    	int lengh = sizeof(a)/sizeof(a[0]);//sizeof(a)/sizeof(a[0])求数组长度
    	insSort(a,lengh);
    	int i = 0;
    	for(;i<lengh;i++){ 
    		printf("%d,",a[i]);
    	}
    	return 0;
     }

要理解直接插入排序有两点：  
（1）：要对第 i 个记录进行排序，那么他之前的序列一定是排好序的  
（2）：要对第 i 个记录进行排序，一定是从第 i-1 个关键字开始比较

## 折半插入排序 ##

**算法思想：**  
我们知道，在查找算法中，折半查找对于有序表的查找性能优于顺序查找，所以也可以将折半查找思想用于插入排序中来确定插入位置。

**算法描述：**

> void BinSort(RecordType r\[\],int length)  
> \{  
> 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; //插入记录（此处的 low 不能改为 high ,因为 high 一定是小于插入位置的）  
> \}  
> \}

*完整代码：*

#include<stdio.h>
    
    void BinSort(int a[],int lengh){ 
    	int i = 1;//从数组的第二位开始
    	for(;i<lengh;++i){ 
    		int x = a[i];//记录关键字的值
    		int low = 0;
    		int high = i-1;
    		while(low<=high){ 
    			int mid = (low + high)/2;
    			if(x<a[mid]){ 
    				high = mid-1;
    			}
    			else{ 
    				low = mid+1;
    			}
    		}
    		int j = i-1;
    		for(;j>=low;--j){ 
    		a[j+1] = a[j];
    		}	a[low] = x;
    	}
    }
    
    int main()
    { 
    	int a[] = { 48,62,35,77,55,14,35,98};
    	int lengh = sizeof(a)/sizeof(a[0]);
    	BinSort(a,lengh);
    	int i = 0;
    	for(;i<lengh;i++){ 
    		printf("%d,",a[i]);
    	}
    	return 0;
    }

## 冒泡排序 ##

**算法思想：**  
反复扫描待排序序列，每一趟将最大（或最小）的数值放在最后面  
即：相邻两个关键字进行比较，逆序就交换位置  
每进行一趟比较，下一趟比较的序列就不必再比较上一趟的最后一位

**算法描述：**

> void BubbleSort(RecorType r\[\],int length)  
> \{  
> change = ture;//保证每进行一次后就少一位；  
> for(i = 1;i<=length && 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 = ture;  
> \}  
> \}  
> \}  
> \}

*完整代码：*

#include<stdio.h>
    
    void bubblesort(int a[],int n){ 
    	int i = 0;
    	for(i = 0;i<n;i++){ 
    		int j = 0;
    		for(;j<n-1;j++){ //算法思想中此处 j<n-i,本程序里写的是j<n-1,相当于每次都将整个序列比较一遍，多执行了多余的步骤，大家写的时候按照算法思想来写，此处就当作一个不完美的示范吧
    			if(a[j]>a[j+1]){ //交换数值
    				int x = a[j];
    				a[j] = a[j+1];
    				a[j+1] = x;
    			}
    		}
    	}
    }
    
    int main()
    { 
    	int a[] = { 5,8,4,53,45,78,6,54};
    	int n = sizeof(a)/sizeof(a[0]);
    	bubblesort(a,n);
    	int i = 0;
    	for(;i<n;i++){ 
    		printf("%d,",a[i]);
    	} 
    	return 0;
     }

突然想到，冒泡中的 j 的范围可与写为 j<n-i-1;也可以省略算法思想中的change步骤，且效率一样。

**总结：**  
笔者最近正在重新学习数据结构，接下来是算法，所以会将数据结构中所有的重点难点加以总结，有不对的地方希望大佬指出，我不要面子的哈哈