A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 、zhi 于 2013-5-27 12:44 编辑
  1. <font size="2">package com.itheima;</font>
  2. <font size="2">
  3. </font>
  4. <font size="2">import java.util.Random;</font>
  5. <font size="2">
  6. </font>
  7. <font size="2">import org.junit.Test;</font>
  8. <font size="2">
  9. </font>
  10. <font size="2">
  11. </font>
  12. <font size="2">public class Test1 {</font>
  13. <font size="2">        int i = 0; //定义一个整型的i记录排序的次数</font>
  14. <font size="2">
  15. </font>
  16. <font size="2">        public static void main(String[] args) {</font>
  17. <font size="2">                Test1 T = new Test1();</font>
  18. <font size="2">                // int[] arr = {49,38,65,97,78,13,27};</font>
  19. <font size="2">                int[] arr = { 49, 38, 65, 97, 78, 13, 27, 12, 11 }; //实例化一个数组</font>
  20. <font size="2">                System.out.println("初始化数组为:");</font>
  21. <font size="2">                printArray(arr);  //把数组打印出来</font>
  22. <font size="2">
  23. </font>
  24. <font size="2">                T.Run(arr, 0, arr.length - 1); //开始排序</font>
  25. <font size="2">
  26. </font>
  27. <font size="2">        }</font>
  28. <font size="2">
  29. </font>
  30. <font size="2">        public void Run(int[] arr, int begin, int end) {  //一个递归,不断的对数组进行排序</font>
  31. <font size="2">                if (begin < end) {                     //只有开始索引比结束索引小的时候才进行排序</font>
  32. <font size="2">                        int key = getMiddle(arr, begin, end);  //进行排序并返回中间值的位置</font>
  33. <font size="2">                        Run(arr, begin, key - 1);  //对中间的左边进行递归</font>
  34. <font size="2">                        Run(arr, key + 1, end);   //对中间的右边进行递归</font>
  35. <font size="2">                }</font>
  36. <font size="2">        }</font>
  37. <font size="2">
  38. </font>
  39. <font size="2">        public int getMiddle(int[] arr, int frist, int last) {</font>
  40. <font size="2">
  41. </font>
  42. <font size="2">                int begin = frist;  //开始索引等于数组第一个下标</font>
  43. <font size="2">                int end = last;    //结束索引等于数组长度减一   </font>
  44. <font size="2">                int key = frist;   //基准数的索引等于数组的第一个索引</font>
  45. <font size="2">                while (begin < end) {  //每当开始索引小于结束索引的时候都不断的排序</font>
  46. <font size="2">
  47. </font>
  48. <font size="2">                        while (begin < end && arr[end] > arr[key]) { //从数组的结束索引开始不断向前找,直到找到一个比基准数小的数位置,然后进行交换</font>
  49. <font size="2">                                end--;  //找不到就向前走</font>
  50. <font size="2">                                if (end == key) { //如果结束索引等于开始索引了,那就要结束循环</font>
  51. <font size="2">                                        break;</font>
  52. <font size="2">                                }</font>
  53. <font size="2">                        }</font>
  54. <font size="2">
  55. </font>
  56. <font size="2">                        key = swap(arr, key, end); //找到了,就交换数据,并返回基准数交换后的索引</font>
  57. <font size="2">                        i++; //每次交换都统计次数</font>
  58. <font size="2">                        System.out.println("第" + i + "次结果为");</font>
  59. <font size="2">                        printArray(arr);  //输出这次交换后的数组</font>
  60. <font size="2">                        </font>
  61. <font size="2">                        while (begin < end && arr[begin] < arr[key]) {//从数组开始不断向后找,直到找到一个比基准数大的数,交换位置</font>
  62. <font size="2">                                begin++;  //找不到就向后走</font>
  63. <font size="2">                                if (begin == key) { //如果前后两个索引相等,就要结束循环</font>
  64. <font size="2">                                        break;</font>
  65. <font size="2">                                }</font>
  66. <font size="2">                        }</font>
  67. <font size="2">
  68. </font>
  69. <font size="2">                        key = swap(arr, key, begin); //找到了,就交换数据,并返回基准数交换后的索引</font>
  70. <font size="2">                        i++;</font>
  71. <font size="2">                        System.out.println("第" + i + "次结果为");</font>
  72. <font size="2">                        printArray(arr);</font>
  73. <font size="2">                        if (begin == end || begin > end) {  //如果前后索引相等或者前面的比后面的大,都要结束循环</font>
  74. <font size="2">                                break;</font>
  75. <font size="2">                        }</font>
  76. <font size="2">
  77. </font>
  78. <font size="2">                }</font>
  79. <font size="2">
  80. </font>
  81. <font size="2">                return begin; //返回中间数的索引</font>
  82. <font size="2">
  83. </font>
  84. <font size="2">        }</font>
  85. <font size="2">
  86. </font>
  87. <font size="2">        private int swap(int[] arr, int key, int x) {</font>
  88. <font size="2">                int temp = arr[x];  </font>
  89. <font size="2">                arr[x] = arr[key];</font>
  90. <font size="2">                arr[key] = temp;</font>
  91. <font size="2">
  92. </font>
  93. <font size="2">                return x; //比较后,要返回基准数新的索引</font>
  94. <font size="2">        }</font>
  95. <font size="2">
  96. </font>
  97. <font size="2">        private static void printArray(int[] arr) {</font>
  98. <font size="2">                for (int j : arr) { // 遍历输出数组的值</font>
  99. <font size="2">                        System.out.print(j + " ");</font>
  100. <font size="2">                }</font>
  101. <font size="2">                System.out.println(); // 换行</font>
  102. <font size="2">        }</font>
  103. <font size="2">
  104. </font>
  105. <font size="2">}</font>
