算法回顾 排序

我太废了 感觉基本上是从头学起了QAQ以前的博客感觉也没啥用233333

为方便起见，以下排序后的数列均为递增数列。

1.插入排序 时间复杂度O(n^2)

基本思路：对于一串数列，从左到右扫描每一个元素，当前位置记为key。从key所在的位置倒着向前扫描，如果遇到有比key大的元素，就把这个数的位置向后移，直到找到第一个小于等于key的位置，然后把key加进去。（说的很抽象）

例如：2 1 5 3

从1开始倒着枚举，遇到2，此时2被存在a[1]中，于是让a[2]=a[1]，继续往前枚举，发现扫到头了（i==0），/*也可以预先把a[0]设置成负无穷*/，再把key插进数列中。

数列变成了：1 2 5 3

从5开始倒着枚举，遇到2之后发现2比5小，可以直接break掉；（这种做法可以保证key位置前的数一定是有序的）

接着是3，遇到5 把5向后挪，遇到2，break，把3插进去（插的位置就是5往后挪之后空出来的位置）

发现所有位置都已经枚举完了，整个数列已经有序了。

    int j=2;cnt=0;
    while(j<=n){
        int key=a[j],i=j-1;
        for(i=j-1;i>=1;--i){
            if(a[i]>key) a[i+1]=a[i];
            else break;
        }
        a[i+1]=key;++j;
    }

View Code

 2.冒泡排序（每个oier都会学到的经典23333）

可以解决逆序对相关问题。

大致思路：从第一个元素开始往后枚举，如果它比后面一个数大，就和后面一个数交换，直至当前数列中最大的数在数列末端（已经排好的默认被T出数列2333）。

例如：3 2 5 1

3比2大 swap 2 3 5 1；3小于5 不动 继续看后面一对 5比1大 swap 2 3 1 5；指针（不是严格意义上的）在第4位

接着又从头开始 2比3小 不动；3比1大 swap 2 1 3 5；指针在第三位

从头开始 2比1大 swap 1 2 3 5 指针在第2位；

时间复杂度：O（n^2）

    int j=n;
    while(j>1){
        for(int i=1;i<j;++i) if(a[i]>a[i+1]) swap(a[i],a[i+1]);
        --j;
    }

View Code

算法回顾 排序

原文：https://www.cnblogs.com/ywqqwq/p/11523338.html