插入排序-阿里云开发者社区

开发者社区> 开发与运维> 正文
登录阅读全文

插入排序

简介: 插入排序

Insertion Sort

对于近乎有序的数组,插入排序的时间复杂度优于O(nlogn)

对于完全有序数组,插入排序时间复杂度会降到O(n)

将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入前面有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面)

和打扑克牌类似,手中的都是排好序的,抽到一张牌后,会插入到已排好序的牌中合适位置

从第二个元素开始,往前比较

算法步骤

template<typename T>

void insertionSort(T arr[],int n){

 //从第二个元素开始插入排序,直到末尾

    for(int i=1;i<n;i++){

        //从后往前比较,如果大于前面元素,说明是在合适位置,跳出当前循环

        for(int j=i;j>0;j--){

            if(arr[j]<arr[j-1])

                swap(arr[j],arr[j-1]); 

            else

                break

        }

    }

}

上述代码虽然可以提前终止内层循环,但是时间性能测试是没有选择排序快的

int main(){

    int n=10000;

    //生成乱序数组

    int* arr=SortTestHelper::generateRandomArray(n,0,n);

    int* arr2=SortTestHelper::copyIntArray(arr,n);//复制arr得到arr2

    //测试耗时

    SortTestHelper::testSort("selectionSort",selectionSort,arr2,n);

    SortTestHelper::testSort("insertionSort",insertionSort,arr,n);

    //释放空间

    delete[] arr;

    delete[] arr2;

    return 0;

}

/*

selectionSort : 0.16 s

insertionSort : 1.484 s

*/

优化

因为swap函数进行了三次赋值,赋值是比比较操作更加耗时的,可以减少赋值从而进行改进

先将要插入的元素存储起来,再将要插入的元素依次与前面的元素进行比较,小于前面元素的话,就将前面元素赋值到当前位置,直到要插入的元素大于等于前面元素。可以看到通过一次赋值替换了交换操作(三次赋值)

template <typename T>

void insertionSortPlus(T arr[],int n){

    //第一个元素显然有序,因此我们从第二个元素开始排序,若间隔为gap,则从下标为gap开始

    for(int i=1;i<n;i++){

        //记录要进行排序的元素

        T e=arr[i];

        //j是要插入的位置

        int j;

        for(j=i;j-1>=0;j=j-1){

            if(e<arr[j-1])

                arr[j]=arr[j-1];

<<<<<<< HEAD

            else break;//明显当e>=arr[j-1]时跳出循环,说明arr[j]正是元素要插入的位置,而之前arr[j]已经后移一位

=======

            else break;//明显当e>arr[j-1]时跳出循环,说明arr[j]正是元素要插入的位置,而之前arr[j]已经后移一位

>>>>>>> 27c092bbe831973f875c92f374e0f8ec3ae3e3b4

        }

        arr[j]=e;

    }

}

selectionSort : 0.158 s

insertionSort : 0.113 s

当数据是近乎有序的,插入排序的时间复杂度甚至优于O(nlogn)

    // 生成一个近乎有序的数组,n是数组元素个数,swapTimes是指交换次数,因为数组要保持近乎有序

    int* generateNearlyOrderedArray(int n,int swapTimes){

        int* arr=new int[n];

        for(int i=0;i<n;i++)

            arr[i]=i;

        srand(time(0));

        for(int i=0;i<swapTimes;i++){

            int posx=rand()%n;

            int posy=rand()%n;

            swap(arr[posx],arr[posy]);

        }

        return arr;

    }

int main(){

    int n=10000;

    //生成近乎有序数组

    int* arr=SortTestHelper::generateNearlyOrderedArray(n,100);

    int* arr2=SortTestHelper::copyIntArray(arr,n);

    //测试耗时

    SortTestHelper::testSort("selectionSort",selectionSort,arr2,n);

    SortTestHelper::testSort("insertionSort",insertionSort,arr,n);

    //释放空间

    delete[] arr;

    delete[] arr2;

    return 0;

}

selectionSort : 0.155 s

insertionSort : 0.003 s

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章
最新文章
相关文章