花几分钟轻松搞定快速排序算法-蒲公英云

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

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

这里写图片描述

//快速排速算法，使用迭代 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);
}