找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 656|回复: 1

[代码] 快速排序

[复制链接]

已领礼包: 13个

财富等级: 恭喜发财

发表于 2018-6-18 13:42:54 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?立即注册

×
Quicksort probably is the most used sorting algorithm than any other, thanks to the relatively simple implementation and yet has great performance on a variety of input datas. That doesn't mean there is no shortcoming though. Quicksort is recursive, not stable, and fragile: which a small implementation mistake can go unnoticed until a spectacular disaster happens. On average quicksort does N log N operations for N number of elements, but on the worst case scenario it takes N^2 operations! Sometime programmers choose shellsort over quicksort due to the possible exploitation of its worst case of N^2 operations, or the effort of making sure correct quicksort implementation just cannot justify the application - especially when the sort mainly processes only small amount of input data. Quicksort however does outperform shellsort up to 10 times more for huge number of elements.

This article will be relying on the applet below. The basic idea for this sort is to first select a pivot, and then partitioning the array so anything smaller than the pivot comes before it and the one larger than the pivot comes after it, and lastly recursively partitioning the partitioned sub-arrays until there is no more sub-array to partition. The applet helps to visualize this process, take a look at it. The yellow bar is the pivot currently selected. At this time just observe how elements are swapped during the partitioning process. Also notice a new sub-array (bounded by blue and red vertical lines) is selected for partitioning whenever the yellow bar itself is swapped.

quicksort

Applet: Basic quicksort animation. Deliberately slowed down to emphasize the exchanges.

There are quite a few ways for selecting the pivot. For simplicity we'll take the last element as the pivot instead. At first the whole array is the sub-array itself so the last element in the array becomes the first pivot. In the applet the pivot is represented by a yellow bar, and the current sub-array is bounded by the blue and red vertical line. To partition the sub-array, starting from the blue vertical line search forward to find an element larger than the pivot and mark this index as left (blue bar). Next starting from the red line search backward to find an element smaller than the pivot and mark the index as right (red bar). Now if left and right has not yet crossed, swap the two element. Keep looking forward and backward starting from the last left and right. When left and right crosses each other swap the pivot with the element currently pointed by left. This completes the partitioning process of a single sub-array. Now the array is already partitioned into two sub-arrays where one of it contains elements less than the pivot and the other one contains elements larger than the pivot. Continue by recursively partitioning on these sub-arrays until there is no more sub-arrays to partition.

Java implementation
Note that this is the very basic of quicksort implementation without any kind of improvement, as such the last element in a sub-array will always be selected as the pivot. The applet above used this method. There are two types of implementation here, the first a "normal" quicksort, and the second similar except without recursion.

1. Basic quicksort.
[C++] 纯文本查看 复制代码
/**
* Quicksort data. Sort starts from here.
* 
* @param data Array to sort. 
*/
public void quicksort(int[] data) {
    // starts by sorting the full array.
    sort(data, 0, data.length-1) ;
}

/**
* Sort a sub-array.
* 
* @param a Array to sort.
* @param l Partition left.
* @param r Partition right.
*/
public void sort(int a[], int l, int r) {
    if (r <= l) return ;

    // start partitioning array using element at r as pivot
    int i = l-1, j = r, pivot = a[r], v ;
    while (true) {
        // scan forward (left to right)
        while (a[++i] < pivot) ;
        // scan backward (right to left)
        while (pivot < a[--j]) if (j == l) break ;
        // stop when left and right crosses
        if (i >= j) break ;
        // no crossing yet so we swap left-i and right-j
        v = a ;
        a = a[j] ;
        a[j] = v ;
    }
    // swap pivot and left-most element
    v = a ;        
    a = a[r] ;
    a[r] = v ;    

    // at this point partitioning is complete

    // recursively sort left partition
    sort(a, l, i-1) ;
    // recursively sort right partition
    sort(a, i+1, r) ;        
}


2. Basic quicksort without recursion.

[C++] 纯文本查看 复制代码
/**
 * Start quicksorting an array.
 * 
 * @param data Array to sort. 
 */    
public void quicksort(int[] data) {
    quicksort(data, 0, data.length-1);
}

/**
 * Start quicksorting a sub-array.
 * 
 * @param a Sub-array to sort.
 * @param l Left index.
 * @param r Right index. 
 */
public void quicksort(int[] a, int l, int r) {
    Stack s = new Stack() ;        
    s.push(l);
    s.push(r);
    int i, j, k, v, pivot ;
    while (!s.isEmpty()) {
        r = (Integer)s.pop(); 
        l = (Integer)s.pop() ;
        if (r <= l) continue ;

        // start partitioning
        i = l-1; 
        j = r; 
        pivot = a[r] ;
        while (true) {
            // scan forward (left to right)
            while (a[++i] < pivot) ;
            // scan backward (right to left)
            while (pivot < a[--j]) if (j == l) break ;
            // stop when left and right crosses
            if (i >= j) break ;
            v = a[i] ;
            a[i] = a[j] ;
            a[j] = v ;
        }
        v = a[i] ;        
        a[i] = a[r] ;
        a[r] = v ;
        // end partitioning

        if (i-l > r-i) {
            s.push(l) ;
            s.push(i-1) ;                
        }
        s.push(i+1) ;
        s.push(r) ;
        if (r-i >= i-l) {
            s.push(l);
            s.push(i-1) ;
        }
    }
}

论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
发表于 2019-12-18 09:28:48 | 显示全部楼层
经典
论坛插件加载方法
发帖求助前要善用【论坛搜索】功能,那里可能会有你要找的答案;
如果你在论坛求助问题,并且已经从坛友或者管理的回复中解决了问题,请把帖子标题加上【已解决】;
如何回报帮助你解决问题的坛友,一个好办法就是给对方加【D豆】,加分不会扣除自己的积分,做一个热心并受欢迎的人!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|申请友链|Archiver|手机版|小黑屋|辽公网安备|晓东CAD家园 ( 辽ICP备15016793号 )

GMT+8, 2024-3-29 23:22 , Processed in 0.296091 second(s), 30 queries , Gzip On.

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表