黑马程序员技术交流社区

标题: 【已解决】快速排序的问题. [打印本页]
作者: 张吉日    时间: 2012-9-2 08:48
标题: 【已解决】快速排序的问题.
本帖最后由 张吉日 于 2012-9-3 10:05 编辑

请问一下这里面的换位操作是怎么实现的. 代码把我搞迷糊了.
static int Partition(int[] arr, int 左边, int 右边)
    {
        int pivot = arr[左边];//把中心置于a[0]
        while (左边 < 右边)
        {
            while(左边<右边 && arr[右边]>=pivot)   //while 循环执行一次之后会继续判断还是会向下面继续执行
                右边--;
            //将比中心记录小的移到低端
        int tmp = arr[右边];
            arr[右边] = arr[左边];
            arr[左边] = tmp;
            while(左边<右边 && arr[左边]<=pivot)
                左边++;
            tmp = arr[右边];
            arr[右边] = arr[左边];
            arr[左边] = tmp;
           //将比中心记录大的移到高端
        }
        arr[左边] = pivot; //中心移到正确位置
        return 左边;  //返回中心位置
    }
作者: 黑马-王言龙    时间: 2012-9-2 09:49
我写了半天的例子一下子点错了位置，全没了，看来编辑还是在不动鼠标的好啊。
给你个程序自己多找两个数组在草稿纸上画两下吧。
  1. import java.util.Arrays;

  3. public class QuickSort {

  5.         /**
  6.          * 快速排序
  7.          *
  8.          * 思路：
  9.          * 1、目标支点定位：拿初始支点和两端数据交替的进行比较。每一轮下来，目标支点左边的数值比支点小，右边的比支点大。
  10.          * 2、左右再分别进行目标支点的定位。
  11.          *
  12.          * 全部目标支点都找到时，即排序完成。
  13.          *
  14.          */
  15.         public static void main(String[] args) {
  16.                 int[] arr = {4,2,1,6,3,5,3};
  17.                 sort(arr, 0, arr.length-1);
  18.                 System.out.println(Arrays.toString(arr));
  19.         }

  21.         public static void sort(int[] arr, int low, int high) {
  22.                 if(low < high) {        //注意此处不能越界
  23.                         int pivotPosition = adjust(arr, low, high);//支点定位
  24.                         sort(arr, low ,pivotPosition-1);//支点左边递归定位
  25.                         sort(arr, pivotPosition+1, high);//支点右边递归定位
  26.                 }
  27.         }
  28.        
  29.         //支点定位
  30.         public static int adjust(int[] arr, int low, int high) {
  31.                 int pivot = arr[low];//初始支点为low位上数
  32.                 while(low < high) {
  33.                         while(low<high && compare(pivot, arr[high]) <= 0) {        //支点和高位数比，比高位数小，就high自减继续比。
  34.                                 high--;       
  35.                         }
  36.                        
  37.                         arr[low] = arr[high];        //支点比高位数大时，就将高位数放到low位
  38.                        
  39.                         while(low<high && compare(pivot, arr[low]) > 0) {        //再将支点和low位数值比较，比低位数大，low 自增继续比
  40.                                 low++;
  41.                         }
  42.                        
  43.                         //找到比支点大的，就将此数放到先前移走那个位置上
  44.                         arr[high] = arr[low];
  45.                         arr[low] = pivot;
  46.                 }
  47.                 System.out.println(arr[low]);
  48.                 return low;
  49.         }
  50.        
  51.         //数值比较
  52.         public static int compare(int num1, int num2) {
  53.                 return num1-num2;
  54.         }
  55. }
复制代码
作者: 张吉日    时间: 2012-9-2 17:01
黑马-王言龙 发表于 2012-9-2 09:49
我写了半天的例子一下子点错了位置，全没了，看来编辑还是在不动鼠标的好啊。
给你个程序自己多找两个数组 ...

额....好吧 我在去看看
作者: AngieFans85    时间: 2012-9-2 20:10
本帖最后由 马镱洵 于 2012-9-2 20:21 编辑

