黑马程序员技术交流社区

标题: 分享，Java快速排序算法的实现 [打印本页]
作者: heshiwei    时间: 2015-10-7 16:17
标题: 分享，Java快速排序算法的实现
（1）基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
  1. publicclass quickSort {

  3.   inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
  4. publicquickSort(){
  5.     quick(a);
  6.     for(int i=0;i<a.length;i++){
  7.        System.out.println(a[i]);
  8.     }
  9. }
  10. publicint getMiddle(int[] list, int low, int high) {  
  11.             int tmp =list[low];    //数组的第一个作为中轴  
  12.             while (low < high){  
  13.                 while (low < high&& list[high] >= tmp) {  
  14.                    high--;  
  15.                 }  

  17.                 list[low] =list[high];   //比中轴小的记录移到低端  
  18.                 while (low < high&& list[low] <= tmp) {  
  19.                     low++;  
  20.                 }  

  22.                 list[high] =list[low];   //比中轴大的记录移到高端  
  23.             }  
  24.            list[low] = tmp;              //中轴记录到尾  
  25.             return low;                   //返回中轴的位置  
  26. }

  28. publicvoid _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. publicvoid quick(int[] a2) {  
  37.             if (a2.length > 0) {    //查看数组是否为空  
  38.                 _quickSort(a2,0, a2.length - 1);  
  39.             }  
  40. }
  41. }
复制代码






1347009479_6587.jpg (83.34 KB, 下载次数: 5)

1347009479_6587.jpg
作者: 920792433    时间: 2015-10-7 18:06
额   吼吼~~~~
作者: 斯文阿昊    时间: 2015-10-7 21:18
第一次见,容我想想
作者: heshiwei    时间: 2015-10-7 21:38
斯文阿昊 发表于 2015-10-7 21:18
第一次见,容我想想

推荐两个快排算法的动画演示，帮助理解。
作者: 迷茫不堪的年纪    时间: 2015-10-8 01:37
说实话， 看完 闷闷哒。 主要是哪里的知识点？ 原理是什么啊？这样不是成折半了么？  还有publicvoid quick(int[] a2) 类似语句，应该public  void quick(int[] a2)吧？    publicvoid 感觉有点不习惯哈。
作者: Synaric    时间: 2015-10-8 08:49
最大数放第一个，那LZ的代码可能越界？
作者: Synaric    时间: 2015-10-8 08:50
Synaric 发表于 2015-10-8 08:49
最大数放第一个，那LZ的代码可能越界？

仔细看了下，并不会。。



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