C指针编程之道（五）- 排序算法

//原始冒泡排序算法
void bubble_sort(int *array, int n) {
    int t;
    for (int i=n-1; i>0; i--) {
        for (int j=0; j<i; j++) {
            if (array[j] > array[j+1]) {
                t = array[j];
                array[j] = array[j+1];
                array[j+1] = t;
            }
        }
    }
}

/*
0   8 2 4 3 1
1   2 4 3 1 8
2   2 3 1 4 8
3   2 1 3 4 8
4   1 2 3 4 8

我们发现，每一趟比较结束之后，若发现从某个位置r开始，不再进行记录交换，就说明从array[r+1]到array[n-1]
已经排好序了，从而下一趟比较只要进行到位置r就可以了。若发现某一趟扫描中没有交换记录，则说明所有的元素都已
经有序，算法就可以结束了，而不是非要进行n-1趟扫描。基于这种思想，可以给出冒泡排序的改进算法。
*/

//改进冒泡排序算法
void bubble_sort(int *array, int n) {
    int m=0,bound=n-1;
    int t=0;
    while (bound!=0) { //bound记录m的值，m是每趟冒泡最后一次发生交换的位置，只要排序还没有排完，m的值就会从0发生改变
        m = 0;
        for (int i=0; i<bound;i++) {
            if (array[i] > array[i+1]) {
                t = array[i];
                array[i] = array[i+1];
                array[i+1] = t;
                m = i;
            }
        }
        bound = m;
    }
}

/*
上述冒泡排序只考虑了重气泡下沉的过程，是“单向起泡”，即使得重气泡下沉，经过一次冒泡至少可以把关键词最大的记录送到最后的位置。
其实我们可以在重气泡下沉的同时，也使轻气泡上浮，这样经过一次扫描就可以至少把关键词最大的记录和关键词最小的记录放到最终的位
置上，这就是“双向起泡”，基于这种思想，我们给出双向起泡排序算法的实现如下。
*/

//双向起泡排序算法（最终版）
void bubble_sort(int *array, int n) {
    int mmin,boundmin=0;
    int mmax,boundmax=n-1;
    int t;
    
    while (boundmin<boundmax) {
        mmin = 0;
        mmax = 0;
        
        //重气泡下沉
        for (int i=boundmin; i<boundmax; i++) {
            if (array[i] > array[i+1]) {
                t = array[i];
                array[i] = array[i+1];
                array[i+1] = t;
                mmax = i;
            }
        }
        if (mmax==0) break; //本次没有记录交换，扫描结束
        boundmax = mmax;
        
        //轻气泡上浮
        for (int i=boundmax; i>boundmin; i--) {
            if (array[i] < array[i-1]) {
                t = array[i];
                array[i] = array[i-1];
                array[i-1] = t;
                mmin = i;
            }
        }
        if (mmin==0) break; //本次没有记录交换，扫描结束
        boundmin = mmin;
    }
}

//分划算法(以最左端值array[i]为基准，不断左右比较后，求出它在最终序列上的下标位置)
int part(int *array, int i, int j) {
    int t=array[i];
    
    while (i<j) { //两端交替向中间扫描，直到i==j为止
        //从右向左扫描，找出第一个小于t的数
        while (i<j && array[j]>=t) {
            j--;
        }
        if (i<j) { //表示找到了这个数array[j]
            array[i] = array[j]; //这里”相当于“array[i]和array[j]交换位置
            i++;
        }
        
        //从左到右扫描，找出第一个大于t的数
        while (i<j && array[i]<=t) {
            i++;
        }
        if (i<j) { //表示找到了这个数array[i]
            array[j] = array[i];//这里”相当于“array[i]和array[j]交换位置
            j--;
        }
    }
    array[i] = t; //最后定位基准位置
    
    return i;
}

//快速排序法
void quick_sort(int * array, int low, int high) {
    if (low < high) {
        int mid = part(array, low, high);
        quick_sort(array, low, mid-1);
        quick_sort(array, mid+1, high);
    }
}

void select_sort(int *array, int n) {
    int k; //记录每趟扫描的最小值
    int t;
    
    for (int i=0; i<n-1; i++) {
        k = i;
        for (int j=i+1; j<n; j++) {
            if (array[j] < array[k]) {
                k = j; //记录当前最小值的位置
            }
        }
        if (k!=i) {
            t = array[k];
            array[k] = array[i];
            array[i] = t;
        }
    }
}

void insert_sort(int *array, int n) {
    int temp;
    int j;
    
    for (int i=1; i<n; i++) {
        if (array[i] < array[i-1]) {
            temp = array[i];
            
            for (j=i-1; temp<array[j]; j--) {
                array[j+1] = array[j];
            }
            
            array[j+1] = temp;
        }
    }
}

void shell_insert(int *array, int step, int n) {
    int j;
    int temp;
    
    for (int i=step; i<n; i++) {
        if (array[i] < array[i-step]) {
            temp = array[i];
            
            for (j=i-step; j>=0 && temp<array[j]; j-=step) {
                array[j+step] = array[j];
            }
            array[j+step] = temp;
        }
    }
}

void shell_sort(int *array, int n) {
    int addition = n;//开始的增量
    while (addition > 1) {
        addition = addition/3+1; //求下一个增量
        shell_insert(array, addition, n);
    }
}