黑马程序员技术交流社区

标题: 数据结构：用数组实现快速排序算法（已优化） [打印本页]

---

作者: 棉/mg花/x糖    时间: 2013-5-26 18:35
标题: 数据结构：用数组实现快速排序算法（已优化）


数据结构：用数组实现快速排序算法（已优化）

注意：算法优化不是很理想，希望哪位大神能继续帮着优化！！谢谢^_^

程序源码如下：

1. package com.yb.ArrayAndString;
   
2. 
   
3. import java.io.BufferedReader;
   
4. import java.io.IOException;
   
5. import java.io.InputStreamReader;
   
6. 
   
7. public class QuickSort {
   
8.     static int count = 0;
   
9.     int partition(int arr[],int i,int j) {                //划分区间
   
10.         int temp = arr[i];
    
11.         while(i < j) {
    
12.             while(i<j && arr[j]>temp) j--;                //从第j所指位置起向前搜索
    
13.             if(i < j) {
    
14.                 arr[i] = arr[j];
    
15.                 i++;
    
16.             }
    
17.             while(i<j && arr[i]<temp) i++;                //从第i所指位置起向后搜索
    
18.             if(i < j) {
    
19.                 arr[j] = arr[i];
    
20.                 j--;
    
21.             }
    
22.         }
    
23.         arr[i] = temp;
    
24.         return i;
    
25.     }
    
26.     void quickSort(int arr[],int low,int high) {          //快速排序方法
    
27.         int p;
    
28.         if(low < high) {
    
29.             p = partition(arr,low,high);                  //做一次划分排序
    
30.             quickSort(arr,low,p-1);                       //左区间递归
    
31.             quickSort(arr,p+1,high);                      //右区间递归
    
32.             count++;
    
33.         }
    
34.     }
    
35. 
    
36.     public static void main(String[] args) throws IOException {
    
37.         // TODO Auto-generated method stub
    
38.         BufferedReader keyin = new BufferedReader(new InputStreamReader(System.in));
    
39.         String ch;
    
40.         int arr[] = new int[8];
    
41.         int len = arr.length;
    
42.         System.out.println("请从键盘输入8个整数，一行只输入一个数：");
    
43.         for(int i = 0; i < len; i++) {
    
44.             ch = keyin.readLine();                         //用于读取一个字符串
    
45.             arr[i] = Integer.parseInt(ch);                 //将字符串类型ch转换成整数类型
    
46.         }
    
47. 
    
48.         //打印原始数据
    
49.         System.out.println("原始数据：");
    
50.         for(int i = 0; i < len; i++) {
    
51.             System.out.print(" "+arr[i]);
    
52.         }
    
53.         System.out.println("\n");
    
54. 
    
55.         QuickSort p = new QuickSort();
    
56.         p.quickSort(arr,0,len-1);
    
57. 
    
58.         //打印排序结果
    
59.         System.out.println("快速排序法的结果：");
    
60.         for(int i = 0; i < len; i++) {
    
61.             System.out.print(" "+arr[i]);
    
62.         }
    
63.         System.out.println("\n");
    
64.         System.out.println("排序趟数："+count);
    
65.     }
    
66. }
    

复制代码

运行结果：

---

作者: 赵崇友    时间: 2013-5-26 22:46
整体的逻辑没有问题，具体的细节可以多想想各种可能出现不正常的情况如何进行处理。。。

---

作者: 棉/mg花/x糖    时间: 2013-5-26 22:49

赵崇友 发表于 2013-5-26 22:46
整体的逻辑没有问题，具体的细节可以多想想各种可能出现不正常的情况如何进行处理。。。 ...

是哦，不过我现在还一下子想不到，你有没好的idea啊，参考参考啊.........

目前能力有限，异常情况的处理也不是很好.......想不到太深

---

作者: 赵崇友    时间: 2013-5-26 23:00
另外把工具类和测试类分开写比较好些，工具类中的方法最好是定义成静态的。处理异常时， 在给用户用时要考虑各种情况的出现并给出有好提示。比如：用户输入的不是数字、输入的数字不是整数等各种情况。

---

作者: 赵崇友    时间: 2013-5-26 23:12

棉/mg花/x糖 发表于 2013-5-26 22:49
是哦，不过我现在还一下子想不到，你有没好的idea啊，参考参考啊.........

目前能力有限，异常情况的处 ...

不知道你流程走完了没有，这个代码优化以后会讲到的。。别太在意，主要是逻辑清晰就ok了。。

---

作者: 棉/mg花/x糖    时间: 2013-5-27 09:58

赵崇友 发表于 2013-5-26 23:12
不知道你流程走完了没有，这个代码优化以后会讲到的。。别太在意，主要是逻辑清晰就ok了。。 ...

嗯，很不错的建议呀，谢谢了哈。你的流程是不是走完了啊？
我还不行，只走了一半啊，只得准备21期了~~~~~

---

作者: 赵崇友    时间: 2013-5-27 13:36

棉/mg花/x糖 发表于 2013-5-27 09:58
嗯，很不错的建议呀，谢谢了哈。你的流程是不是走完了啊？
我还不行，只走了一半啊，只得准备21期了~~~~~ ...

嗯嗯，我申请的20期的，流程走完了！！你要好好努力呀，早点准备21期的，早点面试，不要拖到最后，不然很可能最后没有名额了，又呆等下一期了！！

---

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

黑马程序员IT技术论坛 X3.2