Chinaunix首页 | 论坛 | 博客
  • 博客访问: 567253
  • 博文数量: 213
  • 博客积分: 6789
  • 博客等级: 准将
  • 技术积分: 1947
  • 用 户 组: 普通用户
  • 注册时间: 2009-09-01 17:11
文章分类

全部博文(213)

文章存档

2012年(9)

2011年(62)

2010年(99)

2009年(43)

分类: C/C++

2010-12-12 21:33:20

冒泡,选择,插入,递归,快速排序(bubble, select, insert, recurse, quick)

chechunli@chechunli-virtual-machine:arithmetic $ cat test_arithmetic.c
#include
#include
#include

#define N    8

int a[N];

void show_array(void )
{
    int i = 0;
    for ( i = 0; i < N; ++i )
        printf("%d   ", a[i]);
    printf("\n");
}

void swap(int i, int j )
{
    int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

/* bubble func */
void bubble(int first, int last )
{
    int i = 0, j = 0;
    for ( i = first; i <= last; ++i )
        for ( j = last; j > i; --j )
            if ( a[i] > a[j] ) swap(i, j );
}

/* selection func */
void selection(int first, int last )
{
    int i = 0, j = 0, k = 0;
    for ( i = first; i < last; ++i ){
        k = i;
        for ( j = i + 1; j <= last; ++j )
            if ( a[j] < a[k] ) k = j;
        if ( k != i ) swap(i, k);
    }
}

/* insert func */
void insert(int first, int last )
{
    int i = 0, j = 0;
    for ( i = first + 1; i <= last; ++i )
        for ( j = first; j < i; ++j )
            if ( a[j] > a[i] ) swap(j, i);
}

/*recurse func */
int b[N];

void merge( int f, int m, int l )
{
    int i = 0, j = 0, k = 0;
    for ( i = f; i <= l; ++i ) b[i] = a[i];
    i = f; j = m + 1; k = f;
    while ( i <= m && j <= l )
        if ( b[i] < b[j] ) a[k++] = b[i++];
        else a[k++] = b[j++];
    while ( i <= m ) a[k++] = b[i++];
    while ( j <= l ) a[k++] = b[j++];
}

void recurse(int first, int last)
{
    if ( first >= last ) return;
    int m = (first + last ) / 2;
    recurse( first, m );
    recurse( m + 1, last );
    merge(first, m, last );
}

/* quick func */
int c[N];

int partition(int first, int end)
{
    int key = 0, j = 0;
    for ( key = first , j = first + 1; j <= end; ++j )
        if ( a[j] < a[first] ) swap( j , ++key );

    swap( first , key );
    return key;
}

void quick(int first, int end )
{
    if ( first >= end ) return;
    int m = partition(first, end );
    quick(first, m - 1 );
    quick(m + 1, end );

}

int main(int argc, char *argv[])
{
    int i = 0;
    srand(time(NULL));
    for ( i = 0; i < N; ++i )
        a[i] = rand()%100;

    show_array();
    //bubble(0, N - 1);
    //selection(0, N - 1);
    //insert(0, N -1 );
    //recurse(0, N - 1);
    quick(0, N - 1);
    show_array();

    return 0;
}

阅读(728) | 评论(0) | 转发(0) |
0

上一篇:linux cmd--aptitude

下一篇:search

给主人留下些什么吧!~~