黑马程序员技术交流社区

标题: qiu求排序代码！参考 [打印本页]
作者: 卑微の小幸福    时间: 2013-11-23 15:24
标题: qiu求排序代码！参考
求快速排序代码参考理解。完整版！谢谢！急！
作者: 潘际昌    时间: 2013-11-23 15:37
伸手党{:soso_e148:}
作者: 潘际昌    时间: 2013-11-23 15:38
潘际昌 发表于 2013-11-23 15:37
伸手党

要什么排序？ 冒泡？选择？
作者: 卑微の小幸福    时间: 2013-11-23 16:02
hehe 谢谢 我哦弄出来了！
作者: 王贺    时间: 2013-11-23 16:07
呵呵 刚好有两个，给你参考下
//冒泡排序
        //相邻数之间比较
        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;
                                }
                        }
                }
               
               
               
        }
作者: 张天昊76    时间: 2013-11-23 16:18
快速排序java代码：
  1. public class QuickSort {

  3.         int[] arr = { 23, 54, 14, 67, 15, 35, 27 };

  5.         public QuickSort() {
  6.                 quick(arr);
  7.                 for (int i = 0; i < arr.length; i++) {
  8.                         System.out.println(arr[i]);
  9.                 }
  10.         }

  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.         }

  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.         }

  36.         public void quick(int[] arr2) {
  37.                 if (arr2.length > 0) { // 查看数组是否为空
  38.                         _quickSort(arr2, 0, arr2.length - 1);
  39.                 }
  40.         }

  42. }
复制代码
作者: hurryup    时间: 2013-11-23 16:55
算法如图所示:
快速排序算法的实现依赖于按照枢轴元素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 {

  3. public static void main(String[] args) {

  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. }

  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. }

  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. }

  46. }
复制代码


快排.PNG (59.26 KB, 下载次数: 7)

快排.PNG




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