归并排序

归并排序(Merge-Sort)是建立在归并操作上的一种有效的排序算法，是采用分治法的一个典型的应用。

1. 将待排序序列分成若干个有序的子序列
2. 将有序的子序列进行归并操作，最终生成有序的序列。

递归写法

//首先是将两个有序子序列合并为有序序列的过程
void sort(int *array, int low, int high, int mid) {
    //临时变量tmp来保存新的有序序列
    int tmp[high-low+1];
    int i,j,k;
    i = low;
    j = mid+1;
    k = 0;

    while(i <= mid && j <= high) {
        if(array[i] < array[j]) {
            tmp[k++] = array[i];
            i++;
        }else {
            tmp[k++] = array[j];
            j++;
        }
    }
    //如果循环退出后剩余了某一个序列，则拼接到tmp的后面
    while(i <= mid) {
        tmp[k++] = array[i++];
    }
    while(j <= high) {
        tmp[k++] = array[j++];
    }
    //将新的序列赋值到原始数列对应的位置上。
    for(i = low; i <= high; i++) {
        array[i] = tmp[i-low];
    }
}
//将数列从low到high的位置进行分割以及合并
void merge(int *array, int low, int high) {
    if(low < high) {
        int mid = (low+high)/2;
        merge(array, low, mid);
        merge(array, mid+1, high);
        sort(array, low, high, mid);
    }
}
//函数入口
void mergeSort(int *array, int length) {
    merge(array, 0, length-1);
    printArray(array, length);
}

非递归写法

对于递归写法来说，我们首先将待排序序列分成子序列，再进行归并，是一个从大到小，再到大的过程。那么对于非递归来说，我们可以直接从小开始进行处理

void mergeSort_1(int *array, int length) {
    int k = 2;
    int i;
    //将待排序序列以k个元素一组分为若干组，对其中的元素进行归并操作，例如2/4/8
    while(k < length) {
        for(i = 0; i < length; i+=k) {
            //依次对[0,k-1][k,2k-1][2k,3k-1]...进行排序
            int end = i+k-1;
            int mid;
            //end大于length说明剩余的元素个数小于k值，我们需要手动计算出end和mid的值
            if(end >= length) {
                end = length-1;
                mid = i+(k/2)-1;
            }else {
                mid = (i + end) / 2;
            }
            sort(array, i, end, mid);
        }
        k *= 2;
    }
    //此时的k是大于length的，[0,k/2-1]和[k/2,length-1]都已经是有序的序列了，最后进行一次归并
    sort(array, 0, length-1, k/2-1);
    printArray(array, length);
}

快速排序

快速排序的核心思想是通过一遍排序将子序列分为两个子序列，左边序列都小于某一个值（哨兵），右边的序列都大于哨兵，即此时哨兵处于正确的位置上。接下来在采用分治的方法来对两个子序列进行排序。

void quick(int *array, int low, int high, int sential) {
    if(low >= high) return;
    int i = low;
    int j = high;
    while(i < j) {
        while(i < j && array[j] > sential) {
            j--;
        }
        swap(array, i, j);
        while(i < j && array[i] < sential) {
            i++;
        }
        swap(array, i, j);
    }
    quick(array, low, i-1, array[low]);
    quick(array, i+1, high, array[i+1]);
}

void quickSort(int *array, int length) {
    quick(array, 0, length-1, array[0]);
    printArray(array, length);
}