排序算法

参考白话经典算法 原文链接：http://blog.csdn.net/MoreWindows/article/category/859207

1.冒泡排序

void bubbleSort(int array[], int length){
    //外层控制循环次数 循环次数为=(排序总个数 - 1), 例:2个数只需要1次就可以比较出来
    //i 从1开始比较 只需要比较 (length-1)次即可
    for(int i=1; i<=length-1; i++){
        //j 负责具体的比较,j+1 是这一轮比较的最大下表值，与已循环的次数有关
        for(int j=0; j+1 <= length-1-(i-1); j++){
            if(array[j] > array[j+1]){    //j+1的下标
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

 2.插入排序

void insertSort(int array[], int length){
    int i,j;
    //遍历所有的未排序数
    for(i=1; i<length; i++){
        //遍历所有从小到大的有序的数
        for(j=i-1; j>=0; j--){
            //从最大开始，遍历所有从小到大的有序数，并与要插入的数字比较
            if(array[i] > array[j])
                //如果在有序数中找到了一个比要插入的数字小的
                //则表明左边所有的数字都比这个数小，从有序最大开始
                break;
        }

        //如果要插入的数比最大的数大，则不用插入；否则移动数据
        if(j != i-1){
            //下标[0,j]比要插入数小;
            //下标(j,i)/[j+1,i-1]比要插入数大;
            int tmp = array[i];
            int k;
            for(k=i-1;k+1>j;k--){
                array[k+1] = array[k];
            }
            array[j+1] = tmp;
        }
    }
}

  3.快速排序

int adjustArray(int array[], int l, int r){
    int i = l,j = r;

    //先将最左边的数取出来，并作为比较对象
    int x = array[l];

    while(i < j){
        //从右到左比较 找一个比x小的数字
        while((i<j) && (array[j] > x))
            j--;
        if(i < j){
            //如果找到 就将这个数放到最左边的位置
            array[i] = array[j];
            i++;
        }

        //从左到右比较 找到一个比x大的数字
        while((i<j) && (array[i] < x))
            i++;
        if(i < j){
            //如果找到就将这个数放到刚才比x小的那个数的位置上面
            array[j] = array[i];
            j--;
        }
    }

    //将比较的对象放到中间的位置，这样，左边的所有的数就比这个
    //数小，右边所有的数字就比这个数大
    //最后返回这个数的位置
    array[i] = x;
    return i;
}

void quickSort(int array[], int l, int r){
    if(l < r){
        int i = adjustArray(array,l,r);
        //递归调用
        quickSort(array,l,i-1);
        quickSort(array,i+1,r);
    }
}