复制代码
  1. int[] arr  = new int[20];
  2.                         for(int i = 0;i<arr.length;i++){
  3.                                 Random rand = new Random();  
  4.                                 arr[i] = rand.nextInt(100);  //生成0-100的之间的整型随机数并赋值给arr[i]
  5.                         }
复制代码
这个排序算法很奇怪,对于一些特定的数组是可以从小到大排出来的,但是有些数组就会排序失败,不能从小到大排出来。而且无论数组怎样,排序的次数很多,有没有高手帮忙看看问题出在哪里啊?感激不尽。

有很多人说想知道什么特别数组排不了:
                       int[] arr  = new int[20];
                        for(int i = 0;i<arr.length;i++){
                                Random rand = new Random();  
                                arr = rand.nextInt(100);  //生成0-100的之间的整型随机数并赋值给arr
                        }
如果数组的生成是上面的代码,就会很容易死循环。。

下面有个哥们解决了这个问题。

评分

参与人数 1技术分 +1 收起 理由
袁梦希 + 1 很给力!

查看全部评分

9 个回复

倒序浏览
楼主可否给出一个排不了的数组,我试了几个都是正确的,一时还真找不出来bug


初始化数组为:
1 3 5 7 9 2 4 6 897 78 13 27 12 11
第1次结果为
1 3 5 7 9 2 4 6 897 78 13 27 12 11
第2次结果为
1 3 5 7 9 2 4 6 897 78 13 27 12 11
第3次结果为
1 2 5 7 9 3 4 6 897 78 13 27 12 11
第4次结果为
1 2 3 7 9 5 4 6 897 78 13 27 12 11
第5次结果为
1 2 3 7 9 5 4 6 897 78 13 27 12 11
第6次结果为
1 2 3 7 9 5 4 6 897 78 13 27 12 11
第7次结果为
1 2 3 6 9 5 4 7 897 78 13 27 12 11
第8次结果为
1 2 3 6 7 5 4 9 897 78 13 27 12 11
第9次结果为
1 2 3 6 4 5 7 9 897 78 13 27 12 11
第10次结果为
1 2 3 6 4 5 7 9 897 78 13 27 12 11
第11次结果为
1 2 3 5 4 6 7 9 897 78 13 27 12 11
第12次结果为
1 2 3 5 4 6 7 9 897 78 13 27 12 11
第13次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第14次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第15次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第16次结果为
1 2 3 4 5 6 7 9 897 78 13 27 12 11
第17次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第18次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第19次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第20次结果为
1 2 3 4 5 6 7 9 11 78 13 27 12 897
第21次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第22次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第23次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第24次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第25次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
第26次结果为
1 2 3 4 5 6 7 9 11 12 13 27 78 897
回复 使用道具 举报
太复杂了,一点都不快,能设计出来这个复杂算法不得不赞一个{:soso_e179:}
回复 使用道具 举报
public class Test4 {
        public static void main(String[] args) {
                // TODO Auto-generated method stub               
                int[] arr = {23,4,56,12,567,34,21,9,56,3,12};
                sop(arr);
                kuaiPai(arr);
                sop(arr);

        }
        public static void kuaiPai(int[] arr){
            qSort(arr,0,arr.length-1);
               
        }
        public static void qSort(int[] arr,int low,int high){
                if(low<high){
                        int pin =part(arr,low,high);
                        qSort(arr,low,pin-1);
                        qSort(arr,pin+1,high);
                       
                        }
               
        }
        public static int part(int[] arr,int low,int high){
                int key = arr[low];
                int pin =low ;
                while(low<high){
                        while(low<high&&key<=arr[high])
                                high--;                       
                        arr[pin]=arr[high];
                        pin=high;
                        while(low<high&&key>=arr[low])
                                low++;
                        arr[pin]=arr[low];
                        pin=low;               

                }
                arr[pin]=key;       
                return pin;
        }
        public static void sop(int[] arr){
                System.out.print("[");
                for(int i=0;i<arr.length;i++){
                        if(i==arr.length-1)
                                System.out.println(arr[i]+"]");
                        else
                                System.out.print(arr[i]+",");
                }
        }

}
直接上代码

