黑马程序员技术交流社区

标题: 快速排序法 [打印本页]

作者: 唐见 时间: 2012-8-25 10:16
标题: 快速排序法
一直没弄明白java中快速排序法的逻辑原理。我看百度，越看越糊涂，谁能尽量简单的解释下

作者: 黑马杨晨 时间: 2012-8-25 11:52
这是我在网上看到的一篇文章，看能否帮到你！
快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。最坏情况的时间复杂度为O(n2)，最好情况时间复杂度为O(nlog2n)。

另外 java没指针概念可以认为是句柄
假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一趟快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

               A[1] A[2] A[3] A[4] A[5]    A[6] A[7]：

                  49    38    65    97    76    13    27

进行第一次交换后： 27    38    65    97    76    13    49

               ( 按照算法的第三步从后面开始找)

进行第二次交换后： 27    38    49    97    76    13    65

               ( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27    38    13    97    76    49    65

( 按照算法的第五步将又一次执行算法的第三步从后开始找)

进行第四次交换后： 27    38    13    49    76    97    65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

   此时再执行第三步的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27    38    13    49    76    97    65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

   快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态                      {49 38 65 97 76 13 27}

进行一次快速排序之后划分为    {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

                           结束       结束 {49 65} 76 {97}

                                                49 {65}       结束

                                                   结束

//下面是一个示例,哪位给说说快速排序法的原理,下面的示例中指针和上下标移动我看不太懂,
public class QuickSort {
/**主方法*/
public static void main(String[] args) {
//声明数组
int[] nums = {27, 8, 57, 9, 23, 41, 65, 19, 0, 1, 2, 4, 5};
//应用快速排序方法
quickSort(nums, 0, nums.length-1);
//显示排序后的数组
for(int i = 0; i < nums.length; ++i) {
   System.out.print(nums[i] + ",");
}
System.out.println("");
}

/**快速排序方法*/
public static void quickSort(int[] a, int lo0, int hi0) {
int lo = lo0;
int hi = hi0;

if (lo >= hi)
   return;

//确定指针方向的逻辑变量
boolean transfer=true;

while (lo != hi) {
   if (a[lo] > a[hi]) {
      //交换数字
      int temp = a[lo];
      a[lo] = a[hi];
      a[hi] = temp;
      //决定下标移动，还是上标移动
      transfer = (transfer == true) ? false : true;
   }

   //将指针向前或者向后移动
   if(transfer)
      hi--;
   else
      lo++;

   //显示每一次指针移动的数组数字的变化
   /*for(int i = 0; i < a.length; ++i) {
      System.out.print(a[i] + ",");
   }
   System.out.print(" (lo,hi) = " + "(" + lo + "," + hi + ")");
   System.out.println("");*/
}

//将数组分开两半，确定每个数字的正确位置
lo--;
hi++;
quickSort(a, lo0, lo);
quickSort(a, hi, hi0);
}
}

作者: 刘源 时间: 2012-8-25 12:09
class QuickSort {
public void quickSort(String[] strDate,int left,int right){//数组，左角标，右角标。
  String middle,tempDate;//中间角标，和交换时的中间变量。
  int i,j;
  i=left;
  j=right;
  middle=strDate[(i+j)/2];//中间角标
  do{//将比中间值小的放左边，比中间值大的放右边
while(strDate.compareTo(middle)<0&& i<right)
i++; //找出左边比中间值大的数
while(strDate[j].compareTo(middle)>0&& j>left)
j--; //找出右边比中间值小的数
if(i<=j){ //将左边大的数和右边小的数进行替换
tempDate=strDate;
strDate=strDate[j];
strDate[j]=tempDate;i++;j--;
}
  }
  while(i<=j);
  //当两者交错时停止
  if(i<right){//将到right再次进行递归。直到每次得到排序的最大值。
quickSort(strDate,i,right);
  }
  if(j>left){//将left到j再次进行递归。直到每次得到排序的最小值。
quickSort(strDate,left,j);
  }
}
//因为是用递归法，而且一次两边一起排，所以效率很高。但如果数太多了，就会出问题。
public static void main(String[] args){
  String[] strVoid=new String[]{"11","66","22","0","55","22","0","32"};
  QuickSort sort=new QuickSort();
  sort.quickSort(strVoid,0,strVoid.length-1);
  for(int i=0;i<strVoid.length;i++){
System.out.println(strVoid+" ");
  }
}
}
希望对你有帮助。

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