黑马程序员技术交流社区

标题: 关于快速排序法，看不懂啊，欢迎指导啊 [打印本页]
作者: java8023    时间: 2015-6-7 23:54
标题: 关于快速排序法，看不懂啊，欢迎指导啊
本帖最后由 java8023 于 2015-6-8 00:10 编辑

  2. class Quick
  3. {
  4. 　public　void　sort(int　arr[],int　low,int　high)
  5. 　{
  6. 　int　l=low;
  7. 　int　h=high;
  8. 　int　povit=arr[low];

  10. 　while(l<h)
  11. 　{
  12. 　while(l<h&&arr[h]>=povit)
  13. 　h--;
  14. 　if(l<h){
  15. 　int　temp=arr[h];
  16. 　arr[h]=arr[l];
  17. 　arr[l]=temp;
  18. 　l++;
  19. 　}

  21. 　while(l<h&&arr[l]<=povit)
  22. 　l++;

  24. 　if(l<h){
  25. 　int　temp=arr[h];
  26. 　arr[h]=arr[l];
  27. 　arr[l]=temp;
  28. 　h--;
  29. 　}
  30. 　}
  31. 　print(arr);
  32. 　System.out.print("l="+(l+1)+"h="+(h+1)+"povit="+povit+"\n");
  33. 　if(l>low)sort(arr,low,l-1);
  34. 　if(h<high)sort(arr,l+1,high);
  35. 　}
  36. }
复制代码



作者: 雪域星辰    时间: 2015-6-7 23:56
html代码都出来了
作者: java8023    时间: 2015-6-7 23:57
怎么成这个样子了，坛主给删掉吧，我自己好像删不掉啊。谢谢坛主了。千万不要扣我的分 啊
作者: java8023    时间: 2015-6-8 00:01
雪域星辰 发表于 2015-6-7 23:56
html代码都出来了

怎么删掉这个帖子
作者: 杜黎明    时间: 2015-6-8 00:14
。。。。。路过
作者: mishisanyi    时间: 2015-6-8 20:08
我刚好写了一段选择排序的代码，交流一下
  1. package exam;

  3. public class SelectSort {
  4.         //选择排序的方法实现
  5.         public void sort(int[] array)
  6.         {
  7.                 int i,j;
  8.                 int length = array.length;
  9.                 int min;
  10.                 for(i = 0;i<length; i++)
  11.                 {
  12.                                 min = i;
  13.                                 for(j=i+1;j<length;j++)
  14.                                 {
  15.                                         if(array[min]>array[j])
  16.                                                 min = j;
  17.                                 }
  18.                                 if(min != i)
  19.                                 {
  20.                                         int temp = array[min];
  21.                                         array[min] = array[i];
  22.                                         array[i] = temp;
  23.                                 }
  24.                 }
  25.                 for(i = 0;i < length ; i++)
  26.                 {
  27.                         System.out.print(array[i]+",");
  28.                 }
  29.         }
  30.         public static void main(String[] args)
  31.         {
  32.                 int demoSort[] = {25,34,6,37,5,7};
  33.                 SelectSort selectSort = new SelectSort();
  34.                 selectSort.sort(demoSort);
  35.         }

  37. }
复制代码
作者: java8023    时间: 2015-6-8 23:07
mishisanyi 发表于 2015-6-8 20:08
我刚好写了一段选择排序的代码，交流一下

e还好啊，不过我想要快速排序的
作者: qian0217wei    时间: 2015-6-9 00:05
我知道算法思想！具体实现没做过！
作者: java8023    时间: 2015-6-9 09:06
qian0217wei 发表于 2015-6-9 00:05
我知道算法思想！具体实现没做过！

可以讲一讲啊，网上很多就是代码，基本没有思想和算法讲解，甚至有的连注释都没有
作者: 经济    时间: 2015-6-9 09:28
我的帖子里面有快速排序的方法，代码都有注释，你可以去看看
作者: java8023    时间: 2015-6-9 09:43
经济 发表于 2015-6-9 09:28
我的帖子里面有快速排序的方法，代码都有注释，你可以去看看

