黑马程序员技术交流社区

标题: 分享一个排序算法——快速排序 [打印本页]
作者: yangcy    时间: 2014-7-12 14:35
标题: 分享一个排序算法——快速排序

快速排序算法是对冒泡排序算法的一种改进，由于冒泡排序是对相邻的数据进行两两比较，元素的移动次数和比较次数都比较多，所以快速排序采用了从记录序列的两端向中间进行的方式，所以在元素的移动次数和比较次数上都减少了。
基本思想：首先选定一个轴值（也就是比较的基准），将待排序记录分割成独立的两部分，左侧记录的关键码都小于或是等于轴值，右侧的记录关键码都大于或等于轴值，然后再对这两部分分别重复上述的过程，直到整个序列有序为止。
其中，取轴值的问题，可以取首值、中值或尾值，或是大小居中的值，我一般取首值。
代码如下：


  1. import org.junit.Test;

  3. public class QuickSort {
  4.         @Test
  5.         public void test() {
  6.                 int[] arr = { 3, 6, 2, 4, 7, 1 };
  7.                 quickSort(arr, 0, arr.length - 1);
  8.                 for (int i = 0; i < arr.length; i++) {
  9.                         System.out.print(arr[i] + " ");
  10.                 }
  11.         }

  13.         public void quickSort(int[] arr, int first, int end) {
  14.                 if (first < end) {
  15.                         int i = partition(arr, first, end);
  16.                         quickSort(arr, first, i - 1);// 轴值左侧进行递归划分
  17.                         quickSort(arr, i + 1, end);// 轴值右侧进行递归划分
  18.                 }
  19.         }

  21.         // 一次划分
  22.         public int partition(int[] arr, int first, int end) {
  23.                 int i, j;
  24.                 i = first;// 取first为轴值
  25.                 j = end;
  26.                 while (i < j) {
  27.                         // 在轴值的右侧扫描
  28.                         while (i < j && arr[j] >= arr[i]) {
  29.                                 j--;
  30.                         }
  31.                         // 如果扫描到比轴值小的，则将两者调换位置
  32.                         if (i < j) {
  33.                                 swap(arr, i, j);
  34.                         }
  35.                         // 在轴值的左侧扫描
  36.                         while (i < j && arr[i] < arr[j]) {
  37.                                 i++;
  38.                         }
  39.                         // 如果扫描到比轴值大的，则将两者调换位置
  40.                         if (i < j) {
  41.                                 swap(arr, i, j);
  42.                         }
  43.                 }
  44.                 return i;// 返回轴值的下标
  45.         }

  47.         private void swap(int[] arr, int i, int j) {
  48.                 int temp = arr[i];
  49.                 arr[i] = arr[j];
  50.                 arr[j] = temp;
  51.         }
  52. }
复制代码


作者: itheima-zx    时间: 2014-7-12 22:06
NB啊 ，这个方法确实很好。



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