考研排序

主要分为两类：

1. 内排序：排序的数据量不是很大完全可以放到内存
2. 外排序：数据量很大，需要访问外部

主要学习：

①算法流程——能够自己写出代码理解整个过程
②运行效率：
1.时间复杂度：最好情况、平均情况、最坏情况
2.空间复杂度
3.稳定性

时间复杂度的研究因素：

1. 比较次数（基于比较的排序占主要）（时间复杂度的下界：O(nlogn)）
2. 移动次数

插入排序（Insert sort）

直接插入排序，这是我自己的理解方法：

摸牌法：
想象你打扑克牌的时候，摸牌阶段把一张张的牌用右手摸起，跟左手上的牌目测一下大小并放入顺序的位置上，这就是整个插入排序的过程。

转化成代码：（上机用得不多）

//直接插入排序（没有任何优化的插入排序）
//这里默认全局，所以省略参数列表int q[],int n
void insert_sort()  
{
    for (int i = 1;i < n;i ++)
    {
        int t = q[i], j = i;
        while (j && q[j - 1] > t)
        {
            q[j] = q[j - 1];
            j --;
        }
        q[j] = t;
    }
}

分析：

1. 时间复杂度：
   ①最好情况：O(n)
   ②平均情况：假设每一次插入的概率是相等的平均遍历i/2次，则大致为n^2/4的，即O(n^2)
   ③最坏情况：O(n^2)
2. 辅助空间复杂度：不需要开额外的数组O(1)
3. 稳定性：每一次只会把比基数大的元素往后移动，所以遇到相等元素不会发生改变，因此稳定。

优化方法：

基于每一次排序的时候，前面一段元素都是排好的列 ，因此，我们可以加入二分找到比当前元素大的第一个元素，最后将这个元素以后的所有元素往后移动即可，整个优化过程就是减少了比较次数,那么比较次数优化为：logn,但是移动次数不能优化,所以虽然进行了优化但是效果在实际操作中并不是很显著，但是考研要考，就学吧

我们也将这种优化方法称之为：折半插入排序法

具体实现代码：

//还是老样子，默认数组全局变量
void binary_search_insert_sort()
{
    for (int i = 1; i < n; i ++ )   //第一数不需要
    {
        //如果前面所有有序的元素都比当前元素小，那么就不需要二分直接pass掉
        //pass的方法很简单直接跟前一个元素比,如果小的话，就直接跳过即可
        if (q[i-1] <= q[i]) continue;   
        int t = q[i];
        //二分
        int l = 0, r = i - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] > t) r = mid;
            else    l = mid + 1;
        }
        //找到之后，把r到i-1的所有元素后移
        for (int j = i - 1; j >= r; j -- )
            q[j + 1] = q[j];
        q[r] = t;
    }
}

分析:折半插入排序所有分析跟直接插入排序是一样的，虽然有优化，但时间复杂度没有本质区别，瓶颈在移动次数上。

冒泡排序（Bubble sorting）

这玩意C语言老师都讲过，要展开细讲了就是有辱各位大佬的智商了，要是有新手的话，大致说一下就行

简单描述：

冒泡排序会循环很多次，
第一次将最小的元素冒到开头，
第二次会将倒数第二小的元素冒到开头，
第三次会将倒数第三小的元素冒到开头....
那么第i次就是将第i个元素放到它所正确的位置上，
因此要迭代n-1次就够了，每一次冒出过程就是相邻元素之间对比交换，说人话就是按顺序将所有邻居跟邻居之间对比，不符合顺序就交换，整个迭代一次所达到的结果，就是将最小的元素冒到开头，每一次冒到开头的元素都是最小元素按顺序排的所以排好序的开头元素就不用管了，将后面所有元素再循环重复上面操作就是迭代的过程
不懂了自己模拟一下数据就出来了

优化：

这玩意要真有人让你优化了，那也只能这样了
如果，在执行过程中，迭代一轮之后，发现没有元素交换，那就说明全部是有序的元素，就立个Flag直接结束循环即可

没听懂？直接看代码，模拟：

//老样子，还是省略参数，用全局数组变量
void bubble_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        bool flag = false;  //立个flag,用于优化跳出
        //0~i是冒出来的排好序的
        //因此每次从最后一对邻居开始判断，到第i个就停止
        for (int j = n - 1; j > i ; j --)
            if(q[j] < q[j - 1])
            {
                swap(q[j], q[j - 1]);   //交换数组元素的函数
                flag = true;            //交换过就说明还没有排好序
            }
        if (!flag)  break;              
        //如果一轮结束了，还是false，就说明排好序了，就跳出
    }
}

