黑马程序员技术交流社区

标题: 萌新排序之快排 [打印本页]

---

作者: PaulY    时间: 2019-1-14 19:38
标题: 萌新排序之快排

快速排序

基本思想：

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

优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！其平均时间复杂度为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则对应排序范围首尾元素下标。

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

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

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

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

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

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

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);

        }



    }

最后排序的结果图：

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2