找中值的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

}

以下给出求n个数的中间数拦培的慧锋C语言代码：

#include<stdio.h>

void main()

{

int n,i,j,t

int a[1000]

scanf("%d",&n)  //输入n。

for(i=0i<ni++)

scanf("%d",&a[i])  //输前衡晌入n个数。

for(i=0i<n-1i++)

for(j=i+1j<nj++)

if (a[i]>a[j]) 

{

t=a[i]

a[i]=a[j]

a[j]=t

}    //冒泡排序数列。

if (n%2!=0) printf("%d\n",a[n/2])

else printf("%0.1f\n",((double)(a[n/2]+a[n/2-1])/2))  //求中间数。

}

没有包含头文件conio.h，

还有倒数第三行御旁扒改为printf("%d\n",zws(a,b,c))

#include<conio.h>

#include<stdio.h>

int zws(int a, int b, int c){

int ans

if (a >= b &&a <= c) ans = a

if (a <= b &&a >= c) ans = a

if (b >= a &&b <= c) ans = b

if (b <= a &&b >= c) ans = b

if (c >= a &&c <镇昌= b) ans = c

if (c <= a &&c >= b) ans = c

return ans

}

int main()

{

int a, b, c

printf("please input 3 integar:")

scanf("%d %d %d"启薯, &a, &b, &c)

printf("%d\n",zws(a, b, c))

getch()

}

---