花几分钟轻松搞定快速排序算法

你的名字 2022-06-05 05:05 195阅读 0赞

![这里写图片描述][SouthEast]

//快速排速算法，使用迭代 array待排序的数组, s是数组的首索引，t是最后一个元素索引
    void QuickSort(int[] array, int s, int t)
    {
          //定义变量保存被排序的数组索引
          int i = s, j = t;
           //一个元素就没有必要排序了吧，所以索引s必须小于t
          if(s < t)
          {
              //开始默认数组第一个记录做了基准点
              //什么意思呢，就是我们这个做为一个点，让其左边的都小于他，右边都大于他
              int temp = array[i];
    
              //开始两端扫描比较大小
              while(i != j) //只要i!=j  说明我们两端扫描就还没完
              {
                  while(j >= i) //开启从右端到左边的扫描
                  {
                       if(array[j] > temp)
                       {
                           //开始左移动下标
                           j--;
                       }
                       else
                       {
                         //那么需要移动当前基准点到当前比较的元素对应的索引处
                         //我们把j索引对应的元素移动到了i处,那么j处就空了一个位置
                         array[i] = array[j];               
                         break;
                       }    
                  }
    
                  //开始找大的填到j里          
                  while(i < j) //开启从左边到右边的扫描
                  {
                      if(array[i] < temp)
                      {
                          i++;  //移动到下个元素
                      }else
                      {
                        //说明找到了比基准元素大的，那么我们就把当前这个大的数移动到上次留下的坑
                          array[j] = array[i];
                          break;  //并且要结束循环
                      }
                  }
              }
          }
    
          //执行到这来说明i == j了，说明我们扫描已经到了一个元素了那么这个元素肯定是空的
          array[i] = temp;  
    
          //现在我们已经把基准点放在了正确位置，因为这个时候左边的全部小于他，右边的全部大于他
          //既然这个数搞定了，那么我们现在来排序这个数的两侧，我们用递归把，性质相同
          //左边递归
          QuickSort(array,s,j - 1);
          //右边递归
          QuickSort(array,j + 1,t);
    }

[SouthEast]: /images/20220605/ccac0d3c1fed4bb3b20f1cc0c6975ab9.png