现在的位置: 首页 > 综合 > 正文

C++学习 – 快速排序,更加优化的实现

2018年04月06日 ⁄ 综合 ⁄ 共 3912字 ⁄ 字号 评论关闭
头文件:
   1:  #pragma once
   2:  #include <vector>
   3:   
   4:  namespace FengChen
   5:  {
   6:   
   7:  template<typename T> 
   8:  class QuickSortDemo
   9:  {
  10:  public:
  11:      QuickSortDemo(void){}
  12:      ~QuickSortDemo(void){}
  13:   
  14:      void DoSort(std::vector<T>& );
  15:   
  16:      T Select(const std::vector<T>& Input, unsigned i); // 线性时间复杂度的选择第i小值的算法,递归版本
  17:  private:
  18:      // 选择轴值
  19:      unsigned SelectPivot(std::vector<T>&, unsigned, unsigned);
  20:   
  21:      // 主过程
  22:      unsigned Partition(std::vector<T>&, unsigned, unsigned );
  23:   
  24:      // 排序驱动
  25:      void QuickSortHelper(std::vector<T>&, unsigned, unsigned);
  26:   
  27:      // 差不多排好之后使用插入排序,此时插入排序的效率为O(n)
  28:      void InsertionSort(std::vector<T>& A);
  29:   
  30:      T SelectHelper(std::vector<T>&, unsigned, unsigned, unsigned);
  31:  };
  32:  }
  33:  #include "QuickSortDemo.cc"

 

实现部分代码:

   1:  #ifndef __QUICKSORTDEMO_CC__
   2:  #define __QUICKSORTDEMO_CC__ 1
   3:  #include "QuickSortDemo.h"
   4:  namespace FengChen
   5:  {
   6:      template<typename T>
   7:      void QuickSortDemo<T>::DoSort(std::vector<T>& Input)
   8:      {
   9:          if(Input.size() > 3) QuickSortHelper(Input, 0, Input.size() - 1);
  10:          InsertionSort(Input);
  11:      }
  12:      template<typename T>
  13:      T QuickSortDemo<T>::SelectHelper(std::vector<T>& Input, unsigned left, unsigned right, unsigned i)
  14:      {
  15:          using namespace std;
  16:          unsigned div;
  17:          unsigned offset;
  18:   
  19:          while(left < right)
  20:          {
  21:              div = Partition(Input, left, right);
  22:              offset = div - left + 1;
  23:              
  24:              if( offset == i ) return Input[div];
  25:              
  26:              else if(offset < i)
  27:              {
  28:                  left = div + 1;
  29:                  i = i - offset;
  30:              }
  31:              else 
  32:                  right = div - 1;
  33:          }
  34:   
  35:          if(left == right) return Input[left];
  36:      }
  37:   
  38:      template<typename T>
  39:      void QuickSortDemo<T>::InsertionSort(std::vector<T>& A)
  40:      {
  41:          for(unsigned i = 1; i < A.size(); i++)
  42:          {
  43:              unsigned pos = 0;
  44:              while( A[pos] < A[i] ) pos++; // find the position for A[i]
  45:              unsigned j = i;
  46:   
  47:              while( j > pos )
  48:              {
  49:                  std::swap(A[j], A[j-1]);
  50:                  j--;
  51:              }
  52:          }
  53:      }
  54:   
  55:      template<typename T>
  56:      void QuickSortDemo<T>::QuickSortHelper(std::vector<T>& A, unsigned left, unsigned right)
  57:      {
  58:          if(right - left  + 1 <= 2) return;
  59:   
  60:          unsigned div = Partition(A, left, right);
  61:          QuickSortHelper(A, left, div - 1);
  62:          QuickSortHelper(A, div + 1, right);
  63:      }
  64:   
  65:      template<typename T>
  66:      unsigned QuickSortDemo<T>::Partition(std::vector<T>& A, unsigned left, unsigned right )
  67:      {
  68:          int pivot = SelectPivot(A, left, right);
  69:          std::swap(A[right], A[pivot]);
  70:          const T& R = A[right];
  71:   
  72:          int i = left - 1;
  73:          unsigned j = left;
  74:          while(j < right)
  75:          {
  76:              if(A[j] < R) std::swap(A[++i], A[j++]);
  77:              else j++;
  78:          }
  79:   
  80:          std::swap(A[++i], A[right]);
  81:          return i;
  82:      }
  83:   
  84:      template<typename T>
  85:      unsigned QuickSortDemo<T>::SelectPivot(std::vector<T>& A, unsigned left, unsigned right)
  86:      {
  87:          int mid = (left + right) / 2;
  88:   
  89:          if(A[left] > A[mid]) std::swap(A[left], A[mid]);
  90:          if(A[mid] > A[right]) std::swap(A[mid], A[right]);
  91:          if(A[left] > A[mid]) std::swap(A[left], A[mid]);
  92:   
  93:          return mid;
  94:      }
  95:   
  96:      template<typename T>
  97:      T QuickSortDemo<T>::Select(const std::vector<T>& Input, unsigned i)
  98:      {
  99:          //assert(i > 0 && i <= Input.size());
 100:   
 101:          std::vector<T> Temp(Input);
 102:   
 103:          int res = SelectHelper(Temp, 0, Temp.size() - 1, i);
 104:          return res;
 105:      }
 106:  }
 107:  #endif

抱歉!评论已关闭.