你这个快速排序的代码太麻烦了.其实,Arrays.sort()方法就是快速排序的实现了,硬要自己实现,我就提供一个我实现的代码吧:
  1. public static void quickSort2(int nums[]) {
  2. int i = 0, j = 0;
  3. int temp = 0;
  4. // 循环数组的长度次数,这个不用说了吧.
  5. for (i = 0; i < nums.length; i++) {
  6. // 判断条件很简单,只要第一个开始遍历的元素的值大于0,
  7. // 并且数组中前面一个数大于后面一个数,就能实现快速排序了.
  8. for (j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
  9. // 交换数组元素的代码,大家都懂的.
  10. temp = nums[j];
  11. nums[j] = nums[j - 1];
  12. nums[j - 1] = temp;
  13. }
  14. }
  15. }
复制代码
[/code]
作者: AngieFans85    时间: 2012-9-2 20:22
马镱洵 发表于 2012-9-2 20:10
你这个快速排序的代码太麻烦了.其实,Arrays.sort()方法就是快速排序的实现了,硬要自己实现,我就提供一个我 ...

试一下排版:
  1. public static void quickSort2(int nums[]) {
  2.                 int i = 0, j = 0;
  3.                 int temp = 0;
  4.                 // 循环数组的长度次数,这个不用说了吧.
  5.                 for (i = 0; i < nums.length; i++) {
  6.                         // 判断条件很简单,只要第一个开始遍历的元素的值大于0,
  7.                         // 并且数组中前面一个数大于后面一个数,就能实现快速排序了.
  8.                         for (j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
  9.                                 // 交换数组元素的代码,大家都懂的.
  10.                                 temp = nums[j];
  11.                                 nums[j] = nums[j - 1];
  12.                                 nums[j - 1] = temp;
  13.                         }
  14.                 }
  15.         }
复制代码
作者: 寇龙飞    时间: 2012-9-3 07:35
马镱洵 发表于 2012-9-2 20:22
试一下排版:

哥们，你的函数没有实现排序功能哦。for (j = i; j > 0 && nums[j - 1] > nums[j]; j--)

i、j、temp可以在更小的局部定义
作者: 寇龙飞    时间: 2012-9-3 07:53
你贴的这个函数要实现什么功能？   你要干嘛？说清楚哦。
  1. while(左边<右边 && arr[右边]>=pivot)   //while 循环执行一次之后会继续判断还是会向下面继续执行
  2.                 右边--;
复制代码
继续判断。这里while循环，因为只有一条代码
  1. 右边--;
复制代码
，故可以没写大括号。ps，这里会不会是你丢了大括号。也没法判断，实在看不懂你的代码要干嘛。
ps.函数名规范，首字母小写！
作者: AngieFans85    时间: 2012-9-3 08:01
本帖最后由 马镱洵 于 2012-9-3 08:06 编辑
寇龙飞 发表于 2012-9-3 07:35
哥们，你的函数没有实现排序功能哦。for (j = i; j > 0 && nums[j - 1] > nums[j]; j--)

i、j、temp可以 ...


老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.
我把i j temp定义在方法里是有原因的,因为如果定义在for循环里的话,每次进入for循环的语句,都会增加不必要的在栈内存中开辟变量的系统资源,例如:
  1. // 循环数组的长度次数,这个不用说了吧.
  2.                 for (int i = 0; i < nums.length; i++) {
  3.                         // 判断条件很简单,只要第一个开始遍历的元素的值大于0,
  4.                         // 并且数组中前面一个数大于后面一个数,就能实现快速排序了.
  5.                         for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
  6.                                 // 交换数组元素的代码,大家都懂的.
  7.                                 temp = nums[j];
  8.                                 nums[j] = nums[j - 1];
  9.                                 nums[j - 1] = temp;
  10.                         }
  11.                 }
复制代码
每次一开始执行内循环时,就会在栈空间开辟int变量,程序在栈空间开辟内存的这个过程,也是需要一点cpu资源的,这种资源的消耗根本是不必要的.
总结一下,如果只有一层循环语句,那就可以在for循环内部定义变量.
其实,把所有的变量定义在方法里,而不定义在循环内部,是一种好习惯.不仅省去了多余的确cpu资源的开销,而且在外部调用该方法直到该方法调用结束时,方法中所有的局部变量以及参数都会立刻被释放掉.
作者: 黑马-王言龙    时间: 2012-9-3 08:35
马镱洵 发表于 2012-9-3 08:01
老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.
我把i j temp定义在方法里是有 ...

