请问一下这里面的换位操作是怎么实现的. 代码把我搞迷糊了.
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 左边;  //返回中心位置
    }

我写了半天的例子一下子点错了位置，全没了，看来编辑还是在不动鼠标的好啊。
给你个程序自己多找两个数组在草稿纸上画两下吧。

1. import java.util.Arrays;
   
2. 
   
3. public class QuickSort {
   
4. 
   
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.         }
    
20. 
    
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 09:49
我写了半天的例子一下子点错了位置，全没了，看来编辑还是在不动鼠标的好啊。
给你个程序自己多找两个数组 ...

额....好吧 我在去看看

你这个快速排序的代码太麻烦了.其实,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]

马镱洵 发表于 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-2 20:22
试一下排版:

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

i、j、temp可以在更小的局部定义

你贴的这个函数要实现什么功能？   你要干嘛？说清楚哦。

1. while(左边<右边 && arr[右边]>=pivot)   //while 循环执行一次之后会继续判断还是会向下面继续执行
   
2.                 右边--;

复制代码

继续判断。这里while循环，因为只有一条代码

1. 右边--;

复制代码

，故可以没写大括号。ps，这里会不会是你丢了大括号。也没法判断，实在看不懂你的代码要干嘛。
ps.函数名规范，首字母小写！

寇龙飞 发表于 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:01
老兄,我这代码排序绝对没有问题,希望你能先测试一下我的代码再提出疑问咯.
我把i j temp定义在方法里是有 ...

排序方法有很多种，你这种写法简单，效率如何？
LZ现在在研究的是快速排序
Arrays的sort方法都用到了快速排序，可想其效率...还算可以...

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

呵,我上面的代码就是快速排序的实现啊,您该不是认为我这代码不是快速排序的实现吧.

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

呵呵，没看出是快速排序，求教

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

我是参照Arrays.sort()方法的源码来写的,不过JDK的源码的快速排序太复杂了,我是把代码给简化了一下,又仔细看了一下源代码,我简化后的代码,效率是不如源码那么快吧,但是也足够快了.

马镱洵 发表于 2012-9-3 08:56
我是参照Arrays.sort()方法的源码来写的,不过JDK的源码的快速排序太复杂了,我是把代码给简化了一下,又仔 ...

你这简化后的就是冒泡排序，大量数据而且数据之间顺序毫无规矩的情况，效率定不及快速排序

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

你这就说笑了,虽然不是正宗的快速排序,但我这代码还是要比真正的冒泡排序要快多了.

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

何以证明？两两比较，大的放后面，这不是冒泡？那你认为冒泡的思想是怎样的？：

黑马-王言龙 发表于 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.         }
    
15. 
    
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.         }
    
34. 
    
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.         }
    
53. 
    
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:41
何以证明？两两比较，大的放后面，这不是冒泡？那你认为冒泡的思想是怎样的？： ...

我把冒泡排序和"我的快速排序"的代码都给你了,也写了主方法,你自己把两者都调用几次,自己做个比较吧,看看是不是"我的快速排序"就是你所指的"复杂化的冒充排序".

马镱洵 发表于 2012-9-3 09:54
我把冒泡排序和"我的快速排序"的代码都给你了,也写了主方法,你自己把两者都调用几次,自己做个比较吧,看看 ...

好吧，你赢了，你那不是冒泡，我的是冒泡。

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

确实不是冒泡,不过我也知道这也不是正宗的快速排序,我也说不出来是什么排序,我就默认是另类快速排序好了,呵呵.