美文网首页
快速排序算法小结

快速排序算法小结

作者: 吴振宇 | 来源:发表于2017-06-25 15:02 被阅读0次

    ▼ 简介

    快速排序(Quicksort)是对冒泡排序的一种改进。
    快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

    ▼ 原理

    一趟快速排序的算法是:
    1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;
    2)以第一个数组元素作为基准点。
    3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于Ai的值A[j],将值与A[j]交换;
    4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于A[j](此时基准点)的A[i],将A[j]与A[i]交换;
    5)重复第3步
    6)重复第3、4、5步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束),到此找到基准点的下标,作为分治下标。
    7重复1-6步骤递归排序前半部分
    8 重复1-6步骤递归排序后半部分

    ▼ 代码

    <pre>
    public static void sort(int a[], int low, int hight) {
    int i, j, index;
    if (low > hight) {
    return;
    }
    i = low;
    j = hight;
    index = a[i]; // 用子表的第一个记录做基准
    while (i < j) { // 从表的两端交替向中间扫描
    while (i < j && a[j] >= index)
    j--;
    if (i < j)
    a[i++] = a[j];// 用比基准小的记录替换低位记录
    while (i < j && a[i] < index)
    i++;
    if (i < j) // 用比基准大的记录替换高位记录
    a[j--] = a[i];
    }
    a[i] = index;// 将基准数值替换回 a[i]
    sort(a, low, i - 1); // 对低子表进行递归排序
    sort(a, i + 1, hight); // 对高子表进行递归排序
    }
    </pre>

    ▼ 属性

    稳定度:不稳定
    最差时间分析:O(n2)
    平均时间复杂度: O(n*log2n)
    空间复杂度:O(log2n)-O(n)

    相关文章

      网友评论

          本文标题:快速排序算法小结

          本文链接:https://www.haomeiwen.com/subject/ikxrcxtx.html