Select算法（最坏复杂度O（n））

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8

9 const int nMax = 3000; 10 int A[nMax+1];

11 int B[nMax+1];//⽤来每次5分法后保存要⽐较的值在A中的下标 12 int AIndex[nMax+1]; //⽤来保存A的初始化下标 13

14 //通过插⼊排序获取中位数下标

15 int InsertSort(int A[], int B[], int start, int end) 16 {

17 if (start == end) 18 {

19 return B[start]; 20 } 21

22 for (int i = start+1; i <= end; ++i) 23 {

24 int num = A[B[i]]; 25 int j = i-1;

26 for ( ; j >= start; --j) 27 {

28 if (num < A[B[j]]) 29 {

30 A[B[j + 1]] = A[B[j]]; 31 } 32 else 33 {

34 break; 35 } 36 }

37 A[B[j + 1]] = num; 38 } 39

40 return B[(start + end)/2]; 41 } 42

43 //获取中位数的中位数的下标

44 int GetMidMid(int A[], int AIndex[], int k, int n) 45 {

46 if (k == n) 47 {

48 return AIndex[n]; 49 } 50

51 int len_s = n - k + 1; 52 //筛选出n/5份的中位数 53 int mod = len_s % 5;

54 int len = len_s / 5 + (mod != 0);

55 for (int i = 1, j = k; i<= len && j <= n-mod; ++i, j+=5) 56 {

57 B[i] = InsertSort(A, AIndex,j, j+4); 58 }

59 if (mod != 0) 60 {

61 B[len] = InsertSort(A, AIndex, n - mod + 1, n); 62 }

63 return GetMidMid(A, B, 1, len); } 65

66 //原址排序

67 int Partition(int A[], int p, int n) 68 {

69 int pivot = A[n]; 70 int j = p - 1;

71 for (int i = p; i <= n - 1; ++i) 72 {

73 if (A[i] <= pivot) 74 {

75 j++;

76 swap(A[j], A[i]); 77 } 78 } 79

80 swap(A[j + 1], A[n]);

81 return j + 1; 82 } 83

84 int Select(int A[], int k, int n, int i) 85 {

86 if (k == n) 87 {

88 return A[n]; } 90

91 int midValueIndex = GetMidMid(A, AIndex, k, n); 92

93 //将该中位数作为主元(pivot element) 94 //使⽤⼀次原址重排

95 int pivot = A[midValueIndex]; 96 swap(A[midValueIndex], A[n]); 97 int mid = Partition(A, k, n); 98

99 int t = mid - k + 1;100 if (i == t)101 {

102 return A[mid];103 }

104 else if (i < t)105 {

106 return Select(A, k, mid-1, i);107 }108 else109 {

110 return Select(A, mid+1, n, i-t);111 }112 }

113 int main(int argc, char** argv)114 {

115 int n = 1111;

116 for (int i = 1; i <= n; ++i)117 {

118 A[i] = i;

119 AIndex[i] = i;120 }121

122 //for (int i = 1; i <= n; ++i)123 //{

124 // cout << A[i] << \" \";125 //}

126 //cout << endl;127

128 int equalNum = 0;

129 for (int i = 1; i <= n; ++i)130 {

131 //随机排列A数组

132 for (int i = 1; i <= n; ++i)133 {

134 int j = i + rand() % nMax;135 //swap(A[i], A[j]);136 A[i] = j;137 }138

139 int ans1 = Select(A, 1, n, i);140 sort(A + 1, A + n + 1);141 int ans2 = A[i];142

143 if (ans1 == ans2)144 {

145 equalNum++;146 }147 }

148 cout << n << \" \" << equalNum << endl;149 return 0;150 }