排序方法有很多种，你这种写法简单，效率如何？
LZ现在在研究的是快速排序
Arrays的sort方法都用到了快速排序，可想其效率...还算可以...
作者: AngieFans85    时间: 2012-9-3 08:40
黑马-王言龙 发表于 2012-9-3 08:35
排序方法有很多种，你这种写法简单，效率如何？
LZ现在在研究的是快速排序
Arrays的sort方法都用到了快速 ...

呵,我上面的代码就是快速排序的实现啊,您该不是认为我这代码不是快速排序的实现吧.
作者: 黑马-王言龙    时间: 2012-9-3 08:42
马镱洵 发表于 2012-9-3 08:40
呵,我上面的代码就是快速排序的实现啊,您该不是认为我这代码不是快速排序的实现吧. ...

呵呵，没看出是快速排序，求教
作者: AngieFans85    时间: 2012-9-3 08:56
黑马-王言龙 发表于 2012-9-3 08:42
呵呵，没看出是快速排序，求教

我是参照Arrays.sort()方法的源码来写的,不过JDK的源码的快速排序太复杂了,我是把代码给简化了一下,又仔细看了一下源代码,我简化后的代码,效率是不如源码那么快吧,但是也足够快了.
作者: 黑马-王言龙    时间: 2012-9-3 09:31
本帖最后由 黑马-王言龙 于 2012-9-3 09:36 编辑
马镱洵 发表于 2012-9-3 08:56
我是参照Arrays.sort()方法的源码来写的,不过JDK的源码的快速排序太复杂了,我是把代码给简化了一下,又仔 ...


你这简化后的就是冒泡排序，大量数据而且数据之间顺序毫无规矩的情况，效率定不及快速排序
作者: AngieFans85    时间: 2012-9-3 09:38
黑马-王言龙 发表于 2012-9-3 09:31
你这简化后的就是冒泡排序，大量数据而且数据之间顺序毫无规矩的情况，效率定不及快速排序 ...

你这就说笑了,虽然不是正宗的快速排序,但我这代码还是要比真正的冒泡排序要快多了.
作者: 黑马-王言龙    时间: 2012-9-3 09:41
马镱洵 发表于 2012-9-3 09:38
你这就说笑了,虽然不是正宗的快速排序,但我这代码还是要比真正的冒泡排序要快多了. ...

