黑马程序员技术交流社区

标题: 数组中快速排序的问题 [打印本页]
作者: 我手心里的宝    时间: 2013-4-15 14:34
标题: 数组中快速排序的问题
在网上搜了很多答案，但是还是不明白什么是快速排序？求大神帮忙详细讲解一下快速排序，并给个代码
作者: 田瑞朋    时间: 2013-4-15 15:12
快速排序是对普通排序的改进：
下面是稳定的快速排序，C语言版
int cmp(const void *x, const void *y)
{
        if((*(node *)x).a==(*(node *)y).a)
                return (*(node *)x).id>(*(node *)y).id?1:-1;
        else
                return (*(node *)x).a<(*(node *)y).a?1:-1;
}
作者: 何俊森    时间: 2013-4-15 15:46
本帖最后由 何俊森 于 2013-4-15 15:50 编辑

快速排序（Quicksort）是对冒泡排序的一种改进。
  1. import java.util.Arrays;

  3. public class QuickSort {
  4.         public static void main(String[] ary) {
  5.                 int[] arry = { 49, 38, 65, 97, 76, 13, 27 };
  6.                 sort(arry, 0, arry.length - 1);
  7.         }

  9.         /**
  10.          * 一次排序单元，完成此方法，key左边都比key小，key右边都比key大。
  11.          *
  12.          * @param array
  13.          *            排序数组
  14.          * @param low
  15.          *            排序起始位置
  16.          * @param high
  17.          *            排序结束位置
  18.          * @return 单元排序后的数组
  19.          */
  20.         private static int sortUnit(int[] array, int low, int high) {
  21.                 int key = array[low];
  22.                 while (low < high) {
  23.                         // 从后向前搜索比key小的值
  24.                         while (array[high] >= key && high > low)
  25.                                 --high;
  26.                         // 比key小的放左边
  27.                         array[low] = array[high];
  28.                         // 从前向后搜索比key大的值，比key大的放右边
  29.                         while (array[low] <= key && high > low)
  30.                                 ++low;
  31.                         // 比key大的放右边
  32.                         array[high] = array[low];
  33.                         System.out.println(low + "," + high);
  34.                 }
  35.                 // 左边都比key小，右边都比key大。将key放在游标当前位置。此时low等于high
  36.                 array[high] = key;
  37.                 System.out.println(Arrays.toString(array));
  38.                 return high;
  39.         }

  41.         /**
  42.          * 快速排序
  43.          *
  44.          * @param arry
  45.          * @return
  46.          */
  47.         public static void sort(int[] array, int low, int high) {
  48.                 if (low >= high) {
  49.                         return;
  50.                 }
  51.                 // 完成一次单元排序
  52.                 int index = sortUnit(array, low, high);
  53.                 // 对左边单元进行排序
  54.                 sort(array, low, index - 1);
  55.                 // 对右边单元进行排序
  56.                 sort(array, index + 1, high);
  57.         }
  58. }
复制代码
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索（j -- ），找到第一个小于key的值A[j]，A与A[j]交换；
4）从i开始向后搜索，即由前开始向后搜索（i ++ ），找到第一个大于key的A，A与A[j]交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。）
示例
待排序的数组A的值分别是：（初始关键数据：key=49） 注意关键key永远不变，永远是和key进行比较，无论在什么位置，最后的目的就是把key放在中间，小的放前面大的放后面。

