a_day 阅读(713) 评论(0)

前言:

  写到快速排序时,之前已经进行了冒泡、选择、插入排序,发现算法问题很多东西都是和实际问题相逆的,实际你可能会由外及里,由上及下,可是算法里面它有时就需要你由里往外去扩散,好比最里面的是小成果,然后一次次往外变化,成果也慢慢变大,最后直至达到最终成果为止。本篇快速排序方法因为调用了递归,你就可以逆着由里及外来思考问题。  写这篇文章光画图就花费了我2小时时间,越抽象就越不好形容和比喻,画的不好,希望各位不要吐槽。

快速排序:先快速排序将队列一分为二,然后对每个队列进行递归调用快速排序方法,直至不能再次分解后依次返回成果。


 情景描述:

  紧接选择排序情景,有一天,被同学称为大湿的体育老师胃疼请假休息了,真好数学老师闲着就来代课了,同样要排列队形,但是数学老师牛了,说同学们,我今天教你们一种快速排序的方法,到时候来了别忘了教你们的体育老师哦(体育老师估计胃更疼了...)

一、

  1.  我们就把第一个同学当做基数,其他同学和他进行比较,期间,基数不变,此时基数同学站出来,留下了个空位
  2.  首先从最后一个同学开开始,依次向前和基数进行比较,第一个比基数同学等高或者矮了,就站到基数的位置,自己的位置又空下了
  3.  步骤2后,我们再从第一位依次向后和基数比较,如果等于或者比基数高,就站到步骤二留下的空位,自己位置空出来
  4.    排除前后已经换过位置的同学,重复步骤2和3, 依次和基数比较,然后坐入空位,留下新空位   
  5.    直到都和基数进行比较过,然后基数同学站到最后的空位里面

二、

  1.    通过步骤一我们把要排列的队分为了两队,而两队之内还是高低不齐的
  2.    首先来排前面的,让前面的队依旧以第一个为基数,结尾到分割线同学的前一位,执行步骤一
  3.    接着排后面的,以分割线同学的后一位为开始,队列末尾为结束,执行步骤一
  4. 重复执行步骤2和3,直至不能再拆分即排列完成

步骤一图解

上图为一轮快速排序方法


 步骤二图解

上图为依次递归调用快速排序方法,对每次的新队列进行快速排序


代码片段

/**
     * 快速排序,返回一个中轴下标
     * @param arr
     * @param low    队列起始下标
     * @param high    队列结束下标
     * @return
     */
    public int quickSort(int[] arr, int low, int high) {
        int tmp = arr[low]; // 数组的第一个作为中轴
        
        while (low < high) {
            while (low < high && arr[high] >= tmp) {
                high--;
            }
            arr[low] = arr[high]; // 比中轴小的记录移到低端
            
            while (low < high && arr[low] <= tmp) {
                low++;
            }
            arr[high] = arr[low]; // 比中轴大的记录移到高端
        }

        arr[low] = tmp; // 中轴记录到尾
        return low; // 返回中轴的位置
    }
    
    /** 递归调用快速排序方法,对数组进行排序 **/
    public void _quickSort(int[] list, int low, int high) {
        if (low < high) {
            int middle = quickSort(list, low, high); // 获得中轴下标
            // 对前部分进行排序,递归进行,此时不会执行后半部分,直至不能再次拆分,再依次执行下半部分
            _quickSort(list, low, middle - 1);
            // 对下半部分进行排序
            _quickSort(list, middle + 1, high); 
        }
    }

  代码挺少,但是没图的话理解起来太抽象了,还得边拿笔画着边执行着,完了才领悟了其原理。

再来严谨的总结下步骤:

  1. 设置两个变量i、j,排序开始的时候:i=0,j=N-1
  2. i开始向后搜索,即由前开始向后搜索(i ++ ),找到第一个大于keyA[i]A[i]A[j]交换
  3. j开始向前搜索,即由后开始向前搜索(j -- ),找到第一个小于key的值A[j]A[i]A[j]交换
  4. i开始向后搜索,即由前开始向后搜索(i ++ ),找到第一个大于keyA[i]A[i]A[j]交换
  5. 重复第345步,直到 I=J (3,4步是在程序中没找到时候j=j-1i=i+1,直至找到为止。找到并交换的时候i j指针位置不变。另外当i=j这过程一定正好是i+j-完成的最后令循环结束

优点:速度快,适合基本无序的队列

缺点:多个相同的值的相对位置也许会在算法结束时产生变动,所以不稳定,还有借用了递归思想,数据大量时消耗内存

  终于写完了,洗洗睡了:) ,最后把这几天的排序整合下:

 

                              写作不易,难免有疏漏和错误,还请慷慨指正,不错请推荐

  ps:欢迎转载,转载请注明出处:http://www.cnblogs.com/liuyitian/p/4077624.html


                                        每天多学一点点     代码少敲一点点