首页 > 其他分享 >快速排序和栈溢出

快速排序和栈溢出

时间:2022-10-01 02:44:05浏览次数:47  
标签:int 基准 哨兵 区域 排序 快速 虚拟机 溢出

以前学算法的时候用的《啊哈!算法》,很抱歉,关于算法的各类书籍对于新手都很不友好,这本书绝对是新手第一本书。

  当然啦,如果你是大佬天才,直接跳过这本书。

下面介绍《啊哈!算法》中关于快排的讲解并简单回答 作者 对读者 提出的问题。由于快排用到了递归,这里顺便解释一下栈溢出的问题。

快速排序

  介绍快速排序

    快排------分治的递归算法。

    先来看看《数据结构与算法分析》对快排步骤的解释:

                  

 

          1、说明特殊情况

          2、在S这组数据中随便找一个数作为基准

          3、将S这组数据中除开基准数的其他数据分成两份,一份数据全小于基准数,一份数据全大于基准数。

          4、递归上面的步骤。

  具体步骤

    对于一组数据,视为一个区域,在此区域随便找一个数作为 基准数A(不过就是一个参照数而已),将这片区域中小于基准数A的放左边,大于 基准数A 的放右边。

        (上面这一步姑且称为基准数归位)

    以 基准数A 为界,划分左右两片区域,分别再找基准数B、C,重复上面的动作,将基准数B、C归位。直到分不出左右两片区域。

 

     第一步    统一取最左边数为基准数,同时在最左边和最右边派出两个哨兵,相向而行。   一定要是右哨兵先动

                    

                          图取自----《啊哈!算法》

 

        第二步                右哨兵负责找到小于基准数的位置,左哨兵负责找到大于基准数的位置,交换!

                    

      第三步                    重复第二步直到两哨兵相遇,交换基准数和哨兵脚下数的位置。此时完成了基准数归位

                    

 

      第四步                        以归位后的基准数为界,对左右两片区域分别找基准数,分别设置左右哨兵重复执行基准数归位。

    Java代码

        

 1     public static void quickSort(int[] arr, int left, int right){                                                
 2         if (left >= right) {
 3             return;                         //递归的出口---无法再分出左右两片区域
 4         }
 5         int i = left;                       //定义本区域左哨兵
 6         int j = right;                      //定义本区域右哨兵
 7         int temp = arr[left];               //设本片区域最左边的数为基准数
 8         int swap;                           //用于交换数的中间数
 9         while (i!=j){                       //循环直到本区域左右哨兵相遇
10             while (i<j && arr[j]>=temp){    //一定要右哨兵先动,找到小于基准数的位置停下
11                 j--;
12             }
13             while (i<j && arr[i]<=temp) {   //左哨兵动,找到大于基准数的地方停下
14                 i++;
15             }
16             if (i < j){                     //交换左右哨兵脚下的数
17                 swap = arr[i];
18                 arr[i] = arr[j];
19                 arr[j] = swap;
20             }
21         }
22                                             //退出循环,本区域的左右哨兵相遇了
23         arr[left] = arr[i];                 
24         arr[i] = temp;                      //交换基准与哨兵脚下的数,基准数归位
25         quickSort2(arr, left, i-1);         //划分左区域,递归
26         quickSort2(arr, j+1, right);        //划分右区域,递归
27     }
28 }

 

      作者提出的问题

        为什么定义最左边的数为基准一定要右哨兵先动。

        取极限情况

                  

 

 

 栈溢出

    

 

    概述

        在递归中,一定要往出口调用,不然就会出现栈溢出的问题。

    这里的栈是什么

                  

 

            可以理解为有一个栈,里面是放方法的,方法一直递归,栈就溢出了

      从虚拟机(HotSpot)角度来看:

          虚拟机是软件层面的

              .java文件编译为.class文件后,开始了虚拟机之旅,首先是类加载、链接、初始化,然后就进入了运行时数据区(每个虚拟机实例一份),

              一个Java程序就是一个进程,一个进程对应一个虚拟机实例。

 

                      

                                  ————《深入理解Java虚拟机》第三版

 

          在运行时数据区中有虚拟机栈(每个线程一份),栈由栈帧组成,一个栈帧对应着一个方法,方法不断进栈,栈就溢出了

          虚拟机栈先进后出,没有gc,栈顶的方法称为当前方法,当前方法执行完出栈才能执行下一个方法。

           

              具体的栈帧结构、方法调用本质不展开说,学习JVM一定要看看《深入理解Java虚拟机》哪怕看不懂也没关系。

 

标签:int,基准,哨兵,区域,排序,快速,虚拟机,溢出
From: https://www.cnblogs.com/tyt0o0/p/16746657.html

相关文章

  • ALV :汇总,分类汇总(小计),排序,过滤
    货铺QQ群号:834508274下面开始干货部分……ALV标准功能汇总,分类汇总,排序,过滤这些功能除了可以直接使用它的标准功能按钮之外,你也可以在程序里设定,让ALV列表第一次显示出来就......
  • 冒泡排序
    关于冒泡排序的理解packagearray;importjava.util.Arrays;publicclassShort{publicstaticvoidmain(String[]args){int[]z={1,4,113,5,213,7,3,......
  • 三步快速搭建android开发环境 (下载包已集成可用sdk,无需费心到google相应网站下载,快哉!)
    其中,adtbuntle在这里下:找到这个:​​adt-bundle-windows-x86_64-20140321.zip​​510.0M Android4.2(4.4?)多合一开发包,注意所含eclipse是64位的。===================......
  • 三角函数计算方法及快速查询表,做数控真是太有用了
    今天小编给大家整理了关于函数的计算方法,这应该对从事数控行业的你有所帮助,不会的赶紧学学吧。三角函数的关系(正弦)Sinθ=对边A/斜边C(余弦)Cosθ=邻边B/斜边C(......
  • 学习笔记——Django项目中的F对象,Q对象,聚合函数,排序
    2022-09-30F对象:在shell中是用于两个有关联的属性之间的查询。使用实例:查询书籍表中阅读量大于评论量的记录前提,进入pycharm,进入虚拟环境,进入shell环境。首先,要......
  • 在台钳上如何快速对刀?
    ​这是我最喜欢的方法,因为它每次设置都需要最少的时间和精力,尽管它确实需要预先进行一次设置。对于其他方法,每次将新工件放到机器上时,您都必须找到零零件。使用这种方法,您可......
  • Mastercam孔的快速编程方法
    钻孔是加工中非常常见的工序,对于少而简单的孔加工,单个选择即可完成编程。当遇到多而复杂的孔加工时,如果仍然一个一个的选择就会浪费时间,也可能出现错选或者漏选的现像,这时就......
  • Java实现6种常见排序
    1.冒泡排序(BubbleSort)第0轮3141592653589第1轮1314526535899第2轮1134255356899第3轮11324535568......
  • 【学习笔记】分页和排序
    分页和排序排序关键字:ORDERBY升序:ASC降序:DESC我们以学生成绩的升序降序为例,将学生排序语法:ORDERBY字段名DESC/ASCSELECTs.studentno,studentname,subjectna......
  • 冒泡排序
    inta[]={23,1,55,7,4,2};intn=6,i,j,temp;for(i=1;i<6;i++)//趟数{for(j=0;j<n-i;j++)//每趟的顺序比较 if(a[j]>a[j+1]) {......