老大怎么不给个注释 ，哦链接呢
作者: forTomorrow    时间: 2015-6-9 10:37
我之前有研究过快速排序原理，现在又忘记了，大概是这样的以某一元素的“值”（一般以第一个元素的值）作为基点，从右边元素依次与这个值比较，（根据顺序原理左边小于右边）小则和那个基点元素对调，从对调后的那个元素（对调前在右边的那个元素）开始往右遍历，比基点大则和现在已经在右边的那个基点元素对调，然后再从对调后的那个元素（即现在在右边的那个元素）往左遍历（和初始时候一样了），如此循环下去，直到碰到那个基点元素！！！纯手打
作者: forTomorrow    时间: 2015-6-9 10:40
其实原理就是，顺序排序左边小于右边，倒序排序左边大于右边，小于基础点元素的“位于”（相对位置，实际操作就是交换）基础点左边，大于的放在右边
作者: meng12    时间: 2015-6-9 12:35
排序的话就是拿第0角标位的值和其他角标位的值进行比较，获取的最大或最小值放在0角标位，然后保持0角标位的值不变，在拿1角标位的值和其他角标位的值进行比较，获取的最大或最小值放在1角标位，以此类推，就可以获取有序的数组啦！
作者: 经济    时间: 2015-6-9 14:12
java8023 发表于 2015-6-9 09:43
老大怎么不给个注释 ，哦链接呢

地址：http://bbs.itheima.com/thread-200833-1-1.html
作者: java8023    时间: 2015-6-9 18:24
forTomorrow 发表于 2015-6-9 10:37
我之前有研究过快速排序原理，现在又忘记了，大概是这样的以某一元素的“值”（一般以第一个元素的值）作为 ...

我根据你的原理还是写不出来啊，没有这种能力啊
作者: java8023    时间: 2015-6-9 18:25
meng12 发表于 2015-6-9 12:35
排序的话就是拿第0角标位的值和其他角标位的值进行比较，获取的最大或最小值放在0角标位，然后保持0角标位 ...

谢谢你的回复不过你说的好像不是快速排序，是冒泡排序
作者: java8023    时间: 2015-6-9 18:27
经济 发表于 2015-6-9 14:12
地址：http://bbs.itheima.com/thread-200833-1-1.html

哦 看到你的帖子了，不过和网上的一样都是两个方法的
作者: forTomorrow    时间: 2015-6-10 08:42
java8023 发表于 2015-6-9 18:24
我根据你的原理还是写不出来啊，没有这种能力啊

那你百度参考下人家的代码吧，我记得好像百度文库里有
作者: forTomorrow    时间: 2015-6-10 14:19
我参考网上的自己写的代码：

package com.itheima;

public class QuickSortDemo {

        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] arr = { 3, 8, 6, 5, 7, 2, 9, 4, 1 };
               
                QuickSort qs = new QuickSortDemo().new QuickSort();
                qs.quickSort(arr, 0, arr.length-1);
               
                printArray(arr);

        }
       
        class QuickSort{
                int locationOfFirst(int[] arr,int left, int right){
                       
                        int base = arr[left];
                        int temp = 0;               
                        while (right > left) {
                                if (arr[right] < base) {//从右往左遍历，比基点元素的值小则交换位置
                                        swap(arr,right, left, temp);                                       
                                        left++;
                                        while (left < right) {//从左往右遍历，比基点元素大则交换位置
                                                if (arr[left] > base) {
                                                        swap(arr,left, right, temp);
                                                        break;
                                                }
                                                left++;
                                        }
                                }
                                right--;
                        }
                        return left;
                }
                void quickSort(int[]arr,int left,int right ) {//对数组中角标从left到right的元素进行排序left<right
                        if(left<right){
                                int loca = locationOfFirst(arr, left, right);//求出第一个元素（left到right范围内）的实际位置（按顺序排列后）
                                quickSort(arr,left, loca-1);//对左边比基点元素（即第一个元素）小的元素进行排序
                                quickSort(arr, loca+1, right);//对右边比基点元素大的元素进行排序
                        }
                }
        }

        public void swap(int[] arr, int index1, int index2,int temp) {// 交换数组中对应位置的元素
                temp = arr[index1];
                arr[index1]= arr[index2];
                arr[index2]= temp;
        }

        public static void printArray(int[] arr) {//打印数组元素
                for (int i = 0; i < arr.length; i++) {
                        System.out.print(arr[i] + "  ");
                }
        }

}
作者: forTomorrow    时间: 2015-6-10 14:20
忘记帖运行结果了：
1  2  3  4  5  6  7  8  9  
作者: forTomorrow    时间: 2015-6-10 14:25
其实不用定义两个参数left，right,有个临时变量记住自己的位置就行，单方向遍历就可以，不用双方向，道理一样，联想下排队的时候，假如你在第一个位置，用你去和每一个人比较身高，比你高的站后面，比你矮的站你前面，确定你的实际应该在的位置，这是第一步，这样的结果就是在你前面的都比你矮，你后面的都比你高，然后再对前面的和后面的人 分别排序确定位置



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