求快速排序代码参考理解。完整版！谢谢！急！

伸手党{:soso_e148:}

潘际昌 发表于 2013-11-23 15:37
伸手党

要什么排序？ 冒泡？选择？

hehe 谢谢 我哦弄出来了！

呵呵 刚好有两个，给你参考下
//冒泡排序
        //相邻数之间比较
        public static void Sort1(int[] items)
        {
                for(int i=0; i<items.length-1; i++)
                {                                                                       
                        for(int j=0; j<items.length-i-1; j++)//-i:让每一次比较的元素减少，-1：避免角标越界。
                        {
                                if(items[j]<=items[j+1])
                                {
                                       
                                        int temp = items[j];
                                        items[j] = items[j+1];
                                        items[j+1] = temp;
                                       
                                }
                        }
                }
               
               
        }
        //选择排序
        //每个数和其他数都比较一边
        public static void Sort2(int[] items)
        {
               
                for(int i=0;i<items.length-1;i++)
                {
                        for(int j=i+1;j<items.length;j++)
                        {
                               
                                if(items[i]>=items[j])
                                {
                                         int temp=items[j];
                                        items[j]=items[i];
                                        items[i]=temp;
                                }
                        }
                }
               
               
               
        }

快速排序java代码：

1. public class QuickSort {
   
2. 
   
3.         int[] arr = { 23, 54, 14, 67, 15, 35, 27 };
   
4. 
   
5.         public QuickSort() {
   
6.                 quick(arr);
   
7.                 for (int i = 0; i < arr.length; i++) {
   
8.                         System.out.println(arr[i]);
   
9.                 }
   
10.         }
    
11. 
    
12.         public int getMiddle(int[] list, int low, int high) {
    
13.                 int tmp = list[low]; // 数组的第一个作为中轴
    
14.                 while (low < high) {
    
15.                         while (low < high && list[high] >= tmp) {
    
16.                                 high--;
    
17.                         }
    
18.                         list[low] = list[high]; // 比中轴小的纪录移到低端
    
19.                         while (low < high && list[low] <= tmp) {
    
20.                                 low++;
    
21.                         }
    
22.                         list[high] = list[low]; // 比中轴大的纪录移到高端
    
23.                 }
    
24.                 list[low] = tmp; // 中轴纪录到尾
    
25.                 return low; // 返回中轴的位置
    
26.         }
    
27. 
    
28.         public void _quickSort(int[] list, int low, int high) {
    
29.                 if (low < high) {
    
30.                         int middle = getMiddle(list, low, high); // 将list数组进行一分为二
    
31.                         _quickSort(list, low, middle - 1); // 对低字表进行排序递归排序
    
32.                         _quickSort(list, middle + 1, high); // 对高字表进行排序递归排序
    
33.                 }
    
34.         }
    
35. 
    
36.         public void quick(int[] arr2) {
    
37.                 if (arr2.length > 0) { // 查看数组是否为空
    
38.                         _quickSort(arr2, 0, arr2.length - 1);
    
39.                 }
    
40.         }
    
41. 
    
42. }

复制代码

算法如图所示:
快速排序算法的实现依赖于按照枢轴元素x对待排序序列进行划分的过程。
  对待排序序列进行划分的做法是:使用两个指针low和high分别指向待划分序列arr的范围
,取low所指向元素为枢轴,即int key=arr[low].划分首先从high所指向位置的元素起向前
逐一搜索到第一个比key小的元素,并将其设置到low所指的位置:然后从low所指位置的
元素起向后逐一搜索到第一个比key大的元素,并将其设置到high所指的位置;不断重复上述
两步直到low=high为止,最后将key设置到low与high共同指向的位置。
  使用上述划分方法即可将待排序序列按枢轴元素key分成两个子序列,当然key的选择不一定
必须是arr[low],而可以是arr[low..high]之间的任何数据元素。
具体代码如下：

1. public class TestSort {
   
2. 
   
3. public static void main(String[] args) {
   
4. 
   
5. QuickSort qs=new QuickSort();
   
6. int arr1[]={44,22,2,32,54,22,88,77,99,11};
   
7. qs.arr1=arr1;
   
8. qs.sort(0,qs.arr1.length-1);
   
9. qs.printArray();
   
10. }
    
11. 
    
12. }
    
13. //输入：数据元素数组arr，划分序列区间[low-high]
    
14. //输出:将序列划分为两个子序列并返回枢轴元素key的位置
    
15. class QuickSort{//算法partition实现了一次划分的过程。
    
16. public int arr1[];
    
17. private int partition(int[] arr,int low,int high){
    
18. int key=arr[low];//使用arr[low]作为枢轴元素
    
19. while(low<high){//从两端交替向内扫描
    
20. while(low<high && arr[high]>=key)
    
21. high--;
    
22. arr[low]=arr[high];//将比key小的元素移向低端
    
23. while(low<high && arr[low]<=key)
    
24. low++;
    
25. arr[high]=arr[low];//将比key大的元素移向高端
    
26. }
    
27. arr[low]=key;//设置枢轴
    
28. return low; //返回枢轴元素位置
    
29. }
    
30. 
    
31. //在划分算法的基础上,快速排序算法的递归实现如算法sort所示
    
32. //输入：数据元素数组arr1，数组arr1的待排序区间[low-high]
    
33. //输出:数组arr1以关键字有序
    
34. public void sort(int low,int high){
    
35. if(low<high){
    
36. int result=partition(arr1,low,high);
    
37. sort(low,result-1);
    
38. sort(result+1,high);
    
39. }
    
40. }
    
41. public void printArray(){
    
42. for(int i=0;i<=arr1.length-1;i++)
    
43. System.out.print(arr1[i]+" ");
    
44. }
    
45. 
    
46. }

复制代码