找中值的c语言源代码

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

 
void swap(int A[], int i, int j)
{
if (i != j)
{
int t = A[i];
A[i] = A[j];
A[j] =t;
}
}

int partition(int A[], int p, int r)
{
    int x = A[r];
    int i = p - 1;
    for (int j = p; j <= r-1; j++)
{
if (A[j] <= x)
{
i++;
swap(A, i, j);
}
}
swap(A, i+1, r);
return i+1;
}

int randomized_partition(int A[], int p, int r)
{
srand(time(NULL));
int i = p + rand() % (r-p+1);
swap(A, i, r);
return partition(A, p, r);
}

int randomized_select(int A[], int p, int r, int i)
{
if (p == r) return A[p];
    int q = randomized_partition(A, p, r);
    int k = q - p + 1;

    if (i == k)     return A[q];
    else if (i < k) return randomized_select(A, p, q-1, i);
    else            return randomized_select(A, q+1, r, i-k);
}

void triplet_adjust(int A[], int i, int step)
{
int j = i + step;
    int k = i + 2 * step;
    if (A[i] < A[j])
{
if (A[k] < A[i])      swap(A, i, j);
else if (A[k] < A[j]) swap(A, j, k);
    }
    else
{
if (A[i] < A[k])      swap(A, i, j);
else if (A[k] > A[j]) swap(A, j, k);
}
}

double mean(int A[], int n)
{
double f = A[0];
for (int i = 1; i < n; i++) f += A[i];
return f / n;
}

int approximate_median(int A[], int r)
{
int step = 1;
int size = 1;
int i;
    for (int j = 0; j < r; j++) size *= 3;
    for (int k = 0; k < r; k++)
{
i = (step - 1) / 2;
while (i < size)
{
triplet_adjust(A, i, step);
i += (3 * step);
}
step *= 3;
}
return A[(size - 1) / 2];
}

void selection_sort(int A[], int left, int size, int step)
{
int min;
int i, j;
for (i = left; i < left + (size-1) * step; i += step)
{
min = i;
for (j = i+step; j < left + size; j += step)
{
if (A[j] < A[min]) min = j;
}
swap(A, i, j);
}
}

template<class T, class S>
void ncmerge_sort(T * _A, S _N)
{
S step, ins, l, m, r, pos0, pos1;
T * _T = new T[_N];

for(step = 2; step < _N * 2; step *= 2)
{
for(l = 0; l + step / 2 < _N; l += step)
{
m = l + step / 2;
r = m + step / 2 < _N ? m + step / 2 : _N;
pos0 = l; pos1 = m; ins  = 0;
while(pos0 < m && pos1 < r)
            {
if(_A[pos1] < _A[pos0]) _T[ins++] = _A[pos1++];
else                    _T[ins++] = _A[pos0++];
}
while(pos0 < m) _T[ins++] = _A[pos0++];
while(pos1 < r) _T[ins++] = _A[pos1++];
while(ins  > 0) _A[--r]   = _T[--ins];
}
}
delete [] _T;
}




const int SORT_NUM_THRESHOD = 50;

int approximate_median_any_n(int A[], int size)
{
bool left_to_right = false;
int left = 0;
int step = 1;
int i;
while (size > SORT_NUM_THRESHOD)
{
left_to_right = !left_to_right;
int rem = size % 3;
if (left_to_right) i = left;
else               i = left + (3 + rem) * step;
for (int j = 0; j < (size / 3 - 1); j++)
{
triplet_adjust(A, i, step);
i += 3 * step;
}
        if (left_to_right) left += step;
        else
{
i = left;
left += (1 + rem) * step;
        }
selection_sort(A, i, 3 + rem, step);
if (rem == 2)
{
if (left_to_right) swap(A, i+step, i+2*step);
else               swap(A, i+2*step, i+3*step);
}
step *= 3;
size = size / 3;
}
selection_sort(A, left, size, step);
return A[left + step * int( (size-1) / 2 )];
}

int main(int argc, char* argv[]) 
{
const int DEFAULT_N = 50000000;
    int N;
if (argc < 2)
{
N = DEFAULT_N;
}
else
{
N = atoi(argv[1]);
}
cout << "N = " << N << endl;
clock_t t = clock();
cout << clock() << endl;
int* A = new int[N];
cout << clock() << endl;
srand(time(NULL));
for (int i=0; i<N; i++)
{
A[i] = rand() % N;
}

clock_t t1 = clock();
cout << t1 << endl;
double avg = mean(A, N);
cout << avg << endl;
clock_t t2 = clock();
cout << t2 << endl;
int m = approximate_median_any_n(A, N); // 近似中值选择算法，不太精确，但速度快点
cout << m << endl;
clock_t t3 = clock();
cout << t3 << endl;
m = randomized_select(A, 0, N-1, N/2); // 随机选择法
cout << m << endl;
clock_t t4 = clock();
cout << t4 << endl;
//std::sort(A, A+N); // 标准快速排序
ncmerge_sort(A, N); // 原地并归排序， 排序法
m = A[N/2];
cout << m << endl;
clock_t t5 = clock();
cout << t5 << endl;
cout << endl;
double dt = (double) (t2-t1) / CLOCKS_PER_SEC;
cout << dt << "  " ;
dt = (double) (t3-t2) / CLOCKS_PER_SEC;
cout << dt << "  " ;
dt = (double) (t4-t3) / CLOCKS_PER_SEC;
cout << dt << "  " ;
dt = (double) (t5-t4) / CLOCKS_PER_SEC;
cout << dt << "  " ;
    cout << endl;

 return 0;
}

温馨提示：答案为网友推荐，仅供参考

当前网址：https://verywind.cn/ee/j3yyveej3fjvvj3eye.html