排序算法总结之快速排序(2)

/**
    * 实现了递归的快排主例程, internal quicksort method that makes recrusive calls
    *
    * @param arr
    *            an array of comparable items
    * @param left
    *            the left-most index of subarray
    * @param right
    *            the right-most index of subarray
    */
    private static <T extends Comparable<? super T>> void quickSort(T[] arr,
            int left, int right) {
        if(left + CUTOFF <= right)
        {
            T pivot = media3(arr, left, right);
           
            //begin partitoning
            int i = left, j = right - 1;//在media3中已经将比pivot小的元素放到了a[left]上,把pivot放到了arr[right-1]上,故下面的while中是 ++i 和 --j
            for(;;)
            {
                while(arr[++i].compareTo(pivot) < 0){}
                while(arr[--j].compareTo(pivot) > 0){}
                if(i < j)
                    swapReference(arr, i, j);
                else
                    break;
            }
            swapReference(arr, i, right - 1);//restore pivot
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }else
            //Do an insertion sort on the subarray
            insertSort(arr, left, right);
    }
}

①第3行CUTOFF定义当数组中元素个数为10以下时,采用插入排序。

②第11行的quickSort方法是快排对外提供的接口

③第26行的media3方法实现了三数取中选取枢轴元素。其实,它不仅仅返回了枢轴元素,它还改变了原数组:

1) 它将三个数中最大的那个数放在了数组末尾arr[right]---(比枢轴小的放在枢轴元素左边)

2) 它将三个数中最小的那个数放在了数组的开头arr[left]---(比枢轴大的放在枢轴元素右边)

3) 它将三个数中的中间那个数(枢轴元素)放在了 arr[right-1]位置处!!!---(在第71-72行选取是否交换元素时可以不受枢轴影响)

这是快排算法实现的技巧。

④第61行的quickSort方法则是实现快速递归分割的主例程。首先在第65行选取枢轴元素,第71行,在数组左边寻找比枢轴元素大的元素;第72行,在数组右边寻找比枢轴元素小的元素,第73-74行将之进行交换。可以看出,这些语句实现得非常精巧:在循环中只有自增和自减操作,以及判断语句,因此执行速度是很快的。

在media3中已经将比pivot小的元素放到了a[left]上,把pivot放到了arr[right-1]上,故下面的while中是 ++i 和 --j
⑤第73行if语句 当 i > j 时 表示一趟快排已经结束,第78行将枢轴元素放到它的最终位置。对于快排而言,每进行一趟,枢轴元素的位置就被唯一确定下来,以后都不再变。

⑥第79 和 80行,对枢轴元素左右两个的子数组递归调用。这样,将原问题,划分成了两个子问题。

可以写出它们的递归表达式:T(N)=T(i)+T(N-i-1)+O(N)

⑦当 快速排序划分的子数组足够小时(CUTOFF),不再采用快速排序,而是用插入排序。这样,进一步优化了快速排序的速度。

用到的插入排序实现如下:

private static <T extends Comparable<? super T>> void insertSort(T[] a, int left ,int right){
        for(int p = left + 1; p <= right; p++)
        {
            T tmp = a[p];//保存当前位置p的元素,其中[0,p-1]已经有序
            int j;
            for(j = p; j > 0 && tmp.compareTo(a[j-1]) < 0; j--)
            {
                    a[j] = a[j-1];//后移一位
            }
            a[j] = tmp;//插入到合适的位置
        }

四,快速排序算法复杂度分析

①快速排序的时间复杂度与枢轴元素的选取息息相关。平均情况下,时间复杂度为O(NlogN),最坏情况下为O(N^2)

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/522cd088182f72f12ec2b579851c5ad9.html