进行第一次交换后：27 38 65 97 76 13 49
( 按照算法的第三步从后面开始找，此时:J=6）
进行第二次交换后：27 38 49 97 76 13 65
( 按照算法的第四步从前面开始找>key的值，65>49,两者交换，此时：I=2 )
进行第三次交换后：27 38 13 97 76 49 65
( 按照算法的第五步将又一次执行算法的第三步从后开始找
进行第四次交换后：27 38 13 49 76 97 65
( 按照算法的第四步从前面开始找大于key的值，97>49，两者交换，此时：I=3,J=5 )
此时再执行第三步的时候就发现I=J=3，从而结束一趟快速排序，那么经过一趟快速排序之后的结果是：27 38 13 49 76 97 65，即所有大于key49的数全部在49的后面，所有小于key（49）的数全部在key（49）的前面。
还要不懂可以参考这个舞蹈。http://v.youku.com/v_show/id_XMzMyODk4NTQ4.html

捕获.PNG (2.96 KB, 下载次数: 17)

捕获.PNG
作者: gerenvip    时间: 2013-4-15 15:56
本帖最后由 gerenvip 于 2013-4-15 16:05 编辑

快速排序是综合性能最好的一种排序，它的基本思想是：
分治法
即把待排序序列分而治之，划成很多小序列进行排序。
实现过程，首先可以在序列中选一个元素作为基准元素pivotkey，一般选定为第一个，在这里设为pivotkey=arr[low]，其中low定义为每个划分序列的最低位置，high为每次划分序列的最高位置。
然后拿最低位的元素和这个基准元素比较，如果最低位的元素比基准小，那么low++
直到比基准元素大，这时把low位置上的元素和high位置上的元素互换
然后拿基准元素和最高位比较，如果基准元素小，那么high--，否者再把low位置元素和high位置元素互换。直到什么时候结束呢？肯定是直到low>=high的时候，然后返回一个位置low
上面说的是一趟排序。
返回一个low后，我们就知道，low位置左边的元素都比基准元素小，low右边的元素都比基准元素大。这样，我们就得到了左右两边的序列，两边都不再包含基准元素
然后利用上面的方法在同样处理得到的两个序列。知道最后划分的序列只有一个元素。
其中用到了递归算法。
下面是代码？是我自己从c语言上修改过来的，你可以看看
希望能帮助你！
  1. class  QSort
  2. {
  3.         public static void main(String[] args)
  4.         {
  5.                 int[] arr = {5,1,6,4,2,8};
  6.                 System.out.println("排序前：");
  7.                 printarray(arr);

  9.                 int num=arr.length;

  11.                 QSort(arr,0,num-1);
  12.                 System.out.println("排序后：");
  13.                 printarray(arr);
  14.         }
  15.         public static void printarray(int[] arr)
  16.         {
  17.                 System.out.print("[");
  18.                 for(int i=0;i<arr.length;i++)
  19.                 {
  20.                         if (i!=arr.length-1)
  21.                         System.out.print(arr[i]+", ");
  22.                         else
  23.                         System.out.println(arr[i]+"]");
  24.                 }//for
  25.         }

  27.         public static int Partition(int[] arr,int low,int high)
  28.         {
  29.                 int pivotkey;
  30.                 pivotkey = arr[low];
  31.                 while(low<high)
  32.                 {
  33.                         while(low<high&&arr[high]>=pivotkey)
  34.                                 high--;
  35.                         arr[low] = arr[high]; //将比枢轴小的移到低端
  36.                         while(low<high&&arr[low]<=pivotkey)
  37.                                 low++;
  38.                         arr[high] = arr[low]; //将比枢轴大的移到高端
  39.                
  40.                 }
  41.                 arr[low] = pivotkey;
  42.                 return low;
  43.         }

  45.         public static void QSort(int [] arr,int low,int high)
  46.         {
  47.                 int pivotloc;
  48.                 if(low<high)
  49.                 {
  50.                         pivotloc = Partition(arr,low,high);
  51.                         QSort(arr,low,pivotloc-1); //递归的调用，实现排序。
  52.                         QSort(arr,pivotloc+1,high);
  53.                 }
  54.                
  55.         }

  57. }

复制代码
作者: 何俊森    时间: 2013-4-15 16:03
快速排序的动画演示

快速排序.rar

9.02 KB, 下载次数: 82

快速排序的动画演示



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