分析：

1. 时间复杂度:
   ①最好情况：就是整个序列是有序的，直接O(n)
   ②平均情况：每一次让着整个序列的逆序对减一，逆序对平均有O(n)级别，整个下来就是O(n^2)
   ③最坏情况：有n^2个逆序对O(n^2)
2. 空间复杂度:
   这里直接教你们个小技巧,一个算法如果没有开额外的数组,
   也没有递归过的话,那么它的额外空间复杂度是O(1)的,这个也是一样
3. 稳定性:每次交换两个元素的时候,如果相邻两个元素是相等的话,是不会交换的,就不会改变,相邻元素的相对位置,所以是稳定的

一般把代码搞懂问题就不大,代码就是精确的执行过程和操作流程,总比死记八股文强

简单选择排序（Select sort）

也就是基于冒泡的简单调但效率依然很慢,简述一下:

从左到右,依次选中一个位置作为基准位置,
然后,循环基准位置往后的所有元素,并不断判断,
选出最小的元素的下标记录下来,一轮循环后,把最小元素
同基准位置上的元素进行交换,然后基准位置往下移,重复循环整个过程即可

快上代码:

void select_sort()  //简单选择排序
{
    for (int i = 0;i < n;i ++)
    {
        int k = i;
        for (int j = i + 1; j< n ;j ++)
            if(q[j] < q[k])
                k = j;
        swap(q[i],q[k]);
    }
}

分析：

1. 时间复杂度:
   ①最好情况：O(n^2)
   ②平均情况：O(n^2)
   ③最坏情况：O(n^2)
2. 空间复杂度:O(1)
3. 稳定性:不稳定,
   举个栗子:2 2 1 -> 1 2 2排完序以后,
   第一个2本来是在第二个2的前面,结果排完序以后,第一个2跑到了最后面,因此选择排序不是稳定排序

注意:说实话,稳定不稳定不影响写代码上机,因为实践过程中真的遇见需要处理排序稳定的问题了,设置成双关键字稳不稳定全都变得稳定了,笔试要考没办法学吧!

以上所有排序的代码整合完整代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#define N 100010
using namespace std;

int n;
int q[N];

void insert_sort()  //插入排序int q[],int n
{
    for (int i = 1;i < n;i ++)
    {
        int t = q[i], j = i;
        while (j && q[j - 1] > t)
        {
            q[j] = q[j - 1];
            j --;
        }
        q[j] = t;
    }
}

void binary_search_insert_sort()
{
    for (int i = 1; i < n; i ++ )   //第一数不需要
    {
        //如果前面所有有序的元素都比当前元素小，那么就不需要二分直接pass掉
        //pass的方法很简单直接跟前一个元素比,如果小的话，就直接跳过即可
        if (q[i-1] <= q[i]) continue;   
        int t = q[i];
        //二分
        int l = 0, r = i - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (q[mid] > t) r = mid;
            else    l = mid + 1;
        }
        //找到之后，把r到i-1的所有元素后移
        for (int j = i - 1; j >= r; j -- )
            q[j + 1] = q[j];
        q[r] = t;
    }
}

void bubble_sort()
{
    for (int i = 0; i < n; i ++ )
    {
        bool flag = false;  //立个flag,用于优化跳出
        //0~i是冒出来的排好序的
        //因此每次从最后一对邻居开始判断，到第i个就停止
        for (int j = n - 1; j > i ; j --)
            if(q[j] < q[j - 1])
            {
                swap(q[j], q[j - 1]);   //交换数组元素的函数
                flag = true;            //交换过就说明还没有排好序
            }
        if (!flag)  break;              
        //如果一轮结束了，还是false，就说明排好序了，就跳出
    }
}

void select_sort()  //简单选择排序
{
    for (int i = 0;i < n;i ++)
    {
        int k = i;
        for (int j = i + 1; j< n ;j ++)
            if(q[j] < q[k])
                k = j;
        swap(q[i],q[k]);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )   scanf("%d",&q[i]);

    //insert_sort();
    //binary_search_insert_sort()
    //bubble_sort();
    select_sort();

    for (int i = 0; i < n; i ++ )   printf("%d ",q[i]);
    return 0;
}

听到这，你是不是感觉自己又行了？那就接着学

考研要点之高级排序的总结:
https://www.acwing.com/file_system/file/content/whole/index/content/4244336/