当前位置：首页 > 算法 > 正文内容

【排序】----插入排序

亿万年的星光5年前 (2021-01-28)算法24219

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;
        */
    }
}