黑马程序员技术交流社区

标题: 有大神懂快速排序的吗？ [打印本页]

作者: 深井看海 时间: 2012-11-29 23:59
标题: 有大神懂快速排序的吗？
排序有很多种，冒泡和选择知道了,但不知道快速排序是怎么样拍的，思路是怎么样的啊？另能附上代码讲解最好！

作者: 乔叶旭 时间: 2012-11-30 00:03
所谓快速排序法是从待排序的数组中找一个标本作为分界值（一般是数组的第一个元素），所有比这个值小的值放到它的左边（或者右边），将比它大的值放到它的右边（或者左边），这样这个分界值左右两边的值要么全部比它大，要么全部比它小。之后再利用递归，将此标本右边、左边的所有元素也按部就班。算法如下
package sort;

import java.util.Arrays;

/**
* 快速排序
*
* @author liuyan
*/
public class QuickSort {

/**
   * 交换数组元素位置
   *
   * @param datas
   * @param i
   * @param j
   */
public static void chang(Integer[] datas, int i, int j) {
Integer temp = datas[i];
datas[i] = datas[j];
datas[j] = temp;

}

/**
   * 快速排序法
   *
   * @param datas
   * @param startIndex
   * @param endIndex
   */
public static void quickSort(Integer[] datas, int startIndex, int endIndex) {

if (startIndex < endIndex) {

//标本
Integer startData = datas[startIndex];

//左边的开始索引
int i = startIndex;

//右边的开始索引
int j = endIndex + 1;
while (true) {

//找左边比标本大的下标
while (i < endIndex && datas[++i] > startData){
}

//找右边比标本小的下标
while (j > startIndex && datas[--j] < startData){
}

if (i < j) {

//交换i、j元素位置
chang(datas, i, j);
} else {
break;
}
}

//交换开始位置、j的元素为止
chang(datas, startIndex, j);

//递归标本左边
quickSort(datas, startIndex, j - 1);

//递归标本右边
quickSort(datas, j + 1, endIndex);
}

}
}

作者: 刘腾 时间: 2012-11-30 01:31
总结的比较好的一个帖子，内有代码与详细讲解
http://bbs.itheima.com/forum.php ... F%E6%8E%92%E5%BA%8F

作者: 冯盼 时间: 2012-11-30 02:08
快速排序实际上就是不断的给数组分组，一组为大数，一组为小数，并且两边分别递归。最终递归完成，排序成功。

作者: 孙玉伟 时间: 2012-11-30 12:55
快速排序是对冒泡排序的改进。他的思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
例子：
   public class Test2
{

/**
   *  JAVA排序算法实现代码快速排序。
   */
public static int[] a = { 5, 7, 12, 0, 4, 3 }; // 预设数据数组

   public static void main(String args[]) {

      System.out.print("快速排序前: ");
      for (int i = 0; i < a.length; i++)
      System.out.printf("%3s",a[i]);

      System.out.println("");

      int Index = a.length;

      Quicksort(0, Index - 1, Index); // 快速排序

      // 排序后结果
      System.out.print("快速排序后: ");
      for (int i = 0; i < a.length; i++)
      System.out.printf("%3s", a[i]);

      System.out.println("");
   }

   public static void Quicksort(int Left, int Right, int Index) {
      int i, j, k; // 循环计数变量
      int Pivot; // 枢纽变量
      int Temp; // 暂存变量

      i = Left; // 设定左指针
      j = Right; // 设定右指针

      Pivot = a[Left]; // 取最左边的元素

      if (i < j) {
      do {
         while (a[i] <Pivot && i < Right) // 从左往右找比Pivot大的值
         {
            i++;
         }
         while (a[j] > Pivot && j > Left) // 从右往左找比Pivot小的值
         {
            j--;
         }

         if (i < j) // 交换a[i]和a[j]
         {
            Temp = a[i];
            a[i] = a[j];
            a[j] = Temp;
         }
      } while (i < j);
      if (i > j) {
         Temp = a[Left]; // 交换a[Left]和a[j]
         a[Left] = a[j];
         a[j] = Temp;

         // 打印目前排序结果

         System.out.print("排序中: ");
         for (k = 0; k <= Index; k++) {
            System.out.printf("%3s", a[k]);
         }
         System.out.println("");
      }
      Quicksort(Left, j - 1, Index); // 排序左半边
      Quicksort(j + 1, Right, Index); // 排序右半边
      }
   }

}

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

黑马程序员IT技术论坛 X3.2