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

写在前面

对于经典的排序算法大家都很熟悉，这里提供一个未经过严格测试的快速排序算法代码，仅供学习之用。

另外，说几点在写算法时的一般规律或者说快速记忆方法。

当然，对于分治类型的算法，一般都存在递归解法和非递归解法两种，这里也给出两种实现。

代码实现

package com.nggirl.test.sort;

import java.util.HashSet;
import java.util.Set;

public class QuickSort {

    public static void main(String[] args) {
        int[] sortArray = {1,3,2,6,4,5,9,7,8};
        new QuickSort().sort(sortArray, 0, 8);

        for(int x : sortArray){
            System.out.println(x);
        }


        System.out.println("=============================");
        new QuickSort().sortNonRecurse(sortArray, 0, 8);

        for(int x : sortArray){
            System.out.println(x);
        }
    }

    private void sort(int[] sortArray, int start, int end){
        if(sortArray == null || sortArray.length == 0){
            return;
        }
        if(start > end || start > sortArray.length || end - start > sortArray.length){
            return;
        }

        int pivot = pivot(sortArray, start, end);
        sort(sortArray, start, pivot-1);
        sort(sortArray, pivot+1, end);
    }

    private void sortNonRecurse(int[] sortArray, int start, int end){
        if(sortArray == null || sortArray.length == 0){
            return;
        }
        if(start > end || start > sortArray.length || end - start > sortArray.length){
            return;
        }

        class PartValue{
            private int start;
            private int end;

            public PartValue(int start, int end){
                this.start = start;
                this.end = end;
            }

            public int getStart() {
                return start;
            }
            public int getEnd() {
                return end;
            }
        }

        Set<PartValue> parts = new HashSet<PartValue>();
        parts.add(new PartValue(start, end));

        while(parts.size() != 0){
            Set<PartValue> nextParts = new HashSet<PartValue>();

            for(PartValue part : parts){
                int pivot = pivot(sortArray, part.getStart(), part.getEnd());
                if(part.getStart() < pivot-1){
                    nextParts.add(new PartValue(part.getStart(), pivot-1));
                }
                if(pivot+1 < part.getEnd()){
                    nextParts.add(new PartValue(pivot+1, part.getEnd()));
                }
            }

            parts = nextParts;
        }
    }

    private int pivot(int[] sortArray, int start, int end){
        int cur = sortArray[start];

        while(start < end){
            //右侧小的往左移动
            while(end > start && sortArray[end] > cur){
                end--;
            }
            if(end > start){
                sortArray[start++] = sortArray[end];
                sortArray[end] = cur;
            }

            //左侧大的右移
            while(start < end && sortArray[start] <= cur){
                start++;
            }
            if(start < end){
                sortArray[end--] = sortArray[start];
                sortArray[start] = cur;
            }
        }

        return start;
    }

}

关于递归实现

递归实现的思路很简单，关键是要把握两点。1.终止条件判断；2.递归调用方法。比如，上述代码中的sort方法：

private void sort(int[] sortArray, int start, int end){
        if(sortArray == null || sortArray.length == 0){
            return;
        }
        if(start > end || start > sortArray.length || end - start > sortArray.length){
            return;
        }

        int pivot = pivot(sortArray, start, end);
        sort(sortArray, start, pivot-1);
        sort(sortArray, pivot+1, end);
    }

其中，第二个if中的start > end是递归的终止条件，其他的都是入参检查。

后续的，pivot方法和分开两次调用的sort，就是递归过程。

对于正式的代码，一般来说在递归主方法调用的前面会加上一个包装方法，用来处理条件检查或者主方法所需数据的准备。类似于：

packSort(int[] sortArray, int start, int end){
    if(sortArray == null || sortArray.length == 0){
        return;
    }
    if(start > end || start > sortArray.length || end - start > sortArray.length){
        return;
    }

    sort(sortArray, start, end);
}

private void sort(int[] sortArray, int start, int end){
        //终止条件
        if(start > end){
            return;
        }

        //递归过程---裂变
        int pivot = pivot(sortArray, start, end);
        sort(sortArray, start, pivot-1);
        sort(sortArray, pivot+1, end);
}

非递归实现

对于非递归实现，如果你熟悉二叉树的遍历过程那么大概应该知道：深度优先遍历要用堆栈去辅助，广度优先遍历要用队列去辅助。

对于分治类型的算法都可以类比于树的广度优先遍历，也就是用队列做辅助存储，把后续需要递归遍历的入参插入到队列尾部。

当然，存储的方式不一定必须使用队列，但原理都是一样的，就是存储后续遍历的入参，也就是条件。

这里使用的是不断更新的一个HashSet去存储下一个水平层的所有遍历条件。（可以把二分的过程，想象成一个树状结构，每一次递归，完成树状的一个水平层。）

递归的条件，这里放到了一个局部内部类里面(因为这个类的有效范围仅仅是sortNonRecurse里面，所以使用了局部的内部类)：

class PartValue{
    private int start;
    private int end;

    public PartValue(int start, int end){
        this.start = start;
        this.end = end;
    }

    public int getStart() {
        return start;
    }
    public int getEnd() {
        return end;
    }
}

当然，这里选择HashSet可以看做一个败笔，用一个ArrayList相对来说更能够节省一些不必要的空间。

pivot这个关键方法

这里简单说一下pivot这个方法的过程（这里没有给出详细的解说，仅是给出了一个记忆的线索）：

首先，选择最左侧的值作为pivot-value；
然后，用3个while循环确定pivot的最终位置。内层的两个循环先把右侧第一个小于pivot-value的值移到左侧。再把左侧第一个大于pivot-value的值移动到右侧。由外边的循环不断的完成这个过程。直到start=end为止。
最后，返回start值，此时的start就是要找的划分为止，也就是pivot。

对于第一个步骤还可以采用随机选取的方式，避免sortArray有序时带来的低效。

最后

以上就是懦弱含羞草为你收集整理的快速排序的递归和非递归实现的全部内容，希望文章能够帮你解决快速排序的递归和非递归实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。