排序算法小汇总

关于排序算法汇总，有一篇文章写的非常清楚☞https://www.cnblogs.com/ll409546297/p/10956960.html，这里我就不赘述了。

（以下不成熟的东西请不要看，救命，这写的啥，乱七八糟的（来自两年后的、自己的嘲讽哈哈），还不完整，咋写着写着跑了呢，跑了还真就弃之不顾了，真真负心（忘了估计）🙈，今天翻草稿才发现）

​ 今天对几种排序算法（插入排序，希尔排序，选择排序，堆排序，快速排序，冒泡排序）做个小小的记录。

老样子，先是准备工作，引入头文件：

    #include <iostream>
    #include <algorithm>
    #include <time.h>
    #include <iomanip>
    #include <queue>
    using namespace std;

    void putArray(int a[],int n)    //输出数组
    {
        for(int i=1; i<=n; i++)
            cout<<setw(4) a[i] ; //setw设置输出元素的距离 
        cout<<endl;
    }

插入排序

思路简介：

​ 将一组数分为两部分，前一部分是排好序的数，后一部分是未排好序的数，将未排好序的数n与排好序的数一一比较，找到n的位置，通过交换或赋值将n排好序，对所有未排好序的数重复上述操作，直到所有数都排好序。
eg:对于一组数：1 3 2 4 3，初始时只有1一个数是排好序的，3 2 4 6是未排好序的，从第一个未排好序的数3开始与第一个排好序的数1比较，3大于1，3在1的后面（升序排序），3在正确的位置，不动，3已经与所有排好序的数进行了比较并找到其正确位置，3排好序。排好序的有1，3，未排好序的有2 4 6，从2开始与1比较，2大于1，2的位置不动，接下来2与3比较，2小于3，2与3交换，2已经与所有排好序的数进行了比较且找到其正确的位置，2排好序。那么，排好序的部分：1 2 3，未排好序的部分：4 3.....依次类推，直到最后后一个数排好序。
插入排序是最稳定的排序算法，排好序的数一个一个增加，直到最后一个未排好序的数也排好序。

代码：

    void InsertionSort (int a[],int n,int dk = 1)  
    {//dk是数组中进行排序数的跨度，选择排序默认跨度为1，即一次性将所有数排好序
        int i,j;
        
        for(i=1+dk; i<=n; i+=dk)  //默认第一个数已经有序 
        {
            int t = a[i];     //t记录未排好序的数 
            //将未排好序的数t依次与前面排好序的数a[j]比较,找到 t的位置
            for(j=i-dk; j>=0 && a[j]>t; j-=dk)
                a[j+dk] = a[j];
                
            a[j+dk] = t;
        }
    }

希尔排序

思路简介：

​ 先将几个数排好序，那么后来再进行排序所需比较和值交换的次数会减少，总的来说，这样排序所需要的比较与交换的次数比原始的将所有数进行排序所需要的比较与值交换的次数少得多。
希尔排序是先将几个具有一定跨度的数排好序，减小数与数之间的跨度重复上述操作，最后的跨度为1，即将所有的数进行排序。
eg：对于一组数：4 2 1 6 3 5 7 8，先将4 6 7排好序7 6 4（跨度为3）那么要排序的数为：7 2 1 6 3 5 4 8，再将7 1 3 4 排好序7 4 3 1（跨度为2），那么要排序的数为：7 2 4 6 3 5 1 8最后将7 2 4 6 3 5 1 排序为 8 7 6 5 4 3 2 1。一般来说设置三个跨度{5，3，1}就可以将所有数较高效的排好序。

代码：

    /**缩小增量的希尔排序*/
    void shell(int a[],int n)
    {
        int dk[]={5,3,1};
        
        for(int i=0; i<3; i++)
        {
            InsertionSort(a,n,dk[i]); 
        }
    }

选择排序

思路简介：

选择排序老经典的排序算法了，第一个学的排序算法就是它。
将所有相邻的数两两相比较，找到最大的数放在数列最后一个，那么最大的数已经找到位置排好序。除去最后一个数，将其他相邻的数两两相比较，找到最大的数（整个数列第二大的数），放在数列的倒数第二个数，那么第二大的数已经找到位置排好序。除去排好序的后两个数，将其他相邻的数两两相比较，找到最大的数（整个数列第三大的数），放在数列的倒数第三个数，那么第三大的数已经找到位置排好序。依次类推，直到所有数都找到位置排好序。（写的不清楚，赶时间，待更，代码应该很好懂）

代码：

    /*简单的选择排序*/
    void selectSort(int a[],int n)
    {
        int i,j,k;

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

堆排序

堆

堆是一个完全二叉树，堆分为大顶堆和小顶堆。大顶堆：每个父结点的值都大于小于其子节点的值；小顶堆：每个父结点的值都小于等于其子节点的值。若将堆中结点按从上到下从左到右从0开始进行编号，将堆中结点存放在数组中，堆中结点的编号i对应的数组下标i,该数组满足以下条件：
对编号i：

• 左孩子结点下标：2*i+1
• 右孩子结点下标：2*i+2
• 父结点下标：（i-1）/2
• 大顶堆：arr[i]>=arr[2*i+1] && arr[i]>=arr[2*i+2]（一般升序排序用大顶堆）
• 小顶堆：arr[i]<=arr[2*i+1] && arr[i]<=arr[2*i+2]（一般降序排序用小顶堆）

堆排序思路及其步骤（升序排序,共有n个元素）

思路简介

将待排序序列构造成一个大顶堆，堆顶结点元素即该序列的最大值，将该最大值与末尾元素交换，则末尾元素为最大值，除去末尾元素，其他n-1个元素未排好序。将未排好序的n-1个元素重新构造称一个大顶堆，得到第二大的元素，将第二大的元素与第n-1个元素交换，则第n-1和n个元素排好序，其余n-2个元素未排好序，将未排好序的n-2个元素重新构造成一个大顶堆...以此类推，直到所有元素排好序。

步骤

1.建堆
从左往右从下至上对结点进行调整
    首先从最后一个父节点（非叶子结点，位于倒数第二层）arr[n/2 - 1]开始，将该结点的左右子结点元素进行比较，将较大值放在左结点，将父结点元素与左结点元素比较，将较大值放在父结点。从左往右将倒数第二层的所有结点依次进行上述操作。将倒数第i层结点（起始结点为arr[n/(2^(i-1) - 1)]， i=0,1,2，3，4...n）进行上述操作直到父结点下标为0，此时建好的二叉树即为大顶堆，堆顶元素为该序列的最大值。
2.交换
    将堆顶元素arr[0]与堆尾元素arr[n-i]交换。

代码