六大常见排序算法（插入、堆排、希尔、选择、冒泡、快速）

多多重复，百炼成钢！！！

文章目录：

• 三、希尔排序

• 四、选择排序

• 五、冒泡排序

• 六、快速排序

• 总结

一、直接插入排序

时间复杂度（最坏情况）：O(N^2)

// 最坏时间复杂度O(N^2)-逆序
void InsertSort(int* a, int n)
{
    // 在[0,end]之间 插入 end+1，保持 [0, end+1]有序
    for (int i = 0; i < n - 1; ++i)
    {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0)
        {
            if (a[end] > tmp)
            {
                a[end + 1] = a[end];
                --end;
            }
            else
            {
                break;
            }
        }

        a[end + 1] = tmp;
    }
}

二、堆排序

时间复杂度：O(N*logN)

空间复杂度：O（N)

要求升序-建大堆

要求降序-建小堆

步骤：

1.先找到最后一个节点，然后找到他的父亲a，在a在的堆（无序），通过向下调整把该堆调整为有序（大堆或小堆）
2. 通过 i-- 找到父亲a的前一个节点b（也是另外一个堆的父亲-b），然后在父亲b所在的堆（无序）向下调整为有序
3.迭代往根方向往上走-最后整个堆都有序（大堆或小堆）

 //最后一层排好的调整次数N/2*logN 总：O(N*logN)

 void Heapsort(int* a, int n)
 {
    
     for (int i = (n - 1-1) / 2; i >= 0; --i)//n-1为最后一个节点的下标，最后一个节点的父亲下标：（最后一个节点的下标-1）/2
     {
         Adjustdown(a, n, i);
     }
     int i = 1;
     while (i < n)
     {
         swap(&a[0], &a[n - i]);//把最大的放最后，然后重新排，迭代把最大的头插到后面，排（n-1）次最后排成升序
         Adjustdown(a, n - i, 0);
         ++i;
     }
 }

向下调整

 void Adjustdown(HPDatatype* a, int n, int parent)//向下调整-O(logN)
 {
     int minchild = 2 * parent + 1;
     while (minchild < n)
     {
         if (minchild + 1 < n && a[minchild + 1] > a[minchild])
         {
             minchild++;
         }
         if (a[minchild] > a[parent])
         {
             swap(&a[minchild], &a[parent]);
             parent = minchild;
             int minchild = 2 * parent + 1;
         }
         else
         {
             break;
         }
     }
 }

三、希尔排序

时间复杂度：O(N^1.3)

gap越大，直接插入排序就越快，反而不那么有序

gap越小，直接插入排序就越慢，反而更有序

步骤：

（gap为1的时候为直接插入排序；其余gap>1时为预排序）

1.预排序-接近有序-间隔为gap的数据分为一组，插入排序

2.直接插入排序

 void ShellSort(int* a, int n)
 {
     int gap = n;
     while (gap > 1)
     {
         gap = gap / 3 + 1;
        
         for (int i = 0; i < n - gap; i++)
         {
             int end = i;
             int tmp = a[end + gap];
             while (end >= 0)
             {
                 if (a[end] > tmp)
                 {
                     a[end + gap] = a[end];
                     end -= gap;
                 }

                 else
                 {
                     break;
                 }
             }
             a[end + gap] = tmp;
         }
     }
 }

四、选择排序

时间复杂度：O(N^2)

思路：（要求升序）把第一个元素设为最小值从这里开始找，遍历一轮数组，若找到比最小值还小的元素（遍历元素里面最小的）则交换；

