文档章节

快速排序

超级普华
 超级普华
发布于 2014/12/16 13:53
字数 1663
阅读 12
收藏 0

1、快速算法思想

     快速排序是C.R.A.Hoare1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod)

1 分治法的基本思想

     分治法的基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

2)快速排序的基本思想

     设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:

①分解:

     在R[low..high]中任选一个记录作为基准(Pivot),以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)R[pivotpos+1..high],并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,右边的子区间中所有记录的关键字均大于等于pivot.key,而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。

  注意:

     划分的关键是要求出基准记录所在的位置pivotpos。划分的结果可以简单地表示为(注意pivot=R[pivotpos])

     R[low..pivotpos-1].keysR[pivotpos].keyR[pivotpos+1..high].keys

                  其中lowpivotposhigh

②求解:

     通过递归调用快速排序对左、右区间R[low..pivotpos-1]R[pivotpos+1..high]快速排序。

③组合:

     因为当"求解"步骤中的两个递归调用结束时,其左、右两个子区间已有序。对快速排序而言,"组合"步无需做什么,可看作是空操作。

2、快速排序算法QuickSort

  void QuickSort(SeqList Rint lowint high)

   { //R[low..high]快速排序

     int pivotpos //划分后的基准记录的位置

     if(low<high){//仅当区间长度大于1时才须排序

        pivotpos=Partition(Rlowhigh) //R[low..high]做划分

        QuickSort(Rlowpivotpos-1) //对左区间递归排序

        QuickSort(Rpivotpos+1high) //对右区间递归排序

      }

    } //QuickSort

  注意:

     为排序整个文件,只须调用QuickSort(R1n)即可完成对R[l..n]的排序。

3、划分算法Partition

1 简单的划分方法

 具体做法

  第一步:(初始化)设置两个指针ij,它们的初值分别为区间的下界和上界,即i=lowi=high;选取无序区的第一个记录R[i](R[low])作为基准记录,并将它保存在变量pivot中;

  第二步:令jhigh起向左扫描,直到找到第1个关键字小于pivot.key的记录R[j],将R[j])移至i所指的位置上,这相当于R[j]和基准R[i](pivot)进行了交换,使关键字小于基准关键字pivot.key的记录移到了基准的左边,交换后R[j]中相当于是pivot;然后,令i指针自i+1位置开始向右扫描,直至找到第1个关键字大于pivot.key的记录R[i],将R[i]移到i所指的位置上,这相当于交换了R[i]和基准R[j],使关键字大于基准关键字的记录移到了基准的右边,交换后R[i]中又相当于存放了pivot;接着令指针j自位置j-1开始向左扫描,如此交替改变扫描方向,从两端各自往中间靠拢,直至i=j时,i便是基准pivot最终的位置,将pivot放在此位置上就完成了一次划分。

 

划分算法

  int Partition(SeqList Rint iint j)

    {//调用Partition(Rlowhigh)R[low..high]做划分

     //并返回基准记录的位置

      ReceType pivot=R[i] //用区间的第1个记录作为基准 '

      while(i<j){ //从区间两端交替向中间扫描直至i=j为止

        while(i<j&&R[j].key>=pivot.key) //pivot相当于在位置i

          j-- //从右向左扫描查找第1个关键字小于pivot.key的记录R[j]

        if(i<j) //表示找到的R[j]的关键字<pivot.key

            R[i++]=R[j] //相当于交换R[i]R[j]交换后i指针加1

        while(i<j&&R[i].key<=pivot.key) //pivot相当于在位置j

            i++ //从左向右扫描查找第1个关键字大于pivot.key的记录R[i]

        if(i<j) //表示找到了R[i],使R[i].key>pivot.key

            R[j--]=R[i]; //相当于交换R[i]R[j],交换后j指针减1

       } //endwhile

      R[i]=pivot //基准记录已被最后定位

      return i

  } //partition


 

 

