JAVA算法起步之快速排序实例

什么是快速排序

快速排序是一种十分高效的排序算法，采用分治的策略，对于数据量大的随机数组，快速排序是目前已知的最快的排序算法之一。它的基本思路是：通过一趟排序将待排序列分成两部分，一部分比基准元素小，一部分比基准元素大，然后再递归地对这个两部分进行快速排序，以达到整个序列有序的目的。

快速排序的基本步骤

1. 从数列中挑出一个元素，称为 "基准"（pivot）;
2. 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准后面（相同的数可以摆放到任一侧），在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值的子数列排序。

实现快速排序

快速排序的算法实现代码：

class QuickSort { 
    /* 
     * 快速排序方法：对数组array进行快速排序 
     * 参数说明： 
     *     array -- 待排序的数组 
     *     left  -- 数组的左边界(例如，从起始位置开始排序，则l=0) 
     *     right -- 数组的右边界(例如，排序截止到数组末尾，则r=array.length-1) 
     */ 
    public static void quickSort(int[] array, int left, int right) { 
        if(left < right) { 
            int i,j,x;
            i = left; 
            j = right; 
            x = array[i]; 
            while (i<j) { 
                while(i<j && array[j]>x) 
                    j--; 
                if(i<j) 
                    array[i++] = array[j]; 
                while(i<j && array[i]<x) 
                    i++; 
                if(i<j) 
                    array[j--] = array[i]; 
            } 
            array[i] = x; 
            quickSort(array,left,i-1); /* 递归调用 */ 
            quickSort(array,i+1,right);/* 递归调用 */ 
        } 
    } 

    public static void main(String[] args) { 
        int i; 
        int[] a = {30,40,60,10,20,100,90}; 
        long startTime = System.currentTimeMillis();/* 排序前取得当前时间 */ 

        quickSort(a,0,a.length-1); 

        long endTime = System.currentTimeMillis();/* 排序后取得当前时间 */ 
        System.out.println("排序时间： "+(endTime-startTime)+"ms"); 

        for(i=0; i<a.length; i++) 
            System.out.printf("%d ",a[i]); 
    } 
} 

实例分析1

例如，我们有一个包含10个元素的数组，待排序的数组为{49, 38, 65, 97, 76, 13, 27, 50, 2, 8}，每一次排序的过程如下所示：

第一次排序

初始序列：49, 38, 65, 97, 76, 13, 27, 50, 2, 8

选择第一个元素49作为基准，将大于49的元素放在右边，小于49的元素放在左边：

27, 38, 13, 2, 8, 49, 65, 97, 76, 50

左侧序列为27,38,13,2,8，右侧序列为65,97,76,50，分别对两个子序列进行递归排序。

第二次排序

左侧序列：27, 38, 13, 2, 8

选择第一个元素27作为基准，将大于27的元素放在右边，小于27的元素放在左边：

2, 8, 13, 27, 38

左侧序列为2,8,13，右侧序列为空，递归结束。

右侧序列：65, 97, 76, 50

选择第一个元素65作为基准，将大于65的元素放在右边，小于65的元素放在左边：

50, 65, 76, 97

左侧序列为50，右侧序列为76,97，分别对两个子序列进行递归排序。

第三次排序

左侧序列：50

左侧序列只有一个元素50，不需要排序，递归结束。

右侧序列：76, 97

选择第一个元素76作为基准，将大于76的元素放在右边，小于76的元素放在左边：

50, 65, 76, 97

左子序列为50,65，右子序列为97。

第四次排序

左侧序列：50, 65

左侧序列为50, 65，不需要排序，递归结束。

右侧序列：97

右侧序列只有一个元素97，不需要排序，递归结束。

最终排序结果：2,8,13,27,38,49,50,65,76,97。

实例分析2

例如，我们有一个包含10个元素的数组，待排序的数组为{3,2,1,5,4,6,8,7,9,10}，每一次排序的过程如下所示：

第一次排序

初始序列：3,2,1,5,4,6,8,7,9,10

选择第一个元素3作为基准，将大于3的元素放在右边，小于3的元素放在左边：

2, 1, 3, 5, 4, 6, 8, 7, 9, 10

左侧序列为2,1，右侧序列为5,4,6,8,7,9,10，分别对两个子序列进行递归排序。

第二次排序

左侧序列：2,1

选择第一个元素2作为基准，将大于2的元素放在右边，小于2的元素放在左边：

1, 2, 3, 5, 4, 6, 8, 7, 9, 10

左侧序列为1，右侧序列为3,5,4,6,8,7,9,10，分别对两个子序列进行递归排序。

第三次排序

左侧序列：1

左侧序列只有一个元素1，不需要排序，递归结束。

右侧序列：3,5,4,6,8,7,9,10

选择第一个元素3作为基准，将大于3的元素放在右边，小于3的元素放在左边：

1, 2, 3, 5, 4, 6, 8, 7, 9, 10

左子序列为4，右子序列为5,6,8,7,9,10。

第四次排序

左侧序列：4

左侧序列只有一个元素4，不需要排序，递归结束。

右侧序列：5,6,8,7,9,10

选择第一个元素5作为基准，将大于5的元素放在右边，小于5的元素放在左边：

1, 2, 3, 4, 5, 6, 8, 7, 9, 10

左子序列为7，右子序列为6,8,9,10。

第五次排序

左侧序列：7

左侧序列只有一个元素7，不需要排序，递归结束。

右侧序列：6,8,9,10

选择第一个元素6作为基准，将大于6的元素放在右边，小于6的元素放在左边：

1, 2, 3, 4, 5, 6, 8, 9, 10, 7

左子序列为8,9,10，右子序列为空。

第六次排序

左侧序列：8,9,10

左侧序列为8,9,10，不需要排序，递归结束。

右侧序列：空序列

右侧序列为空序列，不需要排序，递归结束。

最终排序结果：1,2,3,4,5,6,7,8,9,10。

总结

快速排序是一个非常高效的排序算法，由于其采用分治思想，不断地递归执行快速排序，因此也是一个非常经典的算法。在实际应用中，快速排序的时间复杂度较低，因此被广泛应用于大规模数据的排序。