点评

这个代码我试过没问题。。。  发表于 2013-5-27 12:37

评分

参与人数 1技术分 +1 收起 理由
殇_心。 + 1

查看全部评分

回复 使用道具 举报
一些特定的数组楼主给出look下先
回复 使用道具 举报
该你改的你看看不行我再给你改应该没问题
import java.util.Random;
public class Test1 {
        int i = 0; //定义一个整型的i记录排序的次数


        public static void main(String[] args) {
                Test1 T = new Test1();
                //int[] arr={3,4,5,6,1,1,7};//下面getMiddle中的arr[end]>key会出现死循环,你的是arr[end]>arr[key]
               int[] arr = {49,38,65,97,78,13,27,1,2};
               // int[] arr = { 49, 38, 65, 97, 78, 13, 27, 12, 11 }; //实例化一个数组
                System.out.println("初始化数组为:");
                printArray(arr);  //把数组打印出来
                T.Run(arr, 0, arr.length - 1); //开始排序
        }


        public void Run(int[] arr, int begin, int end) {  //一个递归,不断的对数组进行排序
                if (begin < end) {                     //只有开始索引比结束索引小的时候才进行排序
                                        /*你这中间值也用KEY太蒙人,是不是应该换个*/
                        int key = getMiddle(arr, begin, end);  //进行排序并返回中间值的位置
                        Run(arr, begin, key - 1);  //对中间的左边进行递归
                        Run(arr, key + 1, end);   //对中间的右边进行递归
                }
        }


        public int getMiddle(int[] arr, int frist, int last) {
                int begin = frist;  //开始索引等于数组第一个下标
                int end = last;    //结束索引等于数组长度减一  
                //int key = frist;   //基准数的索引等于数组的第一个索引
                                int key = arr[frist];

                while (begin < end) {  //每当开始索引小于结束索引的时候都不断的排序

                        //while (begin < end && arr[end]>arr[key]) { //从数组的结束索引开始不断向前找,直到找到一个比基准数小的数位置,然后进行交换
                                                while (begin < end && arr[end]>=key) {//不加等号会出现死循环,例如一个数组中有相等的值

                                end--;  //找不到就向前走
                                                        //没必要出现这句
                                /*if (end == key) { //如果结束索引等于开始索引了,那就要结束循环
                                        break;
                                }*/

                        }       
                      //swap(arr, key, end); //找到了,就交换数据,并返回基准数交换后的索引
                                           swap(arr,begin,end);//你上面的传值是啥意思,为什么要和标志位换呢,是不是应该像我这样,感觉你的快排的原理和我的不大一样

                                          
                                           /*
                        i++; //每次交换都统计次数
                        System.out.println("第" + i + "次结果为");
                        printArray(arr);  //输出这次交换后的数组*///到这不是本次的最终结果,也许你的结果和我的不是一个意思,判断一次结果是标志的值发生变化才算一次结果

                        
                        while (begin < end && arr[begin]<=key) {//从数组开始不断向后找,直到找到一个比基准数大的数,交换位置
                                begin++;  //找不到就向后走
                               /* if (begin == key) { //如果前后两个索引相等,就要结束循环
                                        break;
                                }*/

                        }


                        //swap(arr, key, begin); //找到了,就交换数据,并返回基准数交换后的索引
                                                swap(arr, end, begin);

                                                /*
                        i++;
                        System.out.println("第" + i + "次结果为");
                        printArray(arr);*/

                                                /*if (begin == end || begin > end) {  //如果前后索引相等或者前面的比后面的大,都要结束循环
                                break;
                        }没必要*/


                }
                                i++;
                System.out.println("第" + i + "次结果为");
                printArray(arr);//输出一次结果


                return begin; //返回中间数的索引


        }


