C language implements eight sorts (1)

1. Insertion sort

What is insert sort ？

Insert sort is the simplest and most intuitive sort algorithm , It works by building an ordered sequence , For unsorted data , Scan backward and forward in sorted series , Locate and insert .

1.1 Simple insert sort

The code implementation is as follows ：

void InsertSort(int*a,int length){
	int i,j;
	for(i=1;i<length;i++){ // from 1 It starts with the subscript 0 There were no elements before  
		if(a[i]<a[i-1]){
		int key=a[i];
		j=i-1;
		while(j>=0&&key<a[j]){  // Until greater than is found a[j] Number of numbers   perhaps j=-1, Insert in first position  
			a[j+1]=a[j];
			j--;
		}
	 a[j+1]=key;	
	}
  }
}
int main(){
	int a[]={1,2,7,4,5,9,6};
	int length=sizeof(a)/sizeof(a[0]);
	InsertSort(a,length);
	for(int i=0;i<length;i++){// Print 
		printf("%d ",a[i]);
	}
	return 0;
} 

However, we believe that this insertion method can still be improved , So we created a new insertion method   -- Half insertion

Be careful ： What we implement here is sorting from small to large ！

The code implementation is as follows ：

void InsertSort(int*a,int length){
	int i,j,left,right;
	for(i=1;i<length;i++){ // from 1 It starts with the subscript 0 There were no elements before  
		int key=a[i];
		left=0;
		right=i-1;
		while(left<=right){
		 int mid = (left+right)/2;
			if(a[mid]>key){   
				right=mid-1;
			}else{
				left=mid+1;
			}
		}
		for(j=i-1;j>=right+1;j--){
			a[j+1]=a[j];
		}
	  a[right+1]=key;	
	
  }
}

1.2 Shell Sort

Hill sort is also an insert sort , We find that the closer to the basic order before sorting , The more efficient the insertion sort is , To improve our efficiency , We can sort across multiple times , Make our sorting speed as fast as possible .

The implementation code is as follows :

void ShellSort(int*a,int d,int length){
	int i,j;
	for(;d>=0;d-=2){// Gradually reduce the stride , Until 1 It becomes a normal insertion sort 
		for(i=d;i<length;i++){
			if(a[i]<a[i-d]){
				int key=a[i];
				for(j=i-d;j>=0&&key<a[j];j-=d){
					a[j+d]=a[j];
				}
				a[j+d]=key;
			}
		}
	} 
}
int main(){
	int a[]={1,2,7,4,5,9,6};
	int length=sizeof(a)/sizeof(a[0]);
	ShellSort(a,5,length); 
	for(int i=0;i<length;i++){
		printf("%d ",a[i]);
	}
	return 0;
}