posts - 7, comments - 17, trackbacks - 0, articles - 0
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

快速排序的递归与非递归实现

Posted on 2010-11-22 05:53 Ardor Leo 阅读(2280) 评论(0)  编辑  收藏 所属分类: 有点心得
最近从《java中的快速排序算法》看到了一个快速排序的实现,实际上手测试了下。然后发现原算法有重复,便优化了一下。另外,自己实现了非递归的算法。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class QSort {

    
/**
     * 
@author WangYu 2008-05-29 初始
     * 
@param pData
     *            需要排序的数组
     * 
@param left
     *            左边的位置,初始值为0
     * 
@param length
     *            右边的位置,初始值为数组长度
     
*/

    
public static void quickSort(int[] pData, int left, int right) {
        
int i, j;
        
int middle, temp;
        i 
= left;
        j 
= right;
        middle 
= pData[left];
        
while (true) {
            
while ((++i) < right - 1 && pData[i] < middle)
                ;
            
while ((--j) > left && pData[j] > middle)
                ;
            
if (i >= j)
                
break;
            temp 
= pData[i];
            pData[i] 
= pData[j];
            pData[j] 
= temp;
        }
        pData[left] 
= pData[j];
        pData[j] 
= middle;

        System.out.print(
"分界值:" + middle + "  下标" + j + "");
        
for (int k = 0; k < pData.length; k++) {
            System.out.print(pData[k] 
+ " ");
        }
        System.out.println();

        
if (left < j)
            quickSort(pData, left, j);

        
if (right > i)
            quickSort(pData, i, right);
    }

    
/**
     * 
@author ardorleo 2010-11-21 快速排序优化后的递归实现
     * 
@param pData
     *            需要排序的数组
     * 
@param left
     *            左边的位置,初始值为0
     * 
@param length
     *            右边的位置,初始值为数组长度
     
*/
    
public static void qSort1(int[] pData, int left, int length) {
        
int i, j;
        
int middle, temp;
        i 
= left;
        j 
= length;
        middle 
= pData[left];

        
while (true) {// 在循环体中,middle只用做比较,但值保持不变
            while ((++i) < length - 1 && pData[i] < middle)
                ;

            
while ((--j) > left && pData[j] > middle)
                ;

            
if (i >= j)
                
break;
            temp 
= pData[i];
            pData[i] 
= pData[j];
            pData[j] 
= temp;
        }

        
// 较小的值在左,较大的值右
        pData[left] = pData[j];
        pData[j] 
= middle;

        System.out.print(
"分界值:" + middle + "  下标" + j + "");
        
for (int k = 0; k < pData.length; k++) {
            System.out.print(pData[k] 
+ " ");
        }
        System.out.println();

        
// 此种条件可以避免多余排序(每一趟最后两个相邻已比较后,就不用再递归了)
        if (j - left > 1)
            qSort1(pData, left, j);

        
if (length - i > 1)
            qSort1(pData, i, length);

    }

    
/**
     * 
@author ardorleo 2010-11-21 快速排序的非递归实现
     * 
@param pData
     *            需要排序的数组
     * 
@param left
     *            左边的位置,初始值为0
     * 
@param length
     *            右边的位置,初始值为数组长度
     
*/
    
public static void qsort2(int[] pData, int orignal_start, int orignal_length) {
        
int temp;
        
int start = orignal_start;
        
int length = orignal_length;
        
int left = orignal_start;
        
int right = orignal_length;
        
int reference = pData[left];

        Stack
<Integer> intStack = new Stack<Integer>();
        
while (true) {
            
while (true) {
                
while ((++left) < length - 1 && pData[left] < reference)
                    ;

                
while ((--right) > start && pData[right] > reference)
                    ;

                
if (left >= right)
                    
break;

                temp 
= pData[left];
                pData[left] 
= pData[right];
                pData[right] 
= temp;
            }
            pData[start] 
= pData[right];
            pData[right] 
= reference;

            System.out.print(
"分界值:" + reference + "  下标:" + right+ " 当前顺序: ");
            
for (int k = 0; k < pData.length; k++) {
                System.out.print(pData[k] 
+ " ");
            }
            System.out.println();

            
//分值左边排序
            if (right > start + 1) {
                intStack.push(length);
                length 
= right;
                left 
= start;
            }
            
            
//分值右边排序
            while (length <= left + 1 && !intStack.empty()) {
                
int tempLength = intStack.pop();
                left 
= length + 1;
                length 
= tempLength;
            }
            
if (length > left + 1) {
                start 
= left;
                right 
= length;
            }
    
            
//结束条件
            if (intStack.empty() && length <= left + 1)
                
break;
            
            
//left值有可能大于下标最大值
            reference = pData[left];
        }

    }

    
public static void main(String[] args) {
        
int[] pData = new int[10];
        
for (int i = 0; i < 10; i++) {
            pData[i] 
= (int) (Math.random() * 100);
        }

        System.out.print(
"数组原始序列:");
        
for (int i = 0; i < pData.length; i++)
            System.out.print(pData[i] 
+ " ");
        System.out.println(
"\n***********************");
        QSort.qsort2(Arrays.copyOf(pData, pData.length), 
0, pData.length);
        System.out.println(
"***********************");
        QSort.qSort1(Arrays.copyOf(pData, pData.length), 
0, pData.length);
        System.out.println(
"***********************");
        QSort.quickSort(Arrays.copyOf(pData, pData.length), 
0, pData.length);
    }

}


只有注册用户登录后才能发表评论。


网站导航: