快速排序

  基本思想:选取一个基准元素,通常为数组最后一个元素(或者第一个元素)。从前向后 遍历数组,当遇到小于基准元素的元素时,把它和左边第一个大于基准元素的元素进行交换。在利用 分治策略从已经分好的两组中分别进行以上步骤,直到排序完成.

动图演示

冒泡排序

C代码

#include<stdio.h>

void swap(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

//分治法把数组分成两份
int patition(int *a, int left,int right) {
    int j = left;    //用来遍历数组
    int i = j - 1;    //用来指向小于基准元素的位置
    int key = a[right];    //基准元素
    //从左到右遍历数组,把小于等于基准元素的放到左边,大于基准元素的放到右边
    for (; j < right; ++j) {
        if (a[j] <= key)
            swap(&a[j], &a[++i]);
    }
    //把基准元素放到中间
    swap(&a[right], &a[++i]);
    //返回数组中间位置
    return i;
}
//快速排序
void quickSort(int *a,int left,int right) {
    if (left>=right)
        return;
    int mid = patition(a,left,right);
    quickSort(a, left, mid - 1);
    quickSort(a, mid + 1, right);
}
int main() {
    int a[] = { 10,6,5,7,12,8,1,3,11,4,2,9,16,13,15,14 };
    int n = sizeof(a) / sizeof(int);
    quickSort(a, 0,n-1);
    printf("排序好的数组为:");
    for (int l = 0; l < n; l++) {
        printf("%d ", a[l]);
    }
    printf("\n");
    return 0;
}

分析:

  最差时间复杂度:每次选取的基准元素都为最大(或最小元素)导致每次只划分了一个 分区,需要进行n-1次划分才能结束递归,故复杂度为O(n^2);最优时间复杂度:每次选取的基准元素 都是中位数,每次都划分出两个分区,需要进行logn次递归,故时间复杂度为O(nlogn);平均时间复 杂度:O(nlogn)。稳定性:不稳定的。辅助空间:O(nlogn)。   当数组元素基本有序时,快速排序将没有任何优势,基本退化为冒泡排序,可在选取基 准元素时选取中间值进行优化。

Copyright © zs0813.com 2020 all right reserved,powered by Gitbook该文件修订时间: 2020-10-09 10:41:12

results matching ""

    No results matching ""