插入排序

问题

特点

对于少量元素的排序，它是一个有效的算法。

理解

我觉得<<算法导论>>中讲的通俗易懂，引用至此：

插入排序的工作方式就像整理扑克牌。

开始时，我们的左手为空并且桌子上放着我们还没摸的牌（PS：他们都朝下放置在桌面上，等等这好像不重要吧）。然后我们每次从桌子上拿走一张牌并将它插入到左手中正确的位置（想想你打扑克牌的场景，是不是每摸一张就排下序=。=）。

为了找到一张牌的正确位置，我们从右到左将它一一与手中的每张牌进行比较。因此拿在左手上的牌总是排序好的。

代码

1. 首先输入n个数字

   int main(){
   	int n;
   	while(~scanf("%d",&n)){
   		int *arr=new int[n];  //用指针开了动态数组，其他方法也可（毕竟这种容易出错）
           
   		for(int i=0;i<n;i++)
   			scanf("%d",&arr[i]); //输入n个数	
           
   		insertion_sort(arr,n); //调用“插入排序”函数
           
   		for(int i=0;i<n;i++){
   			printf("%d ",arr[i]); //将结果输出
   		}
   		printf("\n");
           
   		delete []arr; //释放内存
   	}
   }

2. insertion_sort()定义如下：

   void insertion_sort(int arr[],int n){
   	for(int i=1;i<n;i++){ //从第二张牌开始
   		int key=arr[i]; //key为当前摸得牌
   		int j=i-1; //j为左手拿的牌的最大的那个
   		while(j>=0 && arr[j]>key){ //比较进行的条件，左手有牌且摸得牌还是比较小
   			arr[j+1]=arr[j]; //把左手本轮参与比较的牌往右挪出一个牌的位置
   			j=j-1; //换更小的牌
   		}
   		arr[j+1]=key;
           //循环后的结果有两种：
   		//1.左手没牌了
   		//2.当前左手这个牌比摸得牌还小、
   		//无论哪种情况只需要将arr[j+1]=key即可
   	}
   }

3. 总代码：

   #include<cstdio>
   
   void insertion_sort(int arr[],int n){
   	for(int i=1;i<n;i++){ //从第二张牌开始
   		int key=arr[i]; //key为当前摸得牌
   		int j=i-1; //j为左手拿的牌的最大的那个
   		while(j>=0 && arr[j]>key){ //比较进行的条件，左手有牌且摸得牌还是比较小
   			arr[j+1]=arr[j]; //把左手本轮参与比较的牌往右挪出一个牌的位置
   			j=j-1; //换更小的牌
   		}		
   		arr[j+1]=key;
   		//循环后的结果有两种：
   		//1.左手没牌了
   		//2.当前左手这个牌比摸得牌还小、
   		//无论哪种情况只需要将arr[j+1]=key即可
   	}
   }
   int main(){
   	int n;
   	while(~scanf("%d",&n)){
   		int *arr=new int[n];  //用指针开了动态数组，其他方法也可（毕竟这种容易出错）
   		for(int i=0;i<n;i++)
   			scanf("%d",&arr[i]); //输入n个数		
   		insertion_sort(arr,n); //调用“插入排序”函数
   		for(int i=0;i<n;i++){
   			printf("%d ",arr[i]); //将结果输出
   		}
   		printf("\n");
   		delete []arr; //释放内存
   	}
   }