[数据结构与算法]插入排序

O(∩_∩)O 冲冲冲！！！

1.插入排序

思路是依次挑一个关键字插入前面已排好顺序的数组中。

 14 void insert_sort(int arr[],int N){	//arr为数组名，N为数组长度（升序排列）
 15     int i;
 16     int j;
 17     for(i=1;i<N;i++){	/*把数组的第二个元素作为关键字插入到前面，
 							刚开始前面就一个元素，所以已经有序了*/
 18         int key=arr[i];	//保存key值，arr[i]的值会被覆盖
 19         for(j=i-1;j>=0&&arr[j]>key;--j){	//找到小于key的下标
 20             arr[j+1]=arr[j];				//把大于key的值进行拷贝，
 21         }
 22         if(i!=j+1){
 23             arr[j+1]=key;					/*找到小于key的下标，即j，
 													所以把j+1的值置为key*/
 24         }
 25     }
 26 }

2.折半插入排序

折半插入排序相比于插入排序，只是优化了找到小于key值得下标的次数（当数组元素很多时）

 28 void bininsert_sort(int arr[],int n){
 29     int left,right,mid;
 30     int i,j,key;
 31     for(i=1;i<n;i++){
 32         key=arr[i];
 33         for(left=0,right=i-1;left<=right;){		//折半查找的思想
 34             mid=(left+right)/2;
 35             if(key>arr[mid]){
 36                 left=mid+1;
 37             }else{
 38                 right=mid-1;
 39             }
 40         }
 41         for(j=i-1;j>right;--j){	//拷贝大于key的值
 42             arr[j+1]=arr[j];
 43         }
 44         if(j+1!=i){
 45             arr[j+1]=key;
 46         }
 47     }
 48 }

3.二路插入排序

 52 void tworoad_sort(int arr[],int n){
 53     int *brr = sbrk(sizeof(arr[0])*n);  //申请动态内存，并将值初始化为0
 54     int left = -1,right = n;
 55     int i,j;
 56     for(i = 0;i < n;i++){
 57         if(left == -1 ||arr[i] > brr[0]){ //大于brr[0]的值插入左侧，进行插入排序
 58             for(j = left;j >= 0 && arr[i]<brr[j];--j){
 59                 brr[j+1] = brr[j];
 60             }
 61             brr[j+1]=arr[i];
 62             ++left;
 63         }else{	//不大于brr[0]的值插入右端，进行插入排序
 64             for(j = right;j < n && arr[i] > brr[j];j++){
 65                 brr[j-1] = brr[j];
 66             }
 67             brr[j-1] = arr[i];
 68             --right;
 69         }
 70     }
 71     i=0;	//把brr中左右端已经有序的根据下标 left 和 righ 逐个放回到arr中
 72     for(j = right;j < n;j++){
 73         arr[i++] = brr[j];
 74     }
 75     for(j=0;j <= left;j++){
 76         arr[i++] = brr[j];
 77     }
 78     brk(brr);
 79 }

4.测试代码

#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>

//打印数组
void print(int arr[],int n){
	for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
}



//插入排序
void insert_sort(int arr[],int N){
	int i;
	int j;
	for(i=1;i<N;i++){
		int key=arr[i];
		for(j=i-1;j>=0&&arr[j]>key;--j){
			arr[j+1]=arr[j];
		}
		if(i!=j+1){
			arr[j+1]=key;
		}
	}	
}

void bininsert_sort(int arr[],int n){
	int left,right,mid;
	int i,j,key;
	for(i=1;i<n;i++){
		key=arr[i];
		for(left=0,right=i-1;left<=right;){
			mid=(left+right)/2;
			if(key>arr[mid]){
				left=mid+1;
			}else{
				right=mid-1;
			}
		}
		for(j=i-1;j>right;--j){
			arr[j+1]=arr[j];
		}
		if(j+1!=i){
			arr[j+1]=key;
		}
	}
}

void tworoad_sort(int arr[],int n){
	int *brr = sbrk(sizeof(arr[0])*n);
	int left = -1,right = n;
	int i,j;
	for(i = 0;i < n;i++){
		if(left == -1 ||arr[i] > brr[0]){
			for(j = left;j >= 0 && arr[i]<brr[j];--j){
				brr[j+1] = brr[j];
			}
			brr[j+1]=arr[i];
			++left;
		}else{
			for(j = right;j < n && arr[i] > brr[j];j++){
				brr[j-1] = brr[j];
			}
			brr[j-1] = arr[i];
			--right;
		}
	}
	i=0;
	for(j = right;j < n;j++){
		arr[i++] = brr[j];
	}
	for(j=0;j <= left;j++){
		arr[i++] = brr[j];
	}
	brk(brr);
}