快速排序

1，快速排序

首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。

怎么实现呢？---

它的关键在于完成一趟快排后，基准元素在哪个位置，每次都选取一个分割列的第一个元素作为基准元素，来寻找用它来分割排序列后它自己所处的位置，编写一个

int  findPartition(data,min,max)方法，用于使用data[min]作为基准元素把data[min]到data[max]分割为两个部分，并返回分割以后基准元素自己所在的位置索引。

在主函数里这样来调用：

public static void quickSort(Comparable[] data,int min,int max) {

        int mid;

        if(min < max)

        {

            mid = findPartition(data,min,max);

            quickSort(data,min,mid-1);

            quickSort(data,mid+1,max);

        }

    }

理解递归过程：：：if(min < max)，实际上就是要将值列分割为单一的元素（递归的最深一层），在得到基准元素的位置min后，基准元素在数组中的位置就最终确定，剩下只对左右两侧的分割列

排序：quickSort(data,min,mid-1); quickSort(data,mid+1,max);

下面来看最重要的实现部分，如何实现findPartition函数：

将第一个元素作为基准元素不要动，设两个指针left和right，left从左往右移动寻找比基准元素大的数，right从右往左移动寻找比基准元素小的数，当它们都找到对应的left和right的位置时，交换

这两个元素。重复这个过程，直到right < left.这时，除基准元素外，从min+1到right的元素都比基准元素小，left到max的元素都比基准元素大。形成了这样一个序列：

基准元素（data[min]）  ....比基准元素小的......   data[right]    |    data[left]  ......比基准元素大的  

交换基准元素和data[right]即可得到  以基准元素为分割线的 左右两个分割列。

这里我把  排序递归的调用  与   分割值列和寻找分割位置（核心部分） 分开写成两个方法，为了显得逻辑更加清楚。

完整代码   ：

//快排:快排是一个递归的过程！！！！

    public static void quickSort(Comparable[] data,int min,int max) {

    //快排的支持方法

    public static int findPartition(Comparable[] data,int min,int max){

        int left,right;

        Comparable temp,partitionelement;

        left = min;right = max;

        partitionelement = data[min];//partitionelement 是data[min]的一个副本

        while(left < right)

            while(data[left].compareTo(partitionelement) <= 0 && left < right)

                left++;

            while(data[right].compareTo(partitionelement) > 0)

                right--;

            if(left < right)

            {

                temp = data[left];

                data[left] = data[right];

                data[right] =temp;

            }

        temp = data[min];

        data[min] = data[right];

        data[right] = temp;

        //错错误的写法，要的是把第一个元素和data[right]交换，而不是它的副本

        //temp = data[right];

        //data[right] = partitionelement;

        //partitionelement = temp;

        return right;

本文转自农夫山泉别墅博客园博客，原文链接：http://www.cnblogs.com/yaowen/p/4476776.html，如需转载请自行联系原作者