        private void swap(int[] arr, int key, int x) {
                int temp = arr[x];  
                arr[x] = arr[key];
                arr[key] = temp;
               // return x; //比较后,要返回基准数新的索引
        }


        private static void printArray(int[] arr) {
                for (int j : arr) { // 遍历输出数组的值
                        System.out.print(j + " ");
                }
                System.out.println(); // 换行
        }


}
撑不住了,看得有点晚睡了,不行你再给我huitie明天接着给你搞,不出意外应该没问题

评分

参与人数 1技术分 +1 收起 理由
殇_心。 + 1

查看全部评分

回复 使用道具 举报
如果问题已解决,请及时修改分类,否则继续提问,谢谢合作!
回复 使用道具 举报
、zhi 中级黑马 2013-5-27 12:41:22
8#
张俊迪 发表于 2013-5-27 01:46
该你改的你看看不行我再给你改应该没问题
import java.util.Random;
public class Test1 {

这组代码的话,我用的是随机生成20个数字,排了好久都没有排完,和我原来代码一样,特定的数组可以排,随机生成的数组很容易死循环:
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963568次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963569次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963570次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963571次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963572次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963573次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963574次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963575次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963576次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963577次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963578次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963579次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963580次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963581次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963582次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963583次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963584次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963585次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963586次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963587次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963588次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963589次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963590次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963591次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963592次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963593次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963594次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963595次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963596次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963597次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963598次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963599次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963600次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963601次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963602次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963603次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963604次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963605次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963606次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963607次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963608次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963609次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963610次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963611次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963612次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963613次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963614次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963615次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963616次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963617次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963618次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963619次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963620次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963621次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963622次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963623次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963624次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963625次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963626次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963627次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963628次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963629次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963630次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963631次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963632次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963633次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963634次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963635次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963636次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963637次结果为
3 5 9 10 10 9 20 31 32 71 94 43 77 97 64 34 34 90 38 92
第963638次结果为
回复 使用道具 举报
、zhi 发表于 2013-5-27 12:41
这组代码的话,我用的是随机生成20个数字,排了好久都没有排完,和我原来代码一样,特定的数组可以排,随 ...

我写的代码你好好看了吗,你把我的代码复制上,运行一下,是不是没问题,反正我的电脑上没问题,你知道发生死循环是为什么吗,因为你的数组中有相同的数,而你的排序中没有判断等号的时候,所以会出现死循环,你发生死循环是不是都会有相同的值,麻烦你好好看看我写的代码,还有,你的好好看看快排的原理
回复 使用道具 举报
我自己写过的快速排序的,试过了,没问题:
/**
         *
         * 快速排序的基本思想是:通过一趟排序将要排序的数据分成两部分,左边的所有数据都比右边所有数据都要小,
         * 然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
         */
public class Test2 {

        public static void main(String[] args) {

                int[] arr = {85,3,12,48,96,137,52};
                // 打印排序前的数组
                System.out.print("排序前:");
                printArr(arr);
                // 调用方法对数组进行排序
                qickSort(arr,0,arr.length-1);
                // 打印排序后的数组
                System.out.print("排序后:");
                printArr(arr);
        }

        //用于遍历数组并打印数组
        public static void printArr(int[] arr) {
                for(int a: arr){
                        System.out.print(a+" ");
                }
                System.out.println();
        }


        // 快速排序
        public static void qickSort(int[] arr ,int left,int right){
                int temp;
                int i = left,j = right;
                if(left<right){
                        temp = arr[left];
                        //下边这个循环完成了一趟排序,即将数组中小于temp的元素放在左边,大于temp的元素反正右边
                        while(i!=j){
                                // 从左往右扫描找到一个小于temp的元素
                                while(i<j && arr[j]>temp)
                                        --j;
                                if(i<j){
                                        // 找到后放在temp左边
                                        arr[i] = arr[j];
                                        // 把下次找的起点推后一位
                                        ++i;
                                }
                                // 从右往左扫描找到一个大于temp的元素
                                while(i<j && arr[i]<temp)
                                        ++i;
                                if(i<j){
                                        // 找到后放在temp右边
                                        arr[j] = arr[i];
                                        // 把下次找的起点前移一位
                                        --j;
                                }
                        }
                        // 将temp放在最终位置
                        arr[i] = temp;
                        //递归地对temp左边的元素进行排序
                        qickSort(arr,left,i-1);
                        //递归地对temp右边的元素进行排序
                        qickSort(arr,i+1,right);
                }
        }

}
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马