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); 64 } 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]; 89 } 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 }