数据结构学习笔记3.2—快速排序

快速排序是目前最流行的算法,在大多数情况下,快速排序都是最快的,执行时间为O(N*logN)。

快速排序本质上是通过把一个数组划分为两个子数组,然后在递归调用自身对每一个字数组进行快速排序。

即数组划分为字数组A,B,在对A进行划分为A1,A2,对A1划分为A11,A12。。B也是如此执行,这就涉及到递归调用自身的操作。

1.取右值作为枢纽的情形

数据结构学习笔记3.2—快速排序
    /**
     * 快速排序
     * 
     * @param left
     * @param right
     */
    public static void quickSort(int left, int right, int[] arr)
    {
        // 检查数据是否只包含一个数据项,如果是,则为有序数组,无需排序
        if (right - left <= 0)
        {
            return;
        }
        else
        {
            // 设置参照值为最右边的数据值
            int pivot = arr[right];

            int partition = partitionIt(left, right, pivot, arr);

            // 调用自身对左边排序
            quickSort(left, partition - 1, arr);

            // 调用自身对右边排序
            quickSort(partition + 1, right, arr);
        }
    }
数据结构学习笔记3.2—快速排序

(1)设置枢纽:int pivot = arr[right]; 为了方便,这里选择做右边的作为枢纽。当一轮排序下来后,枢纽的位置在最终排序的位置就确定了,

这是因为,最终排序后,左边的数值总比枢纽的小,右边的数值总比枢纽的大。

 

(2)这里看到主要有3个方法

      1)partitionIt(left, right, pivot, arr); 数据结构学习笔记3.1节所描述的划分方法,主要是取出枢纽值。

      2)quickSort(left, partition - 1, arr); 递归调用自身排序左边的数组。

      3)quickSort(partition + 1, right, arr); 递归调用自身排序右边的数组。

递归方法可以这样理解:先把左边排好,再排列右边。

 

完整代码:

数据结构学习笔记3.2—快速排序
/**
     * 快速排序
     * 
     * @param left
     * @param right
     */
    public static void quickSort(int left, int right, int[] arr)
    {
        // 检查数据是否只包含一个数据项,如果是,则为有序数组,无需排序
        if (right - left <= 0)
        {
            return;
        }
        else
        {
            // 设置参照值为最右边的数据值
            int pivot = arr[right];

            int partition = partitionIt(left, right, pivot, arr);

            // 调用自身对左边排序
            quickSort(left, partition - 1, arr);

            // 调用自身对右边排序
            quickSort(partition + 1, right, arr);
        }
    }

    /**
     * 划分数据
     * 
     * @param left 左边数据
     * @param right 右边数据
     * @param pivot 参照值
     * @return
     */
    public static int partitionIt(int left, int right, int pivot, int[] arr)
    {
        // 左边指针
        // 左边数据-1,为了后面执行++leftPrt操作时,数据能正确+1
        int leftPrt = left - 1;

        // 右边指针
        // 右边数据-1,为了后面执行--rightPrt操作时,数据能正确-1
        int rightPrt = right + 1;

        while (true)
        {
            // 左边数据比参照值的小,不做后续操作,循环
            while (leftPrt < arr.length && arr[++leftPrt] < pivot)
            {
                int a = 0;
            }

            // 右边数据比参照值的大,不做后续操作,循环
            while (rightPrt > 0 && arr[--rightPrt] >= pivot)
            {
                int b = 0;
            }

            if (leftPrt >= rightPrt)
            {
                break;
            }
            else
            {
                // 交左右两边的数据
                swap(leftPrt, rightPrt, arr);
            }
        }

        // 重置参照值
        swap(leftPrt, right, arr);

        return leftPrt;
    }

    /**
     * 数据交换
     * 
     * @param index1 入参1
     * @param index2 入参2
     * @param arr 比较数组
     */
    public static void swap(int index1, int index2, int[] arr)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
数据结构学习笔记3.2—快速排序

 

2.取中值作为枢纽的情形

对于快速排序算法来说,最优的情况是有两个大小相等的子数组。

以右值作为枢纽,有一种情形:当数组以逆序排序列时,这时候产生N-1的子数组和一个只包含枢纽的子数组。此时执行的效率为O(N2)。

 

解决方法:

三数据项取中:思路是取数组N的第1个,第N/2个,第N个数据,即arr[0],arr[N/2],,arr[N-1]项数据,此时操作是:

(1)比较三项数据,取中间值作为枢纽。

(2)对这三个数据排序。

 

完整代码:

数据结构学习笔记3.2—快速排序
    /**
     * 快速排序
     * @param left 数组第一个位置,即0
     * @param right 数组最后一个数据,即arr.length - 1
     * @param arr 数组
     */
    public static void recQuickSort(int left, int right, int[] arr)
    {
        // 数组长度
        int size = right - left + 1;
        
        // 如果数据项只有3项
        if (size <= 3)
        {
            // 处理数组个数小于3个的数组
            manualSort(left, right, arr);
        }
        else
        {
            int median = midanOf3(left, right, arr);
            int partition = partitionIt(left, right, median, arr);
            recQuickSort(left, partition - 1, arr);
            recQuickSort(partition, right, arr);
        }
    }
    
    /**
     * 处理整个数组小于或等于3个数据项的数组
     * @param left 数组左边位置
     * @param right 数组右边位置
     * @param arr 数组
     */
    public static void manualSort(int left, int right, int[] arr)
    {
        int size = right - left + 1;
        if (size <= 1)
        {
            return;
        }
        if (size == 2)
        {
            // 如果左边数据大于右边数据,则交换位置
            if (arr[left] > arr[right])
            {
                swap(left, right, arr);
            }
            return;
        }
        // 数组长度为3
        else
        {
            // 交换位置,交换方法:先用第一个数据项一次于后面两个数据项比较,
            // 取出最小的数据放在最左边,然后在比较后面两个数据
            if (arr[left] > arr[right - 1])
            {
                swap(left, right, arr);
            }
            if (arr[left] > arr[right])
            {
                swap(left, right, arr);
            }
            if(arr[right- 1] > arr[right])    
            {
                swap(right - 1, right, arr);
            }
        }
    }
    
    /**
     * 取出3个数据项,排序,并将中枢取出放在数组right - 1位置
     * @param left 数组左边项
     * @param right数组右边项
     * @param arr 数组
     */
    public static int midanOf3(int left, int right, int[] arr)
    {
        // 取出中间项
        int center = (right + left) / 2;
        
        // 通过交换排序,思路与manualSort中使用的方法一致
        if (arr[left] > arr[center])
        {
            swap(left, center, arr);
        }
        if (arr[left] > arr[right])
        {
            swap(left, right, arr);
        }
        if (arr[center] > arr[right])
        {
            swap(center, right, arr);
        }
        
        // 交换中枢与right - 1的位置
        // 由于arr[right]的位置已经排好,即数值比中枢的要打,已经划分
        // 所以取倒数第二个数据right - 1的数据,将center中枢的位置与之交换,目的减少右边排序次数
        swap(center, right - 1, arr);
        
        // 此时位置值为中枢值
        return arr[right - 1]; 
    }
    
    /**
     * 划分数组
     * @param left 数组左边位置
     * @param right 数组右边位置
     * @param median 中枢值
     * @param arr 数组
     */
    public static int partitionIt(int left, int right, int median ,int[] arr)
    {
        int leftPrt = left;
        int rightPrt = right - 1; 
        
        while(true)
        {
            while (arr[++leftPrt] < median);
            while (arr[--rightPrt] > median);
            
            if (leftPrt >= rightPrt)
            {
                break;
            }
            else
            {
                // 左边大于中枢值,右边小于中枢值,交换
                swap(leftPrt, rightPrt, arr);
            }
        }
        
        // 重置中枢值,此时左边leftPrt指针的位置指向右边数组的第一个数据项,比中枢值大
        // 将左边标记的位置与right - 1交换,此时,中枢值所在的位置已经固定,不会在变
        swap(leftPrt, right - 1, arr);
        return leftPrt;
    }
    
    /**
     * 数据交换
     * 
     * @param index1 入参1
     * @param index2 入参2
     * @param arr 比较数组
     */
    public static void swap(int index1, int index2, int[] arr)
    {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
数据结构学习笔记3.2—快速排序

1. manualSort(left, right, arr);这个方法是处理当数组划分后,数组个数小于等于3个时,此时直接交换排序排序即可。

2.midanOf3(left, right, arr);这个方法是去数组(包含子数组)的中间值,也是通过比较交换的方法排序。

 

取中值排序的特点:对于随机排序,执行效果与取右值相差不大,但是在逆序中,排序消耗时间有明显的提高。

数据结构学习笔记3.2—快速排序

上一篇:第六课 2 物化视图


下一篇:开博。