语源科技BlogJava-ardorleo的技术博客

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

Ardor Leo — Mon, 22 Nov 2010 14:53:00 GMT

最近从《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);
    }

}

Ardor Leo 2010-11-22 22:53 发表评论

自己翻译的Java.In.A.Nutshell.5th中泛型一章，欢迎拍砖把文章砸的漂亮一些

Ardor Leo — Thu, 21 Sep 2006 14:05:00 GMT

摘要: 4.1. Generic Types
Generic types and methods are the defining new feature of Java 5.0. A generic type is defined using one or more type variables and has one or more methods that use a type variable as a placeholder for an argument or return type. For example, the type java.util.List is a generic type: a list that holds elements of some type represented by the placeholder E. This type has a method named add(), declared to take an argument of type E, and a method named get(), 阅读全文

Ardor Leo 2006-09-21 22:05 发表评论

MyEclipse 5.0 正式版来了，keygen也来了

Ardor Leo — Wed, 09 Aug 2006 00:37:00 GMT

Eclipse 3.2强悍的插件组合套装MyEclipse 5.0 正式版已经发布了。从网上搜了一下，真得就找到了可以用的Keygen。放在自己的Blog中，以备使用吧。其实4.1版的keygen还是可以使用的。keygen

Ardor Leo 2006-08-09 08:37 发表评论

形如“2006-07-13 00:00:00”的javascript日期校验

Ardor Leo — Thu, 13 Jul 2006 15:52:00 GMT

这是最近自己写的一个校验如“2006-07-13　00:00:00”形式日期的javascript代码。考虑到了数字验证、闰年、2月，30天31天，小时，分，秒的检验。思路稍偏，记一下

//Long time format validate,for example "2006-07-13 00:00:00"
functionlongDateParse(dateStr){
    var THIRTY_DAY={
       3:30,
       5:30,
       8:30,
       10:30
    }
    var dateArray=dateStr.split(" ");
    if(dateArray.length<=0){returnfalse}

    varstandDateArray=dateArray[0].split("-")
    if(standDateArray.length<=0){returnfalse}
    var y=standDateArray[0]
    var m=standDateArray[1]-1
    var d=standDateArray[2]
    var testDate=newDate(y,m,d)
    //alert(testDate)
    var yTest=testDate.getFullYear()!=y
    var mTest=testDate.getMonth()!=m
    var dTest=testDate.getDate()!=d
    if(yTest||mTest||dTest){
        returnfalse
    }

    var runNianTest=y%4
    if(runNianTest==0&&m==2&&d>29){
        returnfalse;
    }
    if(runNianTest!=0&&m==2&&d>28){
        returnfalse;
    }

    if(THIRTY_DAY[m]&&d>THIRTY_DAY[m]){
        returnfalse;
    }
    //alert(testDate)

    var timeArray=dateArray[dateArray.length-1].split(":");
    if(timeArray.length!=3){return false}
    var hTest=((timeArray[0]>=0)&&(timeArray[0]<=23)&&(timeArray[0]!='-0'))?true:false;
    var mTest=((timeArray[1]>=0)&&(timeArray[1]<=59)&&(timeArray[1]!='-0'))?true:false;
    var sTest=((timeArray[2]>=0)&&(timeArray[2]<=59)&&(timeArray[2]!='-0'))?true:false;
    if(hTest&&mTest&&sTest){
        returnnewDate(y,m,d,timeArray[0],timeArray[0],timeArray[0]);
    }else{
        returnfalse;
    }
}

Ardor Leo 2006-07-13 23:52 发表评论

一段对话，关于Ajax和编码

Ardor Leo — Tue, 20 Jun 2006 14:38:00 GMT

这是我和朋友在MSN上的对话，朋友是非常棒的一个家伙，很厉害。就是他把prototype.js引进到项目中的，介绍给我的，现在都离不开了。
这段对话是在朋友的启发下总结的。有所得，有失误。欢迎不同意见的、高人来拍几下，呵呵。