当前位置：首页 > 资讯 > 技术文档

Java编程实现快速排序及优化代码详解

时间：2021-10-11 17:56 编辑：来源：阅读：
扫一扫，手机访问

摘要：Java编程实现快速排序及优化代码详解

[b]普通快速排序[/b] 找一个基准值base，然后一趟排序后让base左边的数都小于base，base右边的数都大于等于base。再分为两个子数组的排序。如此递归下去。

public class QuickSort {
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  sort(arr, 0, arr.length - 1);
 }
 public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
  if (left >= right) return;
  int p = partition(arr, left, right);
  sort(arr, left, p - 1);
  sort(arr, p + 1, right);
 }
 private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
  T base = arr[left];
  int j = left;
  for (int i = left + 1; i <= right; i++) {
   if (base.compareTo(arr[i]) > 0) {
    j++;
    swap(arr, j, i);
   }
  }
  swap(arr, left, j);
  return j;
  //返回一躺排序后基准值的下角标
 }
 public static void swap(Object[] arr, int i, int j) {
  if (i != j) {
   Object temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 private static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);
  //3  5  1  7  2  9  8  0  4  6
  sort(arr);
  printArr(arr);
  //0  1  2  3  4  5  6  7  8  9
 }
}

快速排序优化：随机选取基准值base 在数组几乎有序时，快排性能不好（因为每趟排序后，左右两个子递归规模相差悬殊，大的那部分最后很可能会达到O(n^2)）。解决：基准值随机地选取，而不是每次都取第一个数。这样就不会受“几乎有序的数组”的干扰了。但是对“几乎乱序的数组”的排序性能可能会稍微下降，至少多了排序前交换的那部分，乱序时这个交换没有意义...有很多“运气”成分..

public class QuickSort {
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  sort(arr, 0, arr.length - 1);
 }
 public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right) {
  if (left >= right) return;
  int p = partition(arr, left, right);
  sort(arr, left, p - 1);
  sort(arr, p + 1, right);
 }
 private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
  //排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
  //就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
  swap(arr,left,(int)(Math.random()*(right - left + 1)+left));
  T base = arr[left];
  int j = left;
  for (int i = left + 1; i <= right; i++) {
   if (base.compareTo(arr[i]) > 0) {
    j++;
    swap(arr, j, i);
   }
  }
  swap(arr, left, j);
  return j;
  //返回一躺排序后，基准值的下角标
 }
 public static void swap(Object[] arr, int i, int j) {
  if (i != j) {
   Object temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 private static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);
  //3  5  1  7  2  9  8  0  4  6
  sort(arr);
  printArr(arr);
  //0  1  2  3  4  5  6  7  8  9
 }
}

快速排序继续优化：配合着使用插入排序快排是不断减小问题规模来解决子问题的，需要不断递归。但是递归到规模足够小时，如果继续采用这种不稳定+递归的方式执行下去，效率不见得会很好。所以当问题规模较小时，近乎有序时，插入排序表现的很好。Java自带的Arrays.sort()里经常能看到这样的注释：“Use insertion sort on tiny arrays”，“Insertion sort on smallest arrays”

public class QuickSort {
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  sort(arr, 0, arr.length - 1, 16);
 }
 /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时，采用插入排序优化
   * @param <T>  泛型，待排序可比较类型
   */
 public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
  // 规模小时采用插入排序
  if (right - left <= k) {
   insertionSort(arr, left, right);
   return;
  }
  int p = partition(arr, left, right);
  sort(arr, left, p - 1, k);
  sort(arr, p + 1, right, k);
 }
 public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
  for (int i = l + 1; i <= r; i++) {
   T cur = arr[i];
   int j = i - 1;
   for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
    arr[j + 1] = arr[j];
   }
   arr[j + 1] = cur;
  }
 }
 private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
  //排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
  //就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
  swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
  T base = arr[left];
  int j = left;
  for (int i = left + 1; i <= right; i++) {
   if (base.compareTo(arr[i]) > 0) {
    j++;
    swap(arr, j, i);
   }
  }
  swap(arr, left, j);
  return j;
  //返回一躺排序后，基准值的下角标
 }
 public static void swap(Object[] arr, int i, int j) {
  if (i != j) {
   Object temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 private static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);
  //3  5  1  7  2  9  8  0  4  6
  sort(arr);
  printArr(arr);
  //0  1  2  3  4  5  6  7  8  9
 }
}

[b]快速排序继续优化：两路快排[/b] 在最开始的普通快速排序说过，让基准值base左边的都比base小，而base右边的都大于等于base。等于base的这些会聚集到右侧(或者稍微改改大小关系就会聚集到左侧)。总之就会聚集到一边。这样在数组中重复数字很多的时候，就又会导致两边子递归规模差距悬殊的情况。这时想把等于base的那些数分派到base两边，而不是让他们聚集到一起。（注：测试代码的时候，最好把插入排序那部分注视掉，向我下面代码中那样...不然数据量小于k=16的时候执行的是插入排序.....）

public class QuickSort {
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  sort(arr, 0, arr.length - 1, 16);
 }
 /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时，采用插入排序优化
   * @param <T>  泛型，待排序可比较类型
   */
 public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
  // 规模小时采用插入排序
  //    if (right - left <= k) {
  //      insertionSort(arr, left, right);
  //      return;
  //    }
  if (left >= right) return;
  int p = partition(arr, left, right);
  sort(arr, left, p - 1, k);
  sort(arr, p + 1, right, k);
 }
 public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
  for (int i = l + 1; i <= r; i++) {
   T cur = arr[i];
   int j = i - 1;
   for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
    arr[j + 1] = arr[j];
   }
   arr[j + 1] = cur;
  }
 }
 private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
  //排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
  //就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
  swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
  T base = arr[left];
  //基准值，每次都把这个基准值抛出去，看成[left+1.....right]左闭右闭区间的排序
  int i = left + 1;
  //对于上一行提到的[left+1.....right]区间，i表示 [left+1......i)左闭右开区间的值都小于等于base。
  int j = right;
  //对于上二行提到的[left+1.....right]区间，j表示 (j......right]左开右闭区间的值都大于等于base。
  while (true) {
   //从左到右扫描，扫描出第一个比base大的元素，然后i停在那里。
   while (i <= right && arr[i].compareTo(base) < 0) i++;
   //从右到左扫描，扫描出第一个比base小的元素，然后j停在那里。
   while (j >= left && arr[j].compareTo(base) > 0) j--;
   if (i > j) {
    //虽说是i>j，但其实都是以j=i-1为条件结束的
    break;
   }
   swap(arr, i++, j--);
  }
  swap(arr, left, j);
  return j;
  //返回一躺排序后，基准值的下角标
 }
 public static void swap(Object[] arr, int i, int j) {
  if (i != j) {
   Object temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 private static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);
  //3  5  1  7  2  9  8  0  4  6
  sort(arr);
  printArr(arr);
  //0  1  2  3  4  5  6  7  8  9
 }
}

[b]快速排序继续优化：两路快排不用swap,用交换[/b] 上面的两路在找到大于base的值和小于base的值时，用的是swap()方法来进行交换。两数交换涉及到第三个变量temp的操作，多了读写操作。接下来用直接赋值的方法，把小于的放到右边，大于的放到左边，当i和j相遇时，那个位置就是base该放的地方。至此一趟完成。递归即可。

public class QuickSort {
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  sort(arr, 0, arr.length - 1, 16);
 }
 /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时，采用插入排序优化
   * @param <T>  泛型，待排序可比较类型
   */
 public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
  // 规模小时采用插入排序
  //    if (right - left <= k) {
  //      insertionSort(arr, left, right);
  //      return;
  //    }
  if (left >= right) return;
  int p = partition(arr, left, right);
  sort(arr, left, p - 1, k);
  sort(arr, p + 1, right, k);
 }
 public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
  for (int i = l + 1; i <= r; i++) {
   T cur = arr[i];
   int j = i - 1;
   for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
    arr[j + 1] = arr[j];
   }
   arr[j + 1] = cur;
  }
 }
 private static <T extends Comparable<? super T>> int partition(T[] arr, int left, int right) {
  //排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
  //就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
  swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
  T base = arr[left];
  //基准值，每次都把这个基准值抛出去，看成[left+1.....right]左闭右闭区间的排序
  int i = left;
  //对于上一行提到的[left+1.....right]区间，i表示 [left+1......i)左闭右开区间的值都小于等于base。
  int j = right;
  //对于上二行提到的[left+1.....right]区间，j表示 (j......right]左开右闭区间的值都大于等于base。
  while (i < j) {
   //从右到左扫描，扫描出第一个比base小的元素，然后j停在那里。
   while (j > i && arr[j].compareTo(base) > 0) j--;
   arr[i] = arr[j];
   //从左到右扫描，扫描出第一个比base大的元素，然后i停在那里。
   while (i < j && arr[i].compareTo(base) < 0) i++;
   arr[j] = arr[i];
  }
  arr[j] = base;
  return j;
  //返回一躺排序后，基准值的下角标
 }
 public static void swap(Object[] arr, int i, int j) {
  if (i != j) {
   Object temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 private static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);
  //3  5  1  7  2  9  8  0  4  6
  sort(arr);
  printArr(arr);
  //0  1  2  3  4  5  6  7  8  9
 }
}

快速排序继续优化：当大量数据，且重复数多时，用三路快排把数组分为三路，第一路都比base小，第二路都等于base，第三路都大于base。用指针从前到后扫描，如果： 1.cur指向的数小于base，那么：交换arr[cur]和arr[i]的值，然后i++,cur++。 2.cur指向的数等于base,那么：cur++ 3.cur指向的数大于base，那么：交换arr[cur]和arr[j]的值，然后j--。当cur>j的时候说明三路都已经完成。 [img]http://files.jb51.net/file_images/article/201712/2017125151233386.png?2017115151249[/img]

public class QuickSort {
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  sort(arr, 0, arr.length - 1, 16);
 }
 /**
   * @param arr  待排序的数组
   * @param left 左闭
   * @param right 右闭
   * @param k   当快排递归到子问题的规模 <= k 时，采用插入排序优化
   * @param <T>  泛型，待排序可比较类型
   */
 public static <T extends Comparable<? super T>> void sort(T[] arr, int left, int right, int k) {
  // 规模小时采用插入排序
  //    if (right - left <= k) {
  //      insertionSort(arr, left, right);
  //      return;
  //    }
  if (left >= right) return;
  int[] ret = partition(arr, left, right);
  sort(arr, left, ret[0], k);
  sort(arr, ret[1], right, k);
 }
 public static <T extends Comparable<? super T>> void insertionSort(T[] arr, int l, int r) {
  for (int i = l + 1; i <= r; i++) {
   T cur = arr[i];
   int j = i - 1;
   for (; j >= 0 && cur.compareTo(arr[j]) < 0; j--) {
    arr[j + 1] = arr[j];
   }
   arr[j + 1] = cur;
  }
 }
 /**
   * @param arr  待排序的数组
   * @param left 待排序数组的左边界
   * @param right 待排序数组的右边界
   * @param <T>  泛型
   * @return
   */
 private static <T extends Comparable<? super T>> int[] partition(T[] arr, int left, int right) {
  //排序前，先让基准值和随机的一个数进行交换。这样，基准值就有随机性。
  //就不至于在数组相对有序时，导致左右两边的递归规模不一致，产生最坏时间复杂度
  swap(arr, left, (int) (Math.random() * (right - left + 1) + left));
  T base = arr[left];
  //基准值，每次都把这个基准值抛出去，看成[left+1.....right]左闭右闭区间的排序
  //三路快排分为下面这三个路(区间)
  int i = left;
  // left表示，[lleft...left) 左闭右开区间里的数都比base小
  int j = right;
  // left表示，(rright...right] 左开右闭区间里的数都比base大
  int cur = i;
  //用cur来遍历数组。[left...cur)左闭右开区间里的数都等于base
  while (cur <= j) {
   if (arr[cur].compareTo(base) == 0) {
    cur++;
   } else if (arr[cur].compareTo(base) < 0) {
    swap(arr, cur++, i++);
   } else {
    swap(arr, cur, j--);
   }
  }
  return new int[]{i - 1, j + 1};
  //[i...j]都等于base,子问题就只需要解决i左边和j右边就行了
 }
 public static void swap(Object[] arr, int i, int j) {
  if (i != j) {
   Object temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
  }
 }
 private static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);
  //3  5  1  7  2  9  8  0  4  6
  sort(arr);
  printArr(arr);
  //0  1  2  3  4  5  6  7  8  9
 }
}

[b]总结[/b] 以上就是本文关于Java编程实现快速排序及优化代码详解的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

全部评论(0)

上一篇：java byte数组与int,long,short,byte的转换实现方法
下一篇：java计算自然数中的水仙花数的方法分享

资讯排行榜
更多>>