何以证明？两两比较，大的放后面，这不是冒泡？那你认为冒泡的思想是怎样的？：
作者: AngieFans85    时间: 2012-9-3 09:47
本帖最后由 马镱洵 于 2012-9-3 09:50 编辑
黑马-王言龙 发表于 2012-9-3 09:41
何以证明？两两比较，大的放后面，这不是冒泡？那你认为冒泡的思想是怎样的？： ...
  1. public static void main(String[] args) {
  2.                 int[] temps = new int[20000];
  3.                 for (int i = 0; i < temps.length; i++) {
  4.                         temps[i] = (int) (Math.random() * 1000);
  5.                 }
  6.                 long start = System.currentTimeMillis();
  7.                 // quickSort2(temps);
  8.                 bubeerSoft(temps);
  9.                 long end = System.currentTimeMillis();
  10.                 System.out.println("start=" + start);
  11.                 System.out.println("end=" + end);
  12.                 System.out.println("排序用时" + (end - start) + "毫秒");
  13.                 print(temps);
  14.         }

  16. /**
  17.          * 冒泡排序
  18.          *
  19.          * @param ints
  20.          */
  21.         public static void bubeerSoft(int[] ints) {
  22.                 int i = 0, j = 0;
  23.                 int temp = 0;
  24.                 for (i = 0; i < ints.length - 1; i++) {
  25.                         for (j = 0; j < ints.length - 1 - i; j++) {
  26.                                 if (ints[j] > ints[j + 1]) {
  27.                                         temp = ints[j];
  28.                                         ints[j] = ints[j + 1];
  29.                                         ints[j + 1] = temp;
  30.                                 }
  31.                         }
  32.                 }
  33.         }

  35. /**
  36.          * 快速排序的方法
  37.          *
  38.       public static void quickSort2(int nums[]) {
  39.                 int i = 0, j = 0;
  40.                 int temp = 0;
  41.                 // 循环数组的长度次数,这个不用说了吧.
  42.                 for (i = 0; i < nums.length; i++) {
  43.                         // 判断条件很简单,只要第一个开始遍历的元素的值大于0,
  44.                         // 并且数组中前面一个数大于后面一个数,就能实现快速排序了.
  45.                         for (j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
  46.                                 // 交换数组元素的代码,大家都懂的.
  47.                                 temp = nums[j];
  48.                                 nums[j] = nums[j - 1];
  49.                                 nums[j - 1] = temp;
  50.                         }
  51.                 }
  52.         }

  54. public static void print(int[] ints) {
  55.                 int i = 0;
  56.                 for (i = 0; i < ints.length; i++) {
  57.                         if (i != ints.length - 1)
  58.                                 System.out.print(ints[i] + " ");
  59.                         else
  60.                                 System.out.println(ints[i]);
  61.                 }
  62.         }
复制代码
作者: 黑马-王言龙    时间: 2012-9-3 09:53
好吧，你赢了，你那不是冒泡，我的是冒泡。
作者: AngieFans85    时间: 2012-9-3 09:54
黑马-王言龙 发表于 2012-9-3 09:41
何以证明？两两比较，大的放后面，这不是冒泡？那你认为冒泡的思想是怎样的？： ...

我把冒泡排序和"我的快速排序"的代码都给你了,也写了主方法,你自己把两者都调用几次,自己做个比较吧,看看是不是"我的快速排序"就是你所指的"复杂化的冒充排序".
作者: 黑马-王言龙    时间: 2012-9-3 09:55
马镱洵 发表于 2012-9-3 09:54
我把冒泡排序和"我的快速排序"的代码都给你了,也写了主方法,你自己把两者都调用几次,自己做个比较吧,看看 ...

好吧，你赢了，你那不是冒泡，我的是冒泡。
作者: AngieFans85    时间: 2012-9-3 09:59
黑马-王言龙 发表于 2012-9-3 09:55
好吧，你赢了，你那不是冒泡，我的是冒泡。

确实不是冒泡,不过我也知道这也不是正宗的快速排序,我也说不出来是什么排序,我就默认是另类快速排序好了,呵呵.
作者: 黑马-王言龙    时间: 2012-9-3 10:00
马镱洵 发表于 2012-9-3 09:59
确实不是冒泡,不过我也知道这也不是正宗的快速排序,我也说不出来是什么排序,我就默认是另类快速排序好了, ...

好吧，你赢了，你那不是冒泡，我的是冒泡。
作者: 寇龙飞    时间: 2012-9-3 11:02
本帖最后由 寇龙飞 于 2012-9-3 11:04 编辑
马镱洵 发表于 2012-9-3 08:01
老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.
我把i j temp定义在方法里是有 ...

老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.

测试啥，读了下就不是快速排序，懒得复制过去测试。你这就是一个稍微优化了点的的伪冒泡（并不一定比真正的冒泡快），有2个问题，实际运行中，1、新增变量temp浪费资源，2、交换赋值过程并没位运算效率高。




每次一开始执行内循环时,就会在栈空间开辟int变量,程序在栈空间开辟内存的这个过程,也是需要一点cpu资源的,这种资源的消耗根本是不必要的.

我在意的也是这一点cpu资源，抱歉的是，每次执行内循环后，这点资源就被释放了。我没必要放大它的生命周期，让其存在于整个方法中，浪费我的资源，并且提高代码耦合度、损坏我代码的逻辑性，极易出错、改bug时哥们就爽了。
作者: AngieFans85    时间: 2012-9-3 11:21
本帖最后由 马镱洵 于 2012-9-3 11:23 编辑
寇龙飞 发表于 2012-9-3 11:02
老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.

测试啥，读了下就不是快速排 ...


"测试啥，读了下就不是快速排序，懒得复制过去测试。你这就是一个稍微优化了点的的伪冒泡（并不一定比真正的冒泡快），"

你挺有趣的.也不测试一下16的代码,就直接断定是伪冒泡了,真行.
还不一定比真正的冒泡快(是不是比真正的冒泡快,你试一下不就知道了吗.有句话叫做光说不练是嘴把式.),我就直接告诉你答案吧.在我的机器上,随机产生20000个int型数据放进一个int型数组中,然后调用我写的"快速排序"方法,测试结果是用时300多毫秒,和插入排序的效率差不多.但是如果是调用真正的冒泡排序,测试结果是1000多毫秒.你要不信,自己就将16楼的代码放进你的eclipse中,然后多试几次,自然就有答案了.
不想多说了,我代码都发出来,你还要来争,我只好表示无可奈何了,如果只是来斗嘴,而不用代码来说事儿的话,那我只好绕道了,因为我惹不起.



"1、新增变量temp浪费资源，2、交换赋值过程并没位运算效率高。"

没错啊,用位运算方式来交换数组的元素,速度确定是最快.但是本贴从始至终都没有谁在争论用temp变量的速度快,还是用位运算的速度快啊,不知道你为什么要跟我说这个,我感觉莫明其妙的.



"我在意的也是这一点cpu资源，抱歉的是，每次执行内循环后，这点资源就被释放了。我没必要放大它的生命周期，让其存在于整个方法中，浪费我的资源，并且提高代码耦合度、损坏我代码的逻辑性，极易出错。"

OK,人各有志,你有你的理解,我不说你的代码好与不好.
我只想说,如果内循环每次都开辟新的空间,循环结束后又释放空间,这开辟与释放的过程,又多浪费了不少cpu资源了,假如内循环是循环1万次呢?这开辟与释放的过程所浪费的cpu资源岂不要连续浪费10000次?你说这10000次浪费的cpu资源少不少?又假如内循环是百万次呢?
将变量定义在方法中,循环结束后,方法也很快就结束,方法一结束,所开辟的temp变量自然就被释放.简单点说,从方法调用到方法结束,一共也就开辟了一次i,j和temp变量.将变量定义在循环中,又假如外循环和内循环的次数都很大呢,都10万次,那怎么办.
你的思维就建立在循环次数只有几次,那当然将变量定义在循环里自然没有什么性能上的问题了.
另外我不明白的是,将变量定义在方法中,怎么就提高了代码的耦合度了?怎么就损坏了代码的逻辑性了?怎么就易出错了?你的解释呢?
作者: AngieFans85    时间: 2012-9-3 11:46
寇龙飞 发表于 2012-9-3 11:02
老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.

测试啥，读了下就不是快速排序 ...

技术上的东西有了分歧,本来就少不要辩论,但是这个辩论不能只是口头争论,而不自己去测试.我欢迎并鼓励所有java爱好者对技术问题进行探讨和辨认,这也是提高实力的一种步骤.
假如你对我前面几贴的回复有什么技术上的质疑,大可以提出来,我从来不会因为辩论输了而觉得没有面子.
同时我也希望对方能摆正心态,切实面向技术问题,而不是面向面子.
作者: AngieFans85    时间: 2012-9-3 14:37
寇龙飞 发表于 2012-9-3 11:02
老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.

测试啥，读了下就不是快速排序 ...

"越往下争论，牵扯到的其他知识越多，新的分歧增加。论坛这种文字形式的讨论，讨论某一个点还行。像咱两这种较真下去，三天三夜都不够。"

你的意思是,你还是认为我的那个排序方法是伪冒泡方法吗?怎么,你试过了那个方法的效率了吗?假如你还是认为我的那个是伪冒泡方法,那么我就要请问了:
测试20000个数据的排序,真正的冒泡方法用时1000多毫秒,而我写的那个方法用时不到400毫秒,请问您是认为真正的冒泡排序与你口中的"伪冒泡排序"用时差不多,还是相差很多?这一点非常重要.
如果你想说,虽然我的排序方法比真正的冒泡排序方法用时要少很多,但是你还是坚定的认为我的排序方法就是伪冒泡方法或者另类冒泡排序方法,那你当我什么也没有问就是了,我只好无语了.



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