该和排序算法做个了结了

15种排序算法动态演示

这个视频是在网上看到的。

那我们就跟着视频来写出这15种排序算法吧。这15种排序分别是：

1.简单选择排序
 2.插入排序
 3.快速排序
 4.合并排序
 5.堆排序
 6.基数排序
 7.最高有效位排序
 8.内省排序
 9.适应性归并排序
 10.希尔排序（缩小增量，插入排序的改进版）
11.冒泡排序
 12.鸡尾酒排序（定向冒泡，选择排序的一种）
13.地精排序（写法最简单的排序）
14.双调排序
 15.Bogo排序（等量子计算时代唯一的算法，穷举法）

选择排序

简单选择排序

简单选择排序，每次找到一个最小的。放到前面。

效率自然是 O(n2)

胜者树

类似线段树，先建树，然后区间最值，最后能得到最小值。取出。
然后删掉这个数，更新区间，得到次小。循环···
更新方法就是线段树的pushUp

插入排序

直接插入排序

加哨兵的核心：

for(int i=2;i<n;i++){
        vt[0]=vt[i];
        int j=i-1;//从i的前一个开始往前找
        for(;vt[j]>vt[0];j--)
            vt[j+1] = vt[j];//找到比哨兵大的就后移(大的在后嘛)
        vt[j+1] = vt[0];//循环走完 j+1的位置就是i的归宿 因为j的位置是比小的
              //这么一轮下来，[1,i]这一段就是有序的了
}

作用

把每次要插入的目标放到vt[0]的位置，
让循环的结束条件vt[j]>vt[0] 一定可以结束。

因为当目标值是最小的时候，第一个元素vt[1]都比目标大，**vt[1]会后移到vt[2]**上。

j-- 则 j就变成了0 。vt[0]>vt[0]不成立，循环结束。且要插入的位置正是 0+1 = 1。目标值放在了位置1上。

复杂度分析：

最好比较n-1次移动0次
最坏比较(n+2)(n-1)/2次移动(n+2)(n-1)/2次
平均：(n^2)/4 时间复杂度O(n^2)

折半插入

寻找位置的过程用折半查找，

平均比较次数 nlogn 移动次数 n^2/4

时间复杂度O(N²)

二路插入

用一个辅助链表，减少移动的次数。

最终移动次数 $n^2/8$ ，相当于以第一个元素为哨兵分成了两个比它大、小的部分，再移动这两个部分。

复杂度$O(n^2)$

希尔排序

不稳定

分别选Delta10\5\3\1为增量。然后对每个位置的数进行插入排序。

实验数据表明效率约为 N^1.3

交换类排序

冒泡排序

每一轮排序：都将【无序序列】中，关键字最大的那个一上升到【有序序列】中。

优化结束条件：本轮没有进行交换。

复杂度

最好

比较 n-1 移动 0
最坏

比较 n(n-1)/2 移动 3n(n-1)/2
O(n²)

快速排序

核心就是i和j两个坐标的移动：

while (i<j){
    while (a[j]>=temp && i<j)
        j--;
    a[i] = a[j];
    while (a[i]<=temp && i<j)
        i++;
    a[j] = a[i];
}

注意的地方：

进入快排，先把传入的i和j两个参数存起啦，最后递归的时候要用
大于等于，一定要带等于！！！不然肯定死循环（只有里面有一样的数，i和j就永远不会进入++和–,相当于你把两个一样的数字交换了位置）。
关于快排的稳定性：

之前想错了。稳定性和比较时带不带>=号没关系。因为在和其他元素比较时，a也会被移动。

优化

对于有序的情况，快排退化成On2，因此不采用每个区间的第一个元素作为“标杆”，而是用区间[i,j]的首、中、尾三个元素做比较，来做为标杆进行排序。

重点来了！

怎么让这个元素做标杆呢！我之前还在傻傻地改代码！！！

其实只要在原来的快排代码上，选出标杆之后，把标杆位置的数和i位置的数swap一下就行了啊！！！这样还是从第一个数做标杆。但第一个数已经成了我们想用的那个。
- x,y,z如何判断y是不是中间值呢？if(y>=x&&y<=z)是不对的。还要||(y<=x&&y>=z)

合并排序

归并的拆分的递归思路特别好。要记住两个函数参数怎么设。
归并要用 i,m,m+1,j

而不要用 i,m-1,m,j

举个例子 i=1,j=2

用第一个(1,1,2,2) 没问题吧

用第二个(1,0,1,2) 看到没，后面又成了1,2. 会无限循环进入1,2
合并时的条件是(i<=m && m+1<=j)

要带上等于号！

因为不能保证两个式子都是小于的。万一有一个等于就无法进入合并了。

比如(1,2,3,3) 虽然(3,3)不用处理，但是（1,2）要处理啊。
需要占用空间啊（要有个临时数组去合并结果）。

堆排序

https://www.cs.usfca.edu/~galles/visualization/HeapSort.html

v = {9999,6,9,5,6,8,2,0};//0的位置没用
void sift(int low, int high){
    int i = low, j = i*2;
    int x = v[i];
    while (j<=high){
        if(j<high && v[j]<v[j+1])
            j = j+1;//右孩子大则j指向右孩子
        if(x < v[j]){//如果x小
            v[i] = v[j];//大的上来
            i = j;      //i下移一层看
            j = i*2;    //j继续当i的儿子
        } else
            break;
    }
    v[i] = x;
}

void heapSort(int n){
    int i;
    int temp;
    for(i=n/2; i>=1; i--)
        sift(i,n);
    for(i=n; i>=2; --i){
        temp = v[1]; //备份当前最大值
        v[1] = v[i]; //把小的顶上来
        v[i] = temp; //最大的归位了
        sift(1,i-1);
    }
}