【算法速查】万字图解带你快速入门八大排序(下）

即使走的再远，也勿忘启程时的初心

C/C++ 游戏开发

Hello,米娜桑们，这里是君兮_，首先在这里祝大家中秋国庆双节同乐！！抓住假期的小尾巴，今天来把算法速查的八大排序的后续写完，当然由于篇幅的原因不是每一种算法都详解，这篇文章更多是作为让初学者有一个初步的了解以及学过的人某个排序算法忘了的话的快速回忆，后续我也会把每种算法的重点以及难点挑出来单独为大家讲解的

• 好了废话不多说，开始我们今天的学习吧！！

  八大排序

  • 前言
  • 五.冒泡排序
  • 六.快速排序
  • • 1.hoare版本
    • 2.挖坑版本
    • 3.前后指针版本
    • 七.归并排序
    • • 非递归实现
      • 八.计数排序
      • 几种排序对比
      • • 不同排序的适用场景
        • 稳定性以及时/空间复杂度对比
        • 总结

          前言

          • 在开始前，我们还是通过一张图片带大家认识一下有哪八大排序

            

          • 之前我们已经讲了什么是排序以及前面的四种排序，具体内容在以下链接

            【算法速查】一篇文章带你快速入门八大排序(上）

          • 今天我们来讲讲后面四种排序

            五.冒泡排序

            • 在我们日常的应用中，实际上由于冒泡排序的时间复杂度实在是太高，我们几乎不会用到，但由于冒泡排序比较简单，它通常出现在课堂上帮助大家入门排序算法
            • 由于比较简单，这里就不详细讲了，感兴趣可以看看我之前写过的这篇博客

              【C语言初阶】带你玩转C语言中的数组，并逐步实现冒泡排序，三子棋，扫雷

            • 这里是冒泡排序的动图

              

              void Qsort(int* a, int n)
              {
                  assert(a);//断言防止越界
                  for (int i = 0; i  a[j + 1])
                          {
                              a[j + 1] = a[j];
                              a[j] = tmp;
                          }
                      }
                  }
              }
              int main()
              {
                  int a[5] = { 5,6,2,9,0 };
                  Qsort(a, 5);
                  for (int i = 0; i  
              六.快速排序
               
              

              • 相信很多人都听过快速排序的顶顶大名，什么排序算法这么狂，敢叫快速排序，根本不把其他算法放在眼里

                

              • 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中

                的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右

                子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

              • 下面我们来讲讲三种实现快速排序的方法

                1.hoare版本

                • 这是由Hoare提出的最初的快速排序，具体的排序是这样的

                  

                  基本思想：

                  1.确定一个key值，先让右走，遇到比key值大的就继续走，遇到比key值小的就停下，此时让左走，遇到比key小的就继续走，遇到比key大的就停下，此时交换两者的值，让比key大的值到右边，比key小的值到左边

                  2.重复上述的循环，直到左右两者相遇，此时交换key和此时左右相遇位置的值，由于我们是让右先走的，如果此时相遇的位置的值比key大，它不可能停下，也就是说，两者相遇位置的值一定是比key小的，交换后，我们就实现了一趟快排循环，此时key右边的值一定大于等于key，key左边的值一定小于等于key值

                  3.以key为界限，把key左边和key右边的数据继续进行单趟快排的操作，直至该数组中所有数据都有序，完成快速排序

                  Swap(int* p1, int* p2)
                  {
                      int tmp = *p1;
                      *p1 = *p2;
                      *p2 = tmp;
                  }
                  int getMid(int* a, int left, int right)
                  {
                      assert(a);
                      int mid = (left + right) / 2;
                      if (a[left] > a[mid])
                      {
                          if (a[mid] > a[right])
                              return mid;
                          else if(a[right]>a[left])
                          {
                              return left;
                          }
                          else
                          {
                              return right;
                          }
                      }
                      else
                      {
                          if (a[mid]  a[right])
                          {
                              return left;
                          }
                          else
                          {
                              return right;
                          }
                      }
                  }
                  int PartSort1(int* a, int left, int right)
                  {
                      int mid = getMid(a, left, right);//三数取中
                      //把取好的key放到left中
                      Swap(&a[left], &a[mid]);
                      int key = left;
                      while (left
                      //右边先走
                          while (left