C语言排序算法（三）

叁歲伎倆 2022-05-23 10:54 200阅读 0赞

直接[插入排序][Link 1]：一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。由于数组是一个连续的顺序表结构体，它的插入不能直接插入，只能靠数组的移动产生空位然后插入，那么从哪开始又要到呢？这时就需要哨兵的作用。

那么什么叫做哨兵呢？实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。所以哨兵的作用如下：

① 进人查找(插入位置)循环之前，它保存了R\[i\]的副本，使不致于因记录后移而丢失R\[i\]的内容；

② 它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R\[0\].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

它的基本思想是：

先把第一个元素作为基点，与下一个元素进行比较，看是否需要交换位置，这样依次进行，例如下面过程：

![20180607150903998][]

具体实现如下：

方法一：

#include<stdio.h>
    #include<iostream>
    using namespace std;
    void print(int a[],int n,int i){
    	cout<<i<<":";
    	for(int j=0;j<n;j++){
    		cout<<a[j]<<" ";
    	}
    	cout<<endl;
    }
    void InsetSort(int a[],int n){
    	for(int i=1;i<n;i++){
    		if(a[i]<a[i-1]){
    			int x=a[i];//保存插入的元素
    			int j=i-1;//保存插入的位置
    			a[i]=a[i-1];//将数组后移
    			while(x<a[j]){
    				a[j+1]=a[j];//插入元素
    				j--;
    			}
    			a[j+1]=x;
    		}
    			print(a,n,i);
    	}
    
    }
    int main(){
    	int a[8]={3,2,5,8,4,7,6,9};
    	InsetSort(a,8);
    	print(a,8,8);
    }

方法二：因为我们发现当我们把当前元素设置为哨兵时，在该哨兵元素之前的元素都是有序排列，我们可以借助这一特点建立起循环将在此之前的元素与之进行比较，当它与第一个元素比较不成立时，就可以立即跳出循环

#include<stdio.h> 
    #include<stdlib.h>
    void InsertSort(int a[],int n){
    	int i,j,x;
    	for(i=1;i<8;i++){
    		x=a[i];
    		for(j=i-1;j>-1;j--){
    			if(a[j]>x) a[j+1]=a[j];
    			else break;
    		}
    		a[j+1]=x; 
    	}
    }
    int main(void){
    	int a[8]={3,2,5,8,4,7,6,9};
    	InsertSort(a,8);
    	for(int j=0;j<8;j++){
    		printf("%5d",a[j]);
    	}
    	return 0;
    }

方法三：其实就是将上一方法中的代码进行简化，我们就可以不考虑不成立的情况，设置条件让循环一直走下去并完成相关的步骤即可

#include<stdio.h> 
    #include<stdlib.h>
    void InsertSort(int a[],int n){
    	int i,j,x;
    	for(i=1;i<8;i++){
    		x=a[i];
    		for(j=i-1;j>-1&&a[j]>x;a[j+1]=a[j],j--);
    		a[j+1]=x; 
    	}
    }
    int main(void){
    	int a[8]={3,2,5,8,4,7,6,9};
    	InsertSort(a,8);
    	for(int j=0;j<8;j++){
    		printf("%5d",a[j]);
    	}
    	return 0;
    }

分析：通过以上三种方法我们可知：直接插入排序作为插入排序中的一种，它的时间复杂度为O（n^2），并且我们发现如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

[Link 1]: https://baike.baidu.com/item/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F
[20180607150903998]: /images/20220523/2c2ea10d000c42bcbed02d72c17bbaa5.png