西部数码主机 | 阿里云主机| 虚拟主机 | 服务器 | 返回乐道官网
当前位置: 主页 > php教程 > 其他 >

快速排序及其优化

时间:2015-12-31 09:38来源:未知 作者:好模板 点击:
简单实现 快速排序是比较经典、常用的算法,下面简要介绍其思路。对于一个数组,选取某个元素作为切分元素(比如第一个元素),然后把比这个元素小的都放到它前面,比这个元素

简单实现

 

快速排序是比较经典、常用的算法,下面简要介绍其思路。对于一个数组,选取某个元素作为切分元素(比如第一个元素),然后把比这个元素小的都放到它前面,比这个元素大的都放到它后面,这样切分元素的最终位置就确定了,并且数组被划分为两个子数组。然后再用同样的方法分别对子数组进行排序,最终整个数组将变成有序的。
这里的关键是实现数组划分的方法,这里举例说明。假如要对数组a={5,3,6,5,8,4,7}排序,选取a[0] 作为切分元素,排序过程如下:

5,3,6,5,8,4,7
i            j

5,3,6,5,8,4,7
    i     j   
    
5,3,4,5,8,6,7
      ij

如上所示,刚开始i指向数组第一个元素,而j指向数组末尾元素后一个位置,i从前往后扫描,直到找到一个大于等于切分元素时停下(这里是6),j从后往前扫描,直到找到一个小于等于切分元素的时候停下(这里是4),然后交换这两个元素。然后继续寻找直到两个指针相遇,则本轮扫描结束。此时j<=ij右边的元素均大于切分元素,交换a[j]与切分元素即可。接着对两个子数组{5,3,4}以及{8,6,7}继续用刚才的方法排序,最终数组将全部有序。代码实现如下:

void sort(int[] a, int lo, int hi) {
    if (hi <= lo)
        return;
    int j = partition(a, lo, hi);
    sort(a, lo, j - 1);
    sort(a, j + 1, hi);
}

int partition(int[] a, int lo, int hi) {
    int i = lo, j = hi + 1;
    int v = a[lo];
    while (true) {
        while (a[++i] < v)
            if (i == hi)
                break;
        while (a[--j] > v)
            if (j == lo)
                break;
        if (i >= j)
            break;
        swap(a, i, j);    //交换元素
    }
    swap(a, lo, j);
    return j;
}

对于快速排序有几点说明:

  • 快速排序是原地排序(只需要一个辅助栈)

  • 一般情况下快速排序的时间复杂度是O(NlgN),因为平均而言划分的子数组是对半分的。但如果切分不均匀,那么时间可能会变成平方级别。例如对于一个已经有序的数组,快速排序的性能反而很差。

  • 在每次扫描时,左侧扫描遇到大于等于切分元素时停下,右侧扫描则是遇到小于等于切分元素时停下。这样会将一些等值元素交换,但可以避免在数组中含有大量重复值的时候运行时间变成平方级别。

优化

 

对于快速排序有3点优化思路:

  1. 对于小数组,可以采用插入排序,避免递归调用。例如,当if(hi <= lo + M)时,就可以转到插入排序。

  2. 采用子数组的一部分元素的中位数来切分数组。这样做得到的切分更好,但代价是需要计算中位数。

  3. 如果数组中含有大量的重复元素,可以采用三向切分。将数组切分为三部分,分别对应于小于、等于和大于切分元素的数组元素。代码实现如下:

       private static void sort1(int[] a, int lo, int hi) {
       if (hi <= lo)
           return;
       int lt = lo, i = lo + 1, gt = hi;
       int v = a[lo];
       while (i <= gt) {
           if (a[i] < v) {
               swap(a, lt++, i++);
           } else if (a[i] > v) {
               swap(a, i, gt--);
           } else {
               i++;
           }
           sort(a, lo, lt - 1);
           sort(a, gt + 1, hi);
       }

    }

另一种实现:单向扫描

 

快速排序的数组切分还有另一种单向扫描的版本,具体步骤是选择数组中最后一个元素作为切分元素,同样设置两个指针,指针i指向数组中第一个元素前面一个位置,j则指向数组中第一个元素。j从前左右往右扫描,遇到小于等于切分元素时就把i加一,然后交换ij指向的元素。最后把i+1位置的元素和切分元素交换即可完成一次数组划分。代码实现如下:

int partition(int[] a, int lo, int hi) {
    int i = lo - 1, j = lo;
    int v = a[hi];
    while (j < hi) {
        if (a[j] <= v) {
            swap(a, ++i, j);
        }
        j++;
    }
    swap(a, i + 1, hi);
    return i + 1;
}
(责任编辑:好模板)
顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
栏目列表
热点内容