排序算法（一）

#include<iostream>
using namespace std;

//1-insert sort method
void insert_sort( int *arr, int n )
{
        int i, k;
        for( i=1; i<n; ++i )
        {
                for( k=i; k>0; --k )
                {
                        if( arr[k] < arr[k-1] )
                        {
                                int tmp = arr[k-1];
                                arr[k-1] = arr[k];
                                arr[k]=tmp;
                        }
                }
        }
}

//2-select sort method
void select_sort( int *arr, int n )
{
        int i,k;
        for( i=0; i<n-1; ++i )
        {
                for( k=i+1; k<n; ++k )
                {
                        if( arr[k] < arr[i] )
                        {
                                int tmp = arr[i];
                                arr[i] = arr[k];
                                arr[k] = tmp;
                        }
                }
        }
}

//3-buble sort method
void buble_sort( int *arr, int n )
{
        int i, k;
        for( k=n-1; k>0; --k )
        {
                for( i=0; i<k; ++i )
                {
                        if( arr[i] > arr[i+1] )
                        {
                                int tmp=arr[i];
                                arr[i]=arr[i+1];
                                arr[i+1]=tmp;
                        }
                }
        }
}

//4-bidirection bublle sort method
void bibuble_sort( int *arr, int n )
{
        int left=0,right=n-1;
        int i;
        while(left<right)
        {
                //move right
                for( i=left;i<right; ++i )
                {
                        if( arr[i]>arr[i+1] )
                        {
                                int tmp = arr[i];
                                arr[i]=arr[i+1];
                                arr[i+1]=tmp;
                        }
                }
                --right;
                //move left
                for( i=right; i>left; --i )
                {
                        if( arr[i]<arr[i-1] )
                        {
                                int tmp = arr[i];
                                arr[i]=arr[i-1];
                                arr[i-1]=tmp;
                        }
                }
        }

}

//5-quick sort method
int quick_part( int*arr, int left, int right )
{
        int val = arr[left], tmp;
        int i=left+1,k=right;
        while(1)
        {
                for( ; i<k; ++i )
                {
                        if( arr[i] > val )
                                break;
                }
                for( ; k>i; --k )
                {
                        if( arr[k] < val )
                                break;
                }
                if( i>=k )
                        break;
                tmp = arr[i];
                arr[i]=arr[k];
                arr[k] = tmp;
                ++i, --k;
        }
        if( i==k )
        {
                if( arr[i] > val )
                        --i;
        }
        else
        {
                --i;
        }
        arr[left]=arr[i];
        arr[i] = val;

        return i;
}
void quick_sort( int *arr, int left, int right )
{
        if( left < right )
        {
                int idx =  quick_part( arr, left, right );
                quick_sort( arr, left, idx-1 );
                quick_sort( arr, idx+1, right );
        }
}

//6-shell sort method
void shell( int *arr, int step, int n )
{
        int i, k;
        for( i=step;i<n; i+=step )
        {
                for( k=i; k>0; k-=step )
                {
                        if( arr[k] < arr[k-step] )
                        {
                                int tmp = arr[k-step];
                                arr[k-step]=arr[k];
                                arr[k] = tmp;
                        }
                }
        }
}
void shell_sort( int *arr, int n )
{
        int step = 5;
        while(step>0)
        {
                shell( arr, step, n );
                step /= 2;
        }
}