黑马程序员技术交流社区

标题: 快速排序哪位大神讲解一下 [打印本页]

作者: 吴海松    时间: 2014-12-26 20:12
标题: 快速排序哪位大神讲解一下
听说快速排序是排序最快的一种,哪位大神说说怎么搞啦
作者: 史云龙    时间: 2014-12-26 20:19
设置两个变量i,j,排序开始的时候,i=0,j=length-1.
以第i个数组元素作为关键数据,赋值给key,用于比较。
从j开始向前搜索,即由后向前搜索(j--),找到第一个小于key的值[j],将[j]和位置的值进行互换。
从i开始向后搜索,即有开始向后搜索(i++),找到第一个比key小的值,将和[j]位置的值进行互换。
直到i>j循环结束。
对左侧(0,i-1)进行循环排序。
对左侧(j+1,length-1)进行循环排序。
  1. package com.demo.test;


  2. /**
  3. * @author 史云龙
  4. * 完成数组的快速排序
  5. * 数组【100,40,60,87,34,11,56,0】
  6. *快速排序:
  7. *从小到大排列
  8. */
  9. public class QuickSort {
  10.        
  11.         /**
  12.          * @param args
  13.          * 主函数
  14.          */
  15.         public static void main(String[] args) {
  16.                
  17.                 int[] array = {100,40,60,87,34,11,56,0};
  18.                 sop("未进行快速排序的数组:");
  19.                 print(array);
  20.                 sop("已经进行快速排序的数组:");
  21.                 sort(array,0,array.length-1);
  22.                 print(array);
  23.         }
  24.        
  25.         /**
  26.          * @param array【需要排序的数组】
  27.          * @param low【最低位】
  28.          * @param high【最高位】
  29.          * 快速排序[从小到大排序]
  30.          * 算法说明:
  31.          *         1、设置两个变量,low,high,初始排序时,low=0,high=array.length-1;
  32.          *                         第6步中,由于需要对分成的两部分数组继续进行排序,
  33.          *                         需要定义两个变化的值来分别初始low和high,这里定义为l、h;
  34.          * 2、以第l个数组元素作为关键数据,赋值给key,即key=array[l]
  35.          * 3、从h开始向前搜索,即由后向前搜索,找到第一个小于key的值array[h],
  36.          *                 将array[h]和array[l]互换,此后key为array[h]
  37.          * 4、从l开始向后搜索,即由前向后搜索,找到第一个大于key的值array[l],
  38.          *                 将array[l]和array[h]互换,此后key为array[l]
  39.          * 5、第一次排序结束后,如果l<h,则重复第3、4两步。
  40.          * 6、如果l>h是排序结束,左侧即【low----l】不一定是符合顺序的,则对左侧排序。
  41.          *                 同时右侧【h----high】也不一定是符合顺序的,则对左侧进行排序的
  42.          *                 由于此时l>=h,对左侧排序时将l进行-1,
  43.          *                 对右侧进行排序时,将h进行+1,保证不会重复。
  44.          *                 (1)l>h即l=h+1,不可能有其他情况,因为l=h+1时,循环已经结束。
  45.          *                 从新开始的排序的两段数组顺序可以看做为【low-h】【l-high】,完全包含这个数组。
  46.          *                 (2)l=h,
  47.          *                 从新开始的排序的两段数组顺序可以看做为【low-l-1】【l=h】【h+1-high】,完全包含这个数组。
  48.          *                 此时array[l]==array[h]大于左侧的数据,小于右侧的数据,可以不用重新排序。
  49.          *                
  50.          *
  51.          */
  52.         public static void sort(int[] array ,int low,int high){
  53.                 //如果最小位置大于最大位置,直接返回。
  54.                 if(low>=high)
  55.                         return;
  56.                 if((high-low)==1){
  57.                         if(array[low]>array[high]){
  58.                                 swap(array,low,high);
  59.                         }
  60.                         return;
  61.                 }
  62.                 //默认排序的KEY值
  63.                 int key = array[low];
  64.                 //将最低值赋给一个变量,用于一次排序后进行后续排序分组
  65.                 int l = low;
  66.                 //将最高值赋给一个变量,作用同上
  67.                 int h=high;
  68.                 //如果l<h,则一直进行循环
  69.                 while(l<h){
  70.                         //从最后向前找,找到比key小的第一个数
  71.                         //如果l<h,且key比array[h]小,则一直循环
  72.                         //直到h小于等于l或此时h处的值比key小,则结束循环
  73.                         //找到比key小的值向前移动
  74.                         while(l<h&&key<array[h])
  75.                                 h--;
  76.                         /*
  77.                          与上述两行代码相同
  78.                         while(l<h){
  79.                                 if(array[h]<key)
  80.                                         break;
  81.                                 h--;
  82.                         }
  83.                         */
  84.                         //交换l和h处位置的数据,key则是array[l],交换,
  85.                         //然后key就和array[h]相等,及此时key变换为array[h]
  86.                         //交换的目的是将小点的数向前方移动
  87.                         swap(array,l,h);
  88.                         //从前向后找,找到比key(即array[h])大的数
  89.                         //如果l<h,且key(array[h])比array[l]大,则一直循环
  90.                         //直到l大于等于h或此时l出的值比key大,则结束循环
  91.                         //找到比key大的值向后移动
  92.                         while(l<h&&key>array[l]){
  93.                                 l++;
  94.                         }
  95.                         /*
  96.                          与上述两行代码相同
  97.                         while(l<h){
  98.                                 if(array[l]>key)
  99.                                         break;
  100.                                 l++;
  101.                         }
  102.                         */
  103.                         //交换l和h处位置的数据,key则是array[h],交换,
  104.                         //然后key就和array[l]相等,及此时key变换为array[l]
  105.                         //交换的目的是将小点的数向前方移动
  106.                         swap(array,l,h);
  107.                 }
  108.                 //对数组的两部分继续排序
  109.                 sort(array,low,l-1);
  110.                 sort(array,h+1,high);

  111.         }
  112.         /**
  113.          * @param b【传入数组并进行打印】
  114.          */
  115.         public static void print(int[] b){
  116.                 for (int i=0;i<b.length;i++){
  117.                         sop(b[i]);
  118.                         if(i==b.length-1){
  119.                                 sop("\n");
  120.                         }else{
  121.                                 sop(" , ");
  122.                         }
  123.                 }
  124.                
  125.         }

  126.         /**
  127.          * @param array
  128.          * @param i
  129.          * @param j
  130.          * 将符合条件的数组数据交换位置
  131.          */
  132.         public static void swap(int[] array,int i,int j){
  133.                 int temp = array[i];
  134.                 array[i]=array[j];
  135.                 array[j]=temp;
  136.                
  137.         }
  138.         /**
  139.          * @param obj[将obj输出]
  140.          */
  141.         public static void  sop(Object obj){
  142.                 System.out.print(obj);
  143.         }
  144. }
复制代码


作者: c91764000    时间: 2014-12-26 21:01
跟着学习一下!
作者: 红楼    时间: 2014-12-26 21:43
Arrays.sort




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