交换排序：快速排序（Quick Sort）

基本思想：

1）选择一个基准元素，通常选择第一个元素或者最后一个元素。

2）通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小；另一部分记录的元素值均比基准值大。

3）此时基准元素在其排好序后的正确位置

4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。

算法的实现：

// 输出数组内容
void print(int array[], int length, int i) {
    printf("privot=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

// 交换两个数据的位置
void swap(int *num1, int *num2) {
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

// 将数组分割成独立的两部分
int partition(int array[], int low, int high) {
    int privotKey = array[low]; // 基准元素
    while (low < high) { // 从表的两端交替地向中间扫描
        while (low < high && array[high] >= privotKey) {
            -- high; // 从 high 所指位置向前搜索，至多到 low+1 位置。将比基准元素小的交换到前端
        }
        swap(&array[low], &array[high]);
        while (low < high && array[low] <= privotKey) {
            ++ low; // 从 low 所指位置向后搜索，至多到 high-1 位置。将比基准元素大的交换到后端
        }
        swap(&array[low], &array[high]);
    }
    print(array, 8, low);
    return low;
}

// 快速排序（Quick Sort）
void quickSort(int array[], int low, int high) {
    if (low < high) {
        int privotLoc = partition(array, low, high); // 将表一分为二
        quickSort(array, low, privotLoc - 1); // 递归对低子表递归排序
        quickSort(array, privotLoc + 1, high); // 递归对高子表递归排序
    }
}

int main(int argc, const char * argv[]) {
    int arrayQuickSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    quickSort(arrayQuickSort, 0, 7);
    
    printf("\n");
    return 0;
}

快速排序的改进

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

在本改进算法中，只对长度大于k的子序列递归调用快速排序，让原序列基本有序，然后再对整个基本有序序列用插入排序算法排序。实践证明，改进后的算法时间复杂度有所降低，且当k取值为 8 左右时，改进算法的性能最佳。

// 输出数组内容
void print(int array[], int length, int i) {
    printf("privot=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

// 交换两个数据的位置
void swap(int *num1, int *num2) {
    int temp = *num1;
    *num1 = *num2;
    *num2 = temp;
}

// 将数组分割成独立的两部分
int partition(int array[], int low, int high) {
    int privotKey = array[low]; // 基准元素
    while (low < high) { // 从表的两端交替地向中间扫描
        while (low < high && array[high] >= privotKey) {
            -- high; // 从 high 所指位置向前搜索，至多到 low+1 位置。将比基准元素小的交换到前端
        }
        swap(&array[low], &array[high]);
        while (low < high && array[low] <= privotKey) {
            ++ low; // 从 low 所指位置向后搜索，至多到 high-1 位置。将比基准元素大的交换到后端
        }
        swap(&array[low], &array[high]);
    }
    print(array, 8, low);
    return low;
}

// 快速排序改进（Quick Sort）
void quickSortImprove(int array[], int low, int high, int k) {
    if (high - low > k) { // 长度大于k时递归，k为指定数
        int privotLoc = partition(array, low, high);
        quickSortImprove(array, low, privotLoc - 1, k);
        quickSortImprove(array, privotLoc + 1, high, k);
    }
}

// 快速排序改进（Quick Sort）
void quickSort(int array[], int low, int high, int k) {
    quickSortImprove(array, low, high, k); // 先调用改进算法，使之基本有序

    // 再用插入排序对基本有序序列排序
    for (int i = 1; i <= high; i ++) {
        int j = i - 1;
        int sentry = array[i]; // 复制为哨兵，即存储待排序元素
        while (j >= 0 && sentry < array[j]) { // 查找在有序表的插入位置
            array[j+1] = array[j];
            j--; // 元素后移
        }
        array[j+1] = sentry; // 插入到正确位置
    }
}

int main(int argc, const char * argv[]) {
    int arrayQuickSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    quickSort(arrayQuickSort, 0, 7, 4);
    print(arrayQuickSort, 8, 0);
    printf("\n");
    
    return 0;
}

总结

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短。