北航计算机软件技术基础课程作业&笔记【5】

题目

（文章一周后公开~）

sort

1.快排算法

• 核心思路：选取（一般是）当前数组第一个元素作为中间值mid，将数组按照比mid小/大分为两半，再对子数组进行同样操作（二叉树前序遍历）

• 具体操作：主要是分2半那里，可以巧妙一些地来遍历，所以用到了left和right指针（重合时就遍历完了），同时自己写的时候用了一下right_flag表示是否要看右边与mid做比较（网上有更好的，我只是自己这样写了而已）

• 左右指针的使用规则：假设以先将right与mid值对比开始，发生了交换后，就改变判断的指针（比如right小于mid，那么交换right与left，后面就开始判断left与mid的大小关系了），否则，一直移动被判断的指针（比如right一直大于mid，那一直right--）

• 代码：

  #include 
  #include 
  #include  
  std::vector origin{78,31,46,22,81,12,55,64,8,17};
  void quick_sort(int left, int right)
  {
   
      if(left >= right)
          return;
      // 直接记录下来，懒得把数组分小了
      int start = left,end = right;
      // 确定好中间位置的值
      int mid = origin.at(left);
      std::cout << mid <
      // 先从右边开始看
      int right_flag = 1;
      // 结束时因为left=right，这就是mid元素应该放的地方
      while(left < right)
      {   
          if(right_flag)
          {
              if(origin.at(right) < mid)
              {
                  // 右边比左大，那就右边往左边放
                  std::swap(origin[left],origin[right]);
                  left++;
                  std::copy(std::begin(origin), std::end(origin), std::ost