然后把第二个元素作为最小值从这里开始找，遍历......以此类推，到最后一个元素为止

 void SelectSort(int* a, int n)//选择排序-O（N*2）
 {
     int begin = 0;
     int end = n - 1;
     //选出最小的放begin位置
    //选出最大的放end位置

    //1.选出最大的数和最小的数
     while (begin < end)
     {
         int minii = begin;
         int maxi = begin;
         for (int i = begin + 1; i <= end; ++i)
         {
             if (a[i] > a[maxi])
             {
                 maxi = i;
             }
             if (a[i] < a[minii])
             {
                 minii = i;
             }
         }
//2.把最大的数放end位置，把最小的数放begin位置
         swap(&a[begin], &a[minii]);//最小的数放在begin位置
         if (maxi == begin)//如果一开始最大的数就在begin位置则这样判断更改bug
         {
             maxi = minii;
         }
         swap(&a[end], &a[maxi]);//最大的数放在2end位置
//3.范围缩小【begin，end】->【begin+1，end—1】
         ++begin;
         --end;
     }
 }

五、冒泡排序

时间复杂度-最坏（O（N^2)) 最好（O(N))

步骤：

升序-把最大的放最后
降序-把最小的放最后

 void BubbleSort(int* a, int n)
 {
     for (int j = 0; j < n; j++)
     {
         int exchange = 0;//优化：如果此时顺序符合升序或降序，则跳出循环
         for (int i = 1; i < n-j; i++)
         {
             if (a[i - 1] > a[i])
             {
                 swap(&a[i - 1], &a[i]);
                 exchange = 1;
             }
         }
         if (exchange == 0)
         {
             break;
         }
     }
 }

六、快速排序

A、递归实现

1.优化：三数取中：三个数当中取个数值大小为中间值的值

取出来的值作为keyi

 int Getmidindex(int* a, int left, int right)//三数取中
 {
     int mid = left + (right - left) / 2;
     if (a[left] < a[mid])
     {
         if (a[mid] < a[right])
         {
             return mid;
         }
         else if (a[left] > a[right])
         {
             return left;
         }
         else
         {
             return right;
         }
     }
     else // a[left] >= a[mid]
     {
         if (a[mid] > a[right])
         {
             return mid;
         }
         else if (a[left] < a[right])
         {
             return left;
         }
         else
         {
             return right;
         }
     }
 }

霍尔排序：

R找比keyi小的值，找到则停下； L找比keyi大的值，找到则停下； 然后L和R交换，依次到最后碰面，把keyi和碰面时的值交换，完成排序。

最后返回碰面的下标

 int PartSort(int* a, int left, int right)//霍尔排序
 {
     int mid = Getmidindex(a, left, right);
     swap(&a[mid], &a[left]);
     int keyi = left;
     while (left < right)
     {
         //R找小
         while (left < right && a[right] >= a[keyi])
         {
            --right;
         }
             //L找大
         while(left < right && a[left] <= a[keyi])
         {
            ++left;
         }

         if (left < right)
             swap(&a[left], &a[right]);
     }
     int meeti = left;
     swap(&a[keyi], &a[meeti]);
     return meeti;
 }

挖坑法

步骤：

先把key（left)所在位置作为坑位；

然后R先走，找到比keyi小的值则把该值填到坑位，然后该位置为新的坑位；

然后L走，找到比keyi大的值则把该值填到坑位，然后形成新的坑位；

以此类推，最后碰面时作为最后的坑位，把keyi填进去；

最后返回最后坑位的下标

 int PartSort2(int* a, int left, int right)//挖坑法
 {

     int mid = Getmidindex(a, left, right);
     swap(&a[mid], &a[left]);
     int key = a[left];
     int hole = left;
     while (left < right)
     {//一开始left为hole
         //R找小,找到小后就把值填到hole所在的坑，填完就为hole
         while (left < right && a[right] >= key)
         {
             --right;
         }
        
         a[hole] = a[right];
         hole = right;

         //L找大，找到大后就把值填到hole所在的坑，填完就为hole
         while (left < right && a[left] <= key)
         {
             ++left;
         }
         a[hole] = a[left];
         hole = left;
     }
    
     a[hole] = key;
     return hole;
 }

前后指针法：

步骤：

cur和prev一起走：如果cur遇到比keyi大的值则prev停下，则cur继续走，之后若遇到比keyi小的值则该值与prev所在的值交换；

以此类推，cur越界后prev停下，此时把prev所在值与keyi交换；

最后返回prev所在的下标

 int PartSort3(int* a, int left, int right)//前后指针法
 {

     int mid = Getmidindex(a, left, right);
     swap(&a[mid], &a[left]);
     int keyi =left;
     int prev = left;
     int cur = left+1;
     while (cur<=right)
     {//cur找比key大的值之后的小
         if (a[cur] < a[keyi] && ++prev != cur)//prev要和cur有间隔
             swap(&a[cur], &a[prev]);
         ++cur;
     }
     swap(&a[keyi], &a[prev]);
     return prev;
 }

以上三种方法都是一轮排序：并不能完全排好，但能把小的值放在左边，大的值放在右边（若升序）；则需要用到递归依次排序好

注：一般情况下 一轮排序最多可把8个值完全排好顺序

总排序-递归（快速排序）

停止排序： 要么剩下一个元素 要么元素不存在（越界）
时间复杂度：
无序O(NlogN)
有序O(NN)

 void QuickSort(int* a, int begin, int end)//单趟-三个区间-2^3=8（最多八个数排序好）
 {

     if (begin >= end)
     {
         return;
     }
     if (end - begin <= 8)//小区间优化：最后一趟（层）用递归消耗大-直接换插入排序
     {
        
         InsertSort(a + begin, end - begin + 1);
     }
     else {
         先对区间[begin,end]进行排序
        // int keyi = PartSort(a, begin, end);//霍尔（hoare)排序
    // int keyi = PartSort2(a, begin, end);//挖坑法
     int keyi = PartSort3(a, begin, end);//前后指针法

//经过上面排序好之后可分为区间：[begin,keyi-1],keyi,[keyi+1,end]

         //则先对区间：[begin,keyi-1]排序
        // PartSort(a, begin, keyi - 1);//霍尔排序
    //    PartSort2(a, begin, keyi - 1);//挖坑法
        PartSort3(a, begin, keyi - 1);//前后指针法

         //再对区间：[keyi+1,end]排序
         //PartSort(a, keyi + 1, end);//霍尔排序
        // PartSort2(a, keyi + 1, end);//挖坑法
         PartSort3(a, keyi + 1, end);//前后指针法
     }
 }

B、非递归实现

栈实现

思路：

若需要需要把数组[9,8,7,6,5,4,3,2,1,0]进行升序排列：

先把下标为0 9push入栈（出栈顺序为9 0 - 对应区间为[0,9]）；

然后取left=0 right=9 并且都pop掉 然后对该区间[left,right]进行排序；

然后分为两个区间[0,4] 5 [6,9]；

然后把下标为 6 9push入栈，再把 下标为 0 4 push入栈 ；

然后取left=0，right=9 并且都pop掉然后对该区域[left,right]进行排序；

然后再分区间......

以此类推

停止排序： 要么剩下一个元素 要么元素不存在（越界）

 void QuickSortNonR(int* a, int begin, int end)
 {
     ST st;
     StackInit(&st);
     StackPush(&st, begin);//放0
     StackPush(&st, end);//放9
//先出9后出0 则范围为[0,9]则是先对[0,9]范围排序
     while (!StackEmpty(&st))
     {
         int right = StackTop(&st);
         StackPop(&st);
         int left = StackTop(&st);
         StackPop(&st);
         int keyi = PartSort3(a, left, right);
         //[left,keyi-1]  keyi [keyi+1,right]
         if (keyi + 1 < right)//然后先push右边区间
         {
             StackPush(&st,keyi+1);
             StackPush(&st, right);
         }

         if (left < keyi - 1)//再push左边区间
         {
             StackPush(&st, left);
             StackPush(&st, keyi - 1);
         }

     }
     StackDestory(&st);
 }

总结

这六大排序算法非常常见且实用，你也一定要掌握好噢！！！

如果以上内容能对你有帮助的话，麻烦给我一件三联！！！（放声痛哭

不许下次一定（doge