Java排序算法之——快速排序

算法简述

所谓快速排序算法是基于交换排序和递归思想的，它的速度的确如名字所示——快！并且这种一算一般被用作数量级比较大的数据当中，在大数据中有着很重要的地位。

算法流程

下面是快速排序算法的流程：
1、首先设定一个分界值（一般都是取中间或者第一个数），通过该分界值将数组分成左右两部分； 2、将数组中大于等于分界值的数值放在分界值的右边，将数组中小于等于分界值的数值放在分界值的左边；
3、然后左右两边的数组又可以按照这个方式进行独立排序；
4、重复这个过程，可以看出这是一种递归的思想，当递归到最后，整个数组也就排序完成；

实例讲解

下面通过一个例子来讲解一下：对数组int[] arr = {34,25,65,33,16,78,43,22}进行快速排序

1. 取33为分界值，用i,j两个引用从两端进行遍历，i从左边依次遍历直到找出比33大的数34(即arr[0]),j从右依次遍历直至找到比33小的数22（即arr[7]）交换这两个数的位置：

{22,25,65,33,16,78,43,34}

1. 然后i向右移，j向左移进行遍历，经过一轮后：{22,25,16,33,65,78,43,34}
2. 接下来通过递归调用，将左右数组进行排序。

代码片段

语言组织能力有限，直接上代码：

/**
     * 排序算法之快速排序
     * 参数arr为需要排序的数组
     * 参数left为数组的起始下角标即0
     * 参数right为数组的最后下角标即arr.length-1
     */
    private void quickSort(int[] arr,int left,int right)
    {
        int f,t;
        int rtemp,ltemp;
        ltemp = left;
        rtemp = right;
        f = arr[(left+right)/2];
        //经过一轮排序，已经将数组分为左右两部分
        while(ltemp<rtemp)
        {
            while(arr[ltemp]<f)
            {
                ++ltemp;
            }
            while(arr[rtemp]>f)
            {
                --rtemp;
            }
            if(ltemp<=rtemp)
            {
                t = arr[ltemp];
                arr[ltemp] = arr[rtemp];
                arr[rtemp] = t;
                --rtemp;
                ++ltemp;
            }
        }
        if(ltemp == rtemp)
        {
            ltemp++;
        }
        //进行递归排序
        if(left<rtemp)
        {
            quickSort(arr,left,ltemp-1);
        }
        if(ltemp<right)
        {
            quickSort(arr,rtemp+1,right);
        }
    }

总结

快速排序的精髓在于分治思想，分而治之，它的时间复杂度为O(nlog2n)。