算法上机实验----各种排序算法

发表于 | 分类于
算法上机实验的代码

第一次上机的内容，实现插入排序、合并排序、快速排序、随机快排、计数排序、基数排序、桶排序
这里用C语言实现，主要是为了贴代码

基础设施建设

引一些头文件，写了个交换函数、打印数组用的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
void swap( int *a, int *b ) {
    int t = *a;
    *a    = *b;
    *b    = t;
}
void print_arr( int *a, int n ) {
    for ( int i = 0; i < n; i++ ) {
        printf( "%d ", a[ i ] );
    }
    printf( "\n" );
}

插入排序

这里传了一个比较函数，主要是为了之后的基数排序需要一个稳定的排序方式，方便之后调用。
算法就是将后面的数字往前插。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int  insert_sort_cmp( int a, int b ) { return a - b; }
void insert_sort( int *arr, int n, int ( *cmp )( int, int ) ) {
    for ( int i = 0; i < n; i++ ) {
        int tmp = arr[ i ];
        for ( int j = i; j >= 0; j-- ) {
            if ( cmp( arr[ j - 1 ], tmp ) > 0 ) {
                arr[ j ] = arr[ j - 1 ];
            } else {
                arr[ j ] = tmp;
                break;
            }
        }
    }
}

归并排序

将数组分成两部分，分别递归调用后再进行合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void merge_sort( int *a, int l, int r ) {
    if ( r - l == 1 ) {
        return;
    }
    int mid = ( l + r ) / 2;
    merge_sort( a, l, mid );
    merge_sort( a, mid, r );
    int *b  = (int *) malloc( sizeof( int ) * ( r - l ) );
    int  li = l, ri = mid, bi = 0;
    for ( int i = 0; i < ( r - l ); i++ ) {
        if ( li != mid && ri != r ) {
            if ( a[ li ] < a[ ri ] ) {
                b[ i ] = a[ li++ ];
            } else {
                b[ i ] = a[ ri++ ];
            }
        } else {
            if ( li != mid ) {
                b[ i ] = a[ li++ ];
            }
            if ( ri != r ) {
                b[ i ] = a[ ri++ ];
            }
        }
    }
    for ( int i = l; i < r; i++ ) {
        a[ i ] = b[ i - l ];
    }
    free( b );
}

快速排序

选一个 privot ，让后将比 privot 大的放在右边， 比 privot 小的放在左边。
挑选挪动的思路是从左往右扫，把比 privot 小的挪到左边，扫完了以后将 privot 换到中间即可。
这样比从两边同时扫不容易错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quick_sort( int *a, int l, int r ) {
    if ( r - l <= 1 ) return;
    int privot = a[ r - 1 ];
    int j      = l;
    for ( int i = l; i < r - 1; i++ ) {
        if ( a[ i ] < privot ) {
            swap( a + j, a + i );
            j++;
        }
    }
    swap( a + j, a + r - 1 );
    quick_sort( a, l, j );
    quick_sort( a, j + 1, r );
}

随机快排

思路跟上面是一样的，只是选 privot 的时候用随机的方法选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort_random( int *a, int l, int r ) {
    if ( r - l <= 1 ) return;
    int p      = (int) ( rand() % ( r - l ) + l );
    int privot = a[ p ];
    swap( a + p, a + r - 1 );
    int j = l;
    for ( int i = l; i < r - 1; i++ ) {
        if ( a[ i ] < privot ) {
            swap( a + j, a + i );
            j++;
        }
    }
    swap( a + j, a + r - 1 );
    quick_sort( a, l, j );
    quick_sort( a, j + 1, r );
}

计数排序

统计数据出现的次数，然后进行排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void counting_sort( int *a, int n ) {
    int *cnt = (int *) malloc( sizeof( int ) * n );
    int *tmp = (int *) malloc( sizeof( int ) * n );
    memset( cnt, 0, sizeof( int ) * n );
    for ( int i = 0; i < n; i++ ) {
        cnt[ a[ i ] ] += 1;
    }
    for ( int i = 1; i < n; i++ ) {
        cnt[ i ] += cnt[ i - 1 ];
    }
    for ( int i = 0; i < n; i++ ) {
        tmp[ --cnt[ a[ i ] ] ] = a[ i ];
    }
    for ( int i = 0; i < n; i++ ) {
        a[ i ] = tmp[ i ];
    }
}

基数排序

每一位都进行排序，从低位开始。每一位的排序方式使用稳定的排序方式，这里用了插入。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int base = 1;
int radix_sort_cmp( int a, int b ) { return ( a / base % 10 - b / base % 10 ); }
void radix_sort( int *a, int n ) {
    int max = 0;
    for ( int i = 0; i < n; i++ ) {
        if ( a[ i ] > max ) max = a[ i ];
    }
    int k = (int) log10( max ) + 1;
    for ( int i = 0; i < k; i++ ) {
        insert_sort( a, n, radix_sort_cmp );
        base *= 10;
    }
    base = 1;
}

桶排序

将数据范围分成几段，即桶，然后将数据放入桶中，然后用以上的各种方法对桶内数据排序，最后将桶的数据连接起来即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void bucket_sort( int *a, int n ) {
    int *bucket[ 10 ];
    for ( int i = 0; i < 10; i++ ) {
        bucket[ i ] = (int *) malloc( sizeof( int ) * n );
    }
    int index_table[ 10 ] = {0};
    int max = 0, min = 10000;
    for ( int i = 0; i < n; i++ ) {
        if ( a[ i ] > max ) max = a[ i ];
        if ( a[ i ] < min ) min = a[ i ];
    }
    int gap = ( max - min ) / 10 + 1;
    for ( int i = 0; i < n; i++ ) {
        int buck_num = ( a[ i ] - min ) / gap;
        bucket[ buck_num ][ index_table[ buck_num ]++ ] = a[ i ];
    }
    for ( int i = 0; i < 10; i++ ) {
        insert_sort( bucket[ i ], index_table[ i ], insert_sort_cmp );
    }
    int index = 0;
    for ( int i = 0; i < 10; i++ ) {
        for ( int j = 0; j < index_table[ i ]; j++ ) {
            a[ index++ ] = bucket[ i ][ j ];
        }
    }
    for ( int i = 0; i < 10; i++ ) {
        free( bucket[ i ] );
    }
}

主函数

生成数据用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main() {
    int arr_num    = 20;
    int arr[ 100 ] = {0};
    srand( time( 0 ) );
    for ( int i = 0; i < arr_num; i++ ) {
        arr[ i ] = (int) ( rand() % 1000 );
    }
    print_arr( arr, arr_num );
    // insert_sort( arr, arr_num, insert_sort_cmp );
    // merge_sort( arr, 0, arr_num );
    // quick_sort( arr, 0, arr_num );
    // quick_sort_random( arr, 0, arr_num );
    // counting_sort( arr, arr_num );
    // radix_sort( arr, arr_num );
    bucket_sort( arr, arr_num );
    print_arr( arr, arr_num );
    return 0;
}