C++學習 - 快速排序，更加優化的實作

頭檔案：      

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;      

24:              if( offset == i ) return Input[div];      

26:              else if(offset < i)      

27:              {      

28:                  left = div + 1;      

29:                  i = i - offset;      

30:              }      

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