关于几种经典的排序算法，选择排序还有冒泡排序都很好理解，但是这两种排序效率不高，而插入排序在一般只有数据量小的时候具有高效率。快速排序是相对高效的排序算法，我知道思想，但是不知道具体怎么实现，研究了好半天后终于整出来了，求大神们指正

1. /*关于快速排序:
   
2. 步骤：
   
3. 1、选择一个标准元素
   
4. 2、使用该标准元素分割数组，使得比该元素小的元素在它的左边，比它大的在右边。
   
5. 3、根据标准元素最后确定的位置，把数组分成三部分，左边的，右边的，标准元素自己，
   
6.         然后再对左边的和右边的分别递归调用快速排序算法即可。  
   
7. */
   
8. 
   
9. 
   
10. class QuickSort
    
11. {
    
12.         public static void main(String[] args)
    
13.         {
    
14.                 int [] arr = new int [] {43,8,12,4,98,43,25,65,44,26,33,2,9,38,66,17};
    
15.                 Sort(arr,0,arr.length-1);
    
16.                 sopArray(arr);
    
17.         }
    
18.         public static void Sort(int [] arr, int mid ,int end)
    
19.         {
    
20.                 int x= mid,y= end; //记录最开始接收的数组的头和尾
    
21.                 if (mid == end)
    
22.                         return;
    
23.                 int start = mid+1;//从start开始逐个与标准值比较(我取的标准值为这一段的最低位)
    
24.                 while (start<=end)
    
25.                 {
    
26.                         //若arr[start]<arr[min]，则把小于标准值的移到左边，mid，start自增
    
27.                         if(arr[start]<arr[mid])
    
28.                         {
    
29.                                 trans(arr,start,mid);//换位
    
30.                                 mid++;
    
31.                                 start++;
    
32.                         }
    
33.                         //否则则把大于等于标准值的值移到尾端，end自减
    
34.                         else
    
35.                         {
    
36.                                 trans(arr,start,end);
    
37.                                 end--;
    
38.                         }
    
39.                         //以刚开始接收的数组的头作为头，以mid-1作为尾，对小于arr[mid]的这段数组进行快速排序
    
40.                         Sort(arr,x,mid-1);
    
41.                         //以mid+1作为头，以刚开始接受的数组的尾作为尾，对大于arr[mid]的这段数组进行快速排序
    
42.                         Sort(arr,mid+1,y);
    
43.                 }
    
44.         }
    
45.         public  static void sopArray(int [] arr)//打印数组
    
46.         {
    
47.                 for (int i=0 ;i<arr.length ;i++ )
    
48.                 {
    
49.                         System.out.print(arr[i]+" ");
    
50.                 }
    
51.                 System.out.println();
    
52.         }
    
53.         public static void trans(int[] arr,int x, int y)//换位
    
54.         {
    
55.                 int temp = arr[x];
    
56.                 arr[x] = arr[y];
    
57.                 arr[y] = temp;
    
58.         }
    
59. }
    

复制代码

看看先，

我还没学到排序呢，看得不是很明白

你这个不是快速排序。。。快速排序、归并排序等等复杂度为O(NLogN)的算法的思想是每次递归把要解决的问题的规模减半。而你的程序是每换位一个数就进行递归，等于是每次只把问题的规模减1 。。。我试了一下让你的程序排5000个数，5分钟过去了，还没排完。实际上，你的程序比冒泡还慢，排20个数就要6秒，我估计时间复杂度是指数级别。。。

写的太复杂了，要用到递归的思想

fantacyleo 发表于 2014-8-20 14:57
你这个不是快速排序。。。快速排序、归并排序等等复杂度为O(NLogN)的算法的思想是每次递归把要解决的问题的 ...

{:3_50:}还没搞明白，我再去研究研究

男人你得有范 发表于 2014-8-20 15:32
写的太复杂了，要用到递归的思想

{:3_49:}嗯，好像还没到点上，有没有大神给详细讲下

以前写的，有注释      

1. private static void quickSort(int[] arr, int left, int right) {
   
2.                 int l,r; //左右哨兵 ，l为左哨兵位置，r为右哨兵位置
   
3.                 int baseNum; //存储基准数
   
4.                
   
5.                 if(left > right)
   
6.                         return;
   
7.                
   
8.                 baseNum = arr[left]; //第一次基准数默认为数组首位
   
9.                 l = left;  //左哨兵从左边出发扫描
   
10.                 r = right; //右哨兵从右边出发扫描
    
11.                
    
12.                 while(l != r) {
    
13.                         //先从右边开始往左扫描,找到第一个比基准数小的
    
14.                         while(arr[r] >= baseNum && l < r)
    
15.                                 r--;
    
16.                         //再从左边开始往右扫描,找到第一个比基准数大的
    
17.                         while(arr[l] <= baseNum && l < r)
    
18.                                 l++;
    
19.                         //交换两个数位置
    
20.                         if(l < r) {
    
21.                                 int temp = arr[l];
    
22.                                 arr[l] = arr[r];
    
23.                                 arr[r] = temp;
    
24.                         }
    
25.                 }
    
26.                
    
27.                 //基准数归位
    
28.                 arr[left] = arr[l];
    
29.                 arr[l] = baseNum;
    
30.                
    
31.                 //递归处理左边
    
32.                 quickSort(arr, left, l - 1);
    
33.                 //递归处理右边
    
34.                 quickSort(arr, l + 1, right);
    
35.         }

复制代码

单线程xia 发表于 2014-8-21 01:31
以前写的，有注释

谢谢，有点懂了

你的快速排序跟我原来看到的不太一样，我也不知道两个，哪个是真的快速排序。

第一感觉就不是快速排序  看着蛮复杂的 没太看懂

运算效率和代码的简单就像鱼和熊掌，不可兼得~~