Java 部分源码:
    
    /**
     * 快速排序
     *
     * 基本思想
     *  设当前待排序的无序区为R[low..high],利用分治法可将快速排序的基本思想描述为:
     * ①分解:
     * 在R[low..high]中任选一个记录作为基准(Pivot),
     * 以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high],
     * 并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key,
     * 右边的子区间中所有记录的关键字均大于等于pivot.key,
     * 而基准记录pivot则位于正确的位置(pivotpos)上,它无须参加后续的排序。
     * 注意:
     * 划分的关键是要求出基准记录所在的位置pivotpos。
     * 划分的结果可以简单地表示为(注意pivot=R[pivotpos]):
     * R[low..pivotpos-1].keys≤R[pivotpos].key≤R[pivotpos+1..high].keys
     * 其中low≤pivotpos≤high。
     * ②求解:
     *  通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
     */
    public void recursionQuickSort( int left, int right )
    {
        if ( left >= right )
        {
            return;
        } else
        {
            int pivotpos = partition(left, right);
            recursionQuickSort(left, pivotpos-1); //对左半段排序
            recursionQuickSort(pivotpos+1, right); //对右半段排序        }
    }
   
    /**
     *
     * 以 arrays [left] 为pivot value将数组arrays中大于pivot value的值放到右边,小于的放到左边,
     * 中间就是pivot value,并返回pivot value所在的index
     *
     * @param left 左边index
     * @param right 右边index
     * @return 返回pivot value所在的index,称之为pivotpos
     */
    public int partition( int left, int right)
    {
        int pivotValue = arrays [left];
        while ( left<right )
        {
            //从右向左扫描,查找第1个元素值小于pivotValue的元素
            while ( left < right && pivotValue <= arrays [right] )
            {
                 right--;
            }
            if ( left<right )//表明找到一个元素值小于pivotValue的元素arrays [right]
            {
                arrays [left] = arrays [right];
                left++;//左边游标向右移一格
            }
           
            //从左向右扫描,查找第1个元素值大于pivotValue的元素arrays [left]
            while ( left < right && pivotValue > arrays [left] )
            {
                left++;
            }
            if ( left<right )//表明找到一个元素值大于pivotValue的元素arrays [left]
            {
                arrays [right] = arrays [left];
                right--;//右左边游标向左移一格
            }
        }
       
        arrays [left] = pivotValue;
        return left;
    }
   
}


© 著作权归作者所有

超级普华
粉丝 0
博文 6
码字总数 6874
作品 0
海淀
私信 提问
常用的简单排序算法集合(更新中)

/** 冒泡排序 /public static void Bubble_Sort(int[] a) {for (int i = 0; i < a.length - 1; i++) {for (int j = 0; j < a.length - i - 1; j++) {if (a[j] > a[j + 1]) {a[i] = a[i] + a[......

维特的烦恼
2014/04/26
139
1
快速排序详解 Java实现

一、快速排序的优缺点 对一个东西,首先要讲他的利与弊,才知道怎么使用它。快速排序适用于各种不同的输入数据且在一般应用中比其他排序都要快得多。快速排序引人注目的特点包括它是原地排序...

小车车
2016/09/03
67
0
每天学习一点儿算法--快速排序

快速排序是一种常用的优雅的排序算法,它使用分而治之的策略。 那么分而治之(D&C)是一种怎样的策略呢? 分而治之 分而治之(D&C)的要点只有两个: 找出简单的基线问题 确定如何缩小问题的...

爱吃西瓜的番茄酱
2018/01/11
0
0
好程序员Java教程教你5分钟了解快速排序

好程序员Java教程教你5分钟了解快速排序,前言: 快速排序是面试中经常会问到的一种排序算法,对比其他一些排序算法,快速排序的平均时间相对较少。 快速排序思想介绍 快速排序使用了分治的思...

好程序员IT
06/21
38
0
快速排序算法QuickSort

1.说明 快速排序法(quicksort)是目前所公认最快的排序方法之一(视解题的对象而定),虽然快速排序法在最差状况下可以达O(n2),但是在多数的情况下,快速排序法的效率表现是相当不错的。快...

嗯哼9925
2017/12/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Qt编写自定义控件55-手机通讯录

一、前言 前面几篇文章中的控件基本上难度系数接近0,甚至有凑控件数量的嫌疑,这次必须来一个强悍的控件,本控件难度系数在所有控件中排前五,代码量也不少,头文件都550行,实现文件1600行...

飞扬青云
24分钟前
21
0
C++与QML交互2:在QML中调用C++特性

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/xi_gua_gua/article/details/56991367 QML引擎(QQmlEngin...

shzwork
41分钟前
3
0
【Go专家编程】defer这里有个坑

前言 项目中,有时为了让程序更健壮,也即不panic,我们或许会使用recover()来接收异常并处理。 比如以下代码: func NoPanic() {if err := recover(); err != nil {fmt.Println("Recov...

恋恋美食
50分钟前
4
0
20190920笔记

扩展: bashrc和bash_profile http://ask.apelearn.com/question/7719 http://www.joshstaiger.org/archives/2005/07/bash_profile_vs.html echo 颜色 http://www.cnblogs.com/lr-ting/archi......

徐-锐
今天
3
0
Shiro整合Redis代码解读

1. shiro默认使用的MemoryConstrainedCacheManager创建MapCache来保存缓存数据。manager和cache对象之间的关系可以参考笔者的另一篇文章,Springboot Redis详解。 2. shiro整合Redis的关键就...

sunranhou
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部