算法—插入排序

1.基本思想

在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

2.过程

·(1)从第一个元素开始，该元素可以认为已经被排序；

·(2)取出下一个元素，在已经排序的元素序列中从后向前扫描；

·(3)如果该元素（已排序）大于新元素，将该元素移到下一位置；

·(4)重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

·(5)将新元素插入到该位置后；

·(6)重复步骤2~5。

动图演示：

3.参考代码

#include<iostream>
using namespace std;
int main() {
	int arr[]= {12,45,13,88,79,11,52,66}; //定义数组
	int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度
	int cur,i,j;
	for(i =1; i<len;i++)
	{
		cur = arr[i];  //待排序元素 
		for(j=i-1;j>=0 && arr[j]>cur;j--)
		{
			arr[j+1]=arr[j]; 
		} 
		arr[j+1]=cur;  //将待排序元素插入数组中 
		
		/*
		for(int i=0;i<len;i++)
			cout<<arr[i]<<" ";
		cout<<endl;
                */
	}
	
	 
	return 0; 
}

---

第二种写法

#include<iostream>
using namespace std;
int main()
{
	 int arr[]={12,45,13,88,79,11,52,66}; //定义数组
	 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 
 	 int i,j,k;
	 for (i =0; i < len; i++)
     {
        /*1目的是为arr[i]找到合适的位置*/
        for (j=i-1; j >= 0; j--) // 在前面有序区间中为a[i]找合适的插入位置 
            if (arr[j] <= arr[i]) //找到比a[i]小的位置就退出，插入其后 
                break;

        /*2 判断是否找到合适位置*/
        if (j != i - 1)
        {
            int temp = arr[i];
            //将比temp大的数据往后移动 
            for (k = i-1; k > j ; k--)
                arr[k+1] = arr[k];
            //将arr[i]放到合适的位置 
             arr[k+1] = temp;
        }
        
        /*
		for(int i=0;i<len;i++)
			cout<<arr[i]<<" ";
		cout<<endl;
        */
    }
	 return 0; 
}  

其他写法：

#include<iostream>
using namespace std;
int main() {
	int arr[]= {12,45,13,88,79,11,52,66}; //定义数组
	int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度
	for(int i=1; i<len; i++) { //从第2个元素开始遍历
		int temp=arr[i];//将当前位置的元素取出
		int j;
		for(j=i; j>0; j--) {
			if(temp<arr[j-1]) {//如果这个元素比temp大就覆盖，否则就证明该元素之前已经有序就break
				arr[j]=arr[j-1];//直接用前一个元素进行覆盖
			} else {
				break;
			}
		}
		//将temp中的元素插入合适位置
		arr[j]=temp;
		
	    /*
		for(int i=0;i<len;i++)
			cout<<arr[i]<<" ";
		cout<<endl;
        */
	}
}

---

#include<iostream>
using namespace std;
int main()
{
	 int arr[]={12,45,13,88,79,11,52,66}; //定义数组
	 int len =sizeof(arr) / sizeof(arr[0]); //测量数组长度 
     for(int i=1;i<len;i++){ //遍历无序部分， 
        int tmp=arr[i],j=i-1; //j为当前下标，tmp为无序部分第一个元素 
        while(j>=0&&tmp<arr[j]){ //找到k元素在有序部分的位置 
            arr[j+1]=arr[j]; //循环的时候直接右移有序数组，为tmp空出位置 
            j--; //不是tmp正确位置，继续循环往前 
        }
        arr[j+1]=tmp; //出来的时候j多减1，要加回去 
        
        /*  
		for(int i=0;i<len;i++)
			cout<<arr[i]<<" ";
		cout<<endl;
        */
    }
}

4.问题及改进

插入排序是将一个一个的元素单独进行插入，效率较慢，可以考虑把一个有序的序列直接插入到数组中，这样速度就比较快了。也就是希尔排序的思想。

---

返回目录：算法

---