黑马程序员技术交流社区

标题: 快速排序 [打印本页]
作者: 徐强    时间: 2012-10-29 22:00
标题: 快速排序
本帖最后由 徐强 于 2012-10-30 09:32 编辑

晚上看了下排序的几种算法，对快还排序没怎么看明白，那位大神能给我讲讲，最好能贴出一份注释祥细的java代码。{:2_41:}
作者: 古银平    时间: 2012-10-29 22:24
我给你思想，希望你能编出代码，自己写了才会记住：
      快速排序顺利用递归原理，把数组无限制的分成两部分，直到所有数据都排好序为止。
分析：快速排序的基本思想是通过一趟排序将要排序的数据分割成两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后按此方法对这两部分数据分别
         进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
步骤：      
        如果要排序的数组是A[0].........A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为中间数据，然后将所有比他小的数都放到它前面，所有比他大的数据都放到它
后面，这个过程称为一趟快速排序。一趟快速排序的算法如下：
（1）设置两个变量i，j，排序开始的时候：i=1,j=N-1.
（2）以第一个数组元素作为中间数据，赋值给pivot，即pivot=A[0]。
（3）从j开始向前搜索，即由后开始向前搜索（j--），找到第一个小于X的值。
（4）从i开始向后搜索，即由前开始向后搜索（i++），找到第一个大于X的值，并与上一步找到的数字交换。
（5）重复3,4步，直到i>=j。
（6）然后把j所在的数字与pivot交换。
（7）最后把j以前的数组和j到最后的数组，在进行递归的快速排序。
作者: 付维翔    时间: 2012-10-29 23:17
  1. public class QuicSort {

  3. /**
  4. * 一趟快速排序的方法
  5. *
  6. * @param array
  7. * 所要排序的数组
  8. * @param h
  9. * 排序子列的开始位置
  10. * @param p
  11. * 排序子列的结束位置
  12. * @return 返回当前一趟快速排序后，比较关键字所处于的位置
  13. */
  14. private static int quickPass(int[] array, int h, int p) {
  15. int i = h;
  16. int j = p;
  17. int x = array[i];// 比较所用的关键字
  18. while (i < j) {
  19. while ((array[j] >= x) && (i < j))
  20. // 自尾端进行比较
  21. j--;
  22. if (i < j) {
  23. array[i] = array[j];// 将小于关键字的记录移至i所指的位置，完成第一次交换
  24. i++;
  25. // 自首端进行比较
  26. while ((array[i] <= x) && (i < j)) {
  27. i++;
  28. if (i < j) {
  29. array[j] = array[i];// 将大于关键字的记录移到j所指的位置
  30. j--;
  31. }
  32. }
  33. }
  34. }
  35. array[i] = x;// 一趟快速排序完成，将x移至正确位置
  36. return i;
  37. }

  39. /**
  40. * 对一个数组的部分进行排序，
  41. *
  42. * @param array
  43. * 排序的数组
  44. * @param s
  45. * 排序开始的位置
  46. * @param t
  47. * 所要排序结束的位置
  48. */
  49. public static void quickSort(int[] array, int s, int t) {

  51. int i = 0;
  52. if (s < t) {// 未做数组越界检查的代码
  53. i = quickPass(array, s, t);
  54. quickSort(array, s, i - 1);
  55. quickSort(array, i + 1, t);
  56. }
  57. }

  59. /**
  60. * 对一个数组进行快速排序
  61. *
  62. * @param array
  63. * 排序的数组
  64. */
  65. public static void quickSort(int[] array) {

  67. int s = 0;
  68. int t = array.length - 1;
  69. int i = 0;
  70. if (s < t) {
  71. i = quickPass(array, s, t);
  72. quickSort(array, s, i - 1);
  73. quickSort(array, i + 1, t);
  74. }
  75. }

  77. /**
  78. * 输出排好序的数组
  79. *
  80. * @param array
  81. */
  82. private static void printArray(int[] array) {
  83. System.out.print("排过序的数组：");
  84. for (int a : array) {
  85. System.out.print(a + " ");
  86. }
  87. System.out.println("");
  88. }

  90. public static void main(String[] args) {
  91. int[] array1 = { 4, 1, 6, 3, 2, 9, 7 };
  92. quickSort(array1);// 此方法对一个数组使用快速排序法做升序排序
  93. System.out.println("对整个数组排序");
  94. printArray(array1);
  95. int[] array2 = { 4, 1, 6, 3, 2, 9, 7 };
  96. // 此方法，提供了对数组部分元素的进行排序的功能，比如，只排序数组中的前五位：
  97. quickSort(array2, 0, 4);
  98. System.out.println("仅对数组中前五位元素进行排序");
  99. printArray(array2);

  101. }
  102. }
复制代码
作者: 徐强    时间: 2012-10-30 10:48
受教了，自己学着写了一个出来看看。
  1. public class Sort {

  3.         /**
  4.          * 快速排序
  5.          */
  6.         public static void main(String[] args) {
  7.                 int arr[] = {4,12,5,1,97,16,3,7};

  9.                 quickSort(arr,0,arr.length-1);
  10.                 printArr(arr);

  12.         }

  14.         //用递归让整个数组序列化
  15.         private static void quickSort(int[] arr, int begin, int end) {
  16.                 if(begin>end){
  17.                         return ;
  18.                 }
  19.                 int i = onceSort(arr,begin,end);
  20.                 quickSort(arr,begin,i-1);
  21.                 quickSort(arr,i+1,end);
  22.         }

  24.         //打印数组
  25.         private static void printArr(int[] arr) {
  26.                 for(int i : arr){
  27.                         System.out.print(i+"\t");
  28.                 }
  29.                
  30.         }

  32.         //一趟快速排序，并返回用于下次分组的中间值i
  33.         public static int onceSort(int[]arr,int begin,int end){
  34.                 int i = begin;
  35.                 int j = end;
  36.                 int key = arr[i];
  37.                
  38.                 while(j>i){
  39.                         while(arr[j]>key&&j>i){
  40.                                 j--;
  41.                         }
  42.                         if(j>i){
  43.                                 arr[i] = arr[j];
  44.                                 arr[j] = key;
  45.                         }
  46.                         while(arr[i]<key&&j>i){
  47.                                 i++;
  48.                         }
  49.                         if(j>i){
  50.                                 arr[j] = arr[i];
  51.                                 arr[i] = key;
  52.                         }
  53.                 }
  54.                
  55.                 return i;
  56.         }
  57. }
复制代码




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