清泉逐流

做着努力,等待幸福到来

Sort Code

作者:Eamonn 时间 : 2014-09-09 20:12 分类:C/C++

void quick_sort(int *arr, int left, int right)
{
    assert(NULL != arr);
    if( left < right ){
        int i = left, j = right;
        int x = arr[i];
           
        while( i < j ){
               
            while(  i < j && arr[j] > x ){
                j --;
            }
            if( i < j ){
                arr[i] = arr[j];
                i ++;
            }
            while(  i < j && arr[i] < x ){
                i ++ ;
            }
            if( i < j ){
                arr[j] = arr[i];
                j --;
            }
        }
        arr[i] = x;
        quick_sort( arr, left, i-1 );
        quick_sort( arr, i+1, right );
    }
}
void insert_sort(int *arr, int n)
{
    assert( NULL != arr );
    for( int i =1; i < n; i++){
        if( arr[i] < arr[i-1] ){
            int j = i-1;
            int x = arr[i];
            while( j >= 0 && arr[j] > x){
                arr[j+1] = arr[j];
                j --;
            }
            arr[j+1] = x;
        }
    }
}
void bubble_sort(int *arr, int n)
{
    assert( NULL != arr);
       
    for(int i=0; i<n; i++){
        for( int j=1; j<n-i; j++){
            if ( arr[j] < arr[j-1] ){
                int tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
            }
        }
    }
}
#define RADIX_BASE  10
#define RADIX_LEN   3
void radix_sort(int *arr, int n)
{
    assert( NULL != arr );
    int *radix_arr = new int[sizeof(int)*n*RADIX_BASE];
    int *radix_arr_count = new int[RADIX_BASE];
    int base = 1;
    for(int i=0; i<RADIX_LEN; i++ ){
           
        for(int j=0; j<RADIX_BASE; j++){
            radix_arr_count[j] = 0;
        }
        for(int j=0; j<n; j++){
            int index = ( arr[j] / base ) % RADIX_BASE;
            int offset = n*index;
            radix_arr[ offset + radix_arr_count[index] ] = arr[j];
            radix_arr_count[index] ++;
        }
           
        int *p = arr;
        for(int j=0; j<RADIX_BASE; j++){
            int offset = n*j;
            for(int k=0; k<radix_arr_count[j]; k++){
                *p++ = radix_arr[offset + k];
            }
        }
        base *= RADIX_BASE;
    }
    delete[] radix_arr;
}
void shell_sort(int *arr, int n, int dk=-1)
{
    assert( NULL != arr );
    if( dk == -1 ){
        dk = n / 2;
    }
       
    for(int i=dk; i<n; i++){
        if( arr[dk] < arr[i-dk] ){
            int j = i-dk;
            int x = arr[i];
            arr[i] = arr[i-dk];
            while( j >=0 && x < arr[j] ) {
                arr[j+dk] = arr[j];
                j -= dk;
            }
            arr[j+dk] = x;
        }
    }
    dk /= 2;
    if(dk >=1){
        shell_sort(arr, n, dk);
    }
}
void select_sort(int *arr, int n)
{
    for(int i=0; i<n; i++){
        int min_index = i;
        for(int j=i+1; j<n; j++){
            if( arr[min_index] > arr[j] ){
                min_index = j;
            }
        }
        if( min_index != i ){
            int tmp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = tmp;
        }
    }
}
void heap_sort_adjust(int *arr, int s, int n)
{
    int child = s*2 +1;
    int x = arr[s];
    while( child < n ){
        if( child+1 < n && arr[child+1] > arr[child] ){
            child ++;
        }
        if ( arr[child] > x ){
            arr[s] = arr[child];
            s = child;
            child = 2*s + 1;
        }else{
            break;
        }
        arr[s] = x;
    }
}
void heap_sort(int *arr, int n)
{
    for( int i=n/2; i>=0; i--){
        heap_sort_adjust(arr, i, n);
    }
    cout << endl;
    for( int i= n - 1; i>=0; i--){
        int tmp = arr[i]; arr[i] = arr[0]; arr[0] = tmp;
        heap_sort_adjust(arr, 0, i);
    }
    cout << endl;
}


转载注明: http://www.eamonning.com/note/view/36
» 笔记大类