快速排序

概述

快速排序基于分治法

稳定性

快速排序在分割的过程中会交换不相邻元素，因此属于不稳定的排序算法。

时间复杂度

如果快速排序分割时能恰好选择到中间值，则整个过程与归并排序一样大致分为logN层。快速排序平均时间复杂度为O(NlogN)，最坏的情况复杂度高达O(n^2)

C代码

#include <stdio.h>
int array[101], n;

void quickSort(int left, int right) {
    
    int temp, i, j, t;
    
    if (left > right) {
        return;
    }
    
    temp = array[left];
    i = left;
    j = right;
    
    while (i != j) {
        // 从右向左找
        while (array[j] >= temp && i < j) {
            j --;
        }
        // 从左向右找
        while (array[i] <= temp && i < j) {
            i ++;
        }
        // 交换两个数在数组中的位置
        if (i < j) {// 如果两个哨兵没有相遇
            t = array[i];
            array[i] = array[j];
            array[j] = t;
        }
        
    }
    
    // 将基准数归位
    array[left] = array[i];
    array[i] = temp;
    
    quickSort(left, i - 1);
    quickSort(i + 1, right);
    
    return;
    
}

int main(int argc, const char * argv[]) {
    // insert code here...
    
    int i;
    // 读入数据
    
    printf("请输入总数 n = ");
    scanf("%d", &n);
    for (i = 0; i < n; i ++) {
        scanf("%d", &array[i]);
    }
    
    quickSort(0, n - 1);
    
    printf("排序后的数据：");
    
    for (i = 0; i < n; i ++) {
        printf("%d", array[i]);
        printf(", ");
    }
    
    printf("排序完毕");
    
    getchar(); getchar();
    
    printf("Hello, World!\n");
    return 0;
}

未完待续