交换类排序算法：快速排序

交换类排序算法：快速排序

五月 29, 2021

快速排序

  1. 快速排序处理函数（需要递归调用，因此以函数形式封装定义）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void QSort(SqList *L,int low,int high)
    {
        int pivot;
        if(low < high)
        {
            pivot= Partition(L,low,high);	//关键点：枢纽pivot值选取函数
            QSort(L , low , pivot-1);	//对低子表递归排序
            QSort(L , pivot+1 , high);	//对高子表递归排序
        }
    }

  2. 选取关键字作为==枢纽==（pivot）函数

    1. 关键思路：

      1. 用low位值作为枢轴比较记录
      2. 分别从左右端交替比较
      3. low < key , low ++ ; low > key , low <-> high
      4. high > key , high – ; high < key , high <-> low
      5. high = low , 返回low值为函数得出的pivot
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      int Partition(SqList *L,int low,int high)
      {
          int pivotkey;
          pivotekey = L->[low];	
          /***************/
          while(low<high)
          {
              while(L->r[high] > pivotekey)
              {
                  high--;
              }
              swap(L , high , low);
              while(low<high && L->r[low] < pivotekey)
              {
                  low++;
              }
              swap(L , low , high);
          }
          return low;
      }

  3. 快速排序优化方案

    1. 优化选取枢轴值（提高大概率选取到为中间值）

      1. 随机数选取法
      2. 三数取中法
      3. 九数取中法

    2. 优化不必要的交换

      1. 思路：（进行直接替换）采用直接赋值替代函数swap()的调用

    3. 优化小数组时排序方案

      1. 思路：（避免大材小用）设定阈值，对于小数组用直接插入法排序
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      /*
      2. 选定合适阈值
      2.判断数组大或小
          a. 大于阈值：调用快排（递归）
              -、选取枢轴
              -、低子表递归快排
              -、高子表递归快排
          b.	小于阈值：调用插排
      */
      define MAX_LENGTH_INSERT_SORT 7	//设定合适的阈值
      void OSort(SqList *L,int low,int high)
      {
          int pivot;
          if(high-low)>MAX_LENGTH_INSERT_SORT)	//大于阈值：快排
          {
              pivot=Partiton1(L , low , high);	
              QSort1(L , low , pivot-1 );
              QSort1(L , pivot+1 , high);
          }
          else	//小于阈值：插排
          {
              InsertSort(L);	
          }
      }

    4. 优化递归操作

      1. 思路：（减少递归，减少对栈空间的消耗）以迭代进行尾递归代替第二个递归排序
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      void QSort2(SqList *L,int low,int high)
      {
          int pivot;
          if()
          {
              while(low < high)
              {
                  /**********/
                  /**********/
                  low = pivot+1;	//尾递归
              }
          }
          else
          {
              InsertSort(L);
          }
      }
  1. 1. 快速排序
    1. 1.1. 快速排序优化方案