传智播客旗下技术交流社区北京校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© PaulY 初级黑马   /  2019-1-14 19:38  /  125 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 PaulY 于 2019-1-14 19:50 编辑

快速排序



基本思想:

从待排序列中任取一个元素(例如取第一个) 作为中心,所有比它小的元素一律前放,所有比它大的元素一律后放,形成左右两个子表;然后再对各子表重新选择中心元素并依此规则调整(递归自己),直到每个子表的元素首尾标记相等或差值为一。此时便为有序序列了。


优点:因为每趟可以确定不止一个元素的位置,而且呈指数增加,所以特别快!其平均时间复杂度为O(nlogn),最坏情况下则是O(n2).
前提:顺序存储结构

具体实现过程:

先在要排序的序列 array中选取一个中轴值,而后将序列分成两个部分,其中左边的部分中的元素均小于或者等于中轴值,右边的部分元素均大于或者等于中轴值,而后通过递归调用快速排序的过程分别对两个部分进行排序,最后将两部分产生的结果合并即可得到最后的排序序列。


“基准值”的选择有很多种方法。最简单的是使用第一个记录的关键字值。但是如果输入的数组是正序或者逆序的,就会将所有的记录分到“基准值”的一边。较好的方法是随机选取“基准值”,这样可以减少原始输入对排序造成的影响。但是随机选取“基准值”的开销大。

  为了实现一次划分,我们可以从数组(假定数据是存在数组中)的两端移动下标,必要时交换记录,直到数组两端的下标相遇为止。为此,我们附设两个下角标low和high,分别代表遍历过程中首尾元素下标,将第一个元素定为基准(或中轴值),通过high从当前序列的有段向左扫描,越过不小于基准值的记录。当遇到小于基准值的记录时,扫描停止,将array[high]对应元素赋值给array[low],然后通过low角标从当前序列的左端向右扫描,越过小于基准值的记录。当遇到不小于基准值的记录时,扫描停止。将array[low]对应元素赋值给array[high](也可以在左右都遇到与条件不符的元素后在进行互换)。然后,继续扫描,直至low与high相遇为止。扫描和交换的过程结束。这是low与high值相等,且左边的记录的关键字值都小于基准值,右边的记录的关键字值都不小于基准值。

下面我们通过一个案例来演示一下快速排序的基本步骤: 以序列{ 56, 92, 24,37, 48, 86, 13, 39, 50, 90} 共10个元素。


定义temp保存基准值,pivotkey保存数组基准值所在下标,low跟high则对应排序范围首尾元素下标。

qs01.JPG

先将a[0]元素值定义为基准值,存入temp中

qs02.JPG
high标记从尾元素开始向前遍历,在遍历至a[8]时,元素值小于基准值,遍历停止,high角标对应元素值替换掉low角标对应元素值(对应元素以先行存入temp中,不会丢失)low标记开始从首元素向后遍历,在遍历至a[1]时,元素值大于基准值,遍历停止,low角标对应元素值替换掉high角标对应元素值

qs03.JPG
low标记开始从首元素向后遍历,在遍历至a[1]时,元素值大于基准值,遍历停止,low角标对应元素值替换掉high角标对应元素值

qs04.JPG
high标记继续向前遍历,在遍历至a[7]时,元素值小于基准值,遍历停止,high角标对应元素值替换掉low角标对应元素值

qs05.JPG
low标记继续向后遍历,在遍历至a[5]时,元素值大于基准值,遍历停止,low角标对应元素值替换掉high角标对应元素值

qs06.JPG
high标记继续向前遍历,在遍历至a[6]时,元素值小于基准值,遍历停止,high角标对应元素值替换掉low角标对应元素值

qs07.JPG
low标记继续向后遍历,在遍历至a[6]时,low与high标记相遇,此时将temp中基准值存入数组,并将数组对应下标传至pivotkey中保存,后返回至调用处,一次排序结束。并将整个数组以a[6]为中轴,分为左右两个数组(或子表)。
代码实现如下:
[Java] 纯文本查看 复制代码
public int[] quickSort(int[] array, int low, int high ,int[]arraymark){
        //挖坑填坑法:
        int temp;
        temp = array[low];
        while (low < high){
            while(array[high] > temp && low < high) {
                --high;
            }
            array[low] = array[high];
            while (array[low] <= temp && low < high){
                ++low;
            }
            array[high] = array[low];
        }
        array[low] = temp;
        arraymark[1]++;
        if (arraymark[1] < 10) {
            System.out.print("第0" + arraymark[1] + "次快速排序结果:");
        }else{
            System.out.print("第" + arraymark[1] + "次快速排序结果:");
        }
        for (int index = 0; index < array.length; index++) {
            System.out.print(array[index] + " ");
        }
        arraymark[0] = low;
        System.out.println();
        return arraymark;
    }
由于是个萌新,只好用数组返回多个值方便调用......

后续每趟中对各子表的操作都相似,所以主程序可采用递归算法,多次递归后,整个序列完成有序排列。

代码如下:
[Java] 纯文本查看 复制代码
public void qSort(int[] array, int low, int high, int[] pivotkey){
        if (low < high){
            pivotkey = quickSort(array, low, high ,pivotkey);
            qSort(array,low,pivotkey[0]-1,pivotkey);
            qSort(array,pivotkey[0]+1,array.length-1,pivotkey);
        }

    }
最后排序的结果图: 捕获.JPG




分享至 : QQ空间
收藏

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马