十大排序算法之快速排序

快速排序是一类比较著名的排序算法，时间复杂度为O（n log n)，体现了分治思想，侧重于分，归并排序在于治。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序重要过程就是partition，找到使得元素p左边比它小，右边比它大的位置。以下是具体实现过程，其中加了两步优化，一个是当是小序列时直接用插入排序，第二个是在partition过程中，随机将区间的某一元素与区间最左边位置进行互换，避免每一次partition将序列分割成非常不平衡的情况，这种情况导致递归树太深退化为链表，时间复杂度时O(n ^ 2)，针对近乎有序的数组有效，但是对于大量重复的元素此步优化操作效果较差，因为还是会将序列分割成为极度不平衡的情况，后面讲到的双路快速排序和三路快速排序就是来解决此类问题。

import java.util.Random;

import cn.zjut.util.SortTestUtil;

public class QuickSort {
Random random;

public void quickSort(int[] arr, int n) {
random = new Random(0xff);
quickSort(arr, 0, n - 1);
}

private void quickSort(int[] arr, int l, int r) {
//  if (l >= r)
//   return;
  //优化1
  //对于小序列使用插入排序
  if(r - l <=15) {
   new InsertSort().insertSort(arr, l, r);
   return;
  }
  //获取对当前区间的分割位置
  int p = partition(arr, l, r);
  //分别对分割点两部分子区间进行递归调用快速排序过程
  quickSort(arr, l, p - 1);
  quickSort(arr, p + 1, r);
}

//partition过程
private int partition(int[] arr, int l, int r) {
  //优化2
  //将区间中任一一点元素与最左边元素位置进行交换
  SortTestUtil.swap(arr, l, random.nextInt(Integer.MAX_VALUE) % (r - l + 1) + l );
  int v = arr[l];  //获取区间最左边元素值,也是分割值(关键值)
  int j = l;   //记录当前分割值应该在的位置,初始在区间左边界
  //循环遍历整个区间
  for (int i = l + 1; i <= r; i++) {
   //如果元素比分割值小,j自加一
   if (arr[i] < v) {
    j++;
    //将这个两个元素进行交换
    SortTestUtil.swap(arr, i, j);
   }
  }
  //交换找到分割点j与左边元素
  SortTestUtil.swap(arr, l, j);
  //返回分割点
  return j;
}
}

以下是快速排序与优化后归并排序测试程序

import cn.zjut.util.SortTestUtil;

public class Main {

以下是测试结果

十大排序算法之快速排序

对于随机数组，效果优于优化后的归并排序，对于大量重复元素的数组效果相差很大，当大量重复元素数组数据量加大时会报栈内存溢出，针对近乎有序数组，效果与优化后的归并排序相差不大。针对以上情况，有了双路快速排序，和三路快速排序。双路快速排序是将小于v和大于v的元素放在数组的两端，将使用用新的索引j的记录大于v的边界位置。i索引不断向后扫描，当i的元素小于v的时候继续向后扫描，直到碰到了某个元素大于等于v。j同理，直到碰到某个元素小于等于v。此时只需要交换i和j的位置所对应的元素，i++，j--，继续遍历，知道遍历完整个数组。以下是具体实现过程：

import java.util.Random;

import cn.zjut.util.SortTestUtil;

public class QuickSortDoubleWay {
Random random;

public void quickSort(int[] arr, int n) {
random = new Random(0xff);
quickSort(arr, 0, n - 1);
}

private void quickSort(int[] arr, int l, int r) {
  if (r - l <= 15) {
   new InsertSort().insertSort(arr, l, r);
   return;
  }
  int p = partition(arr, l, r);
  quickSort(arr, l, p - 1);
  quickSort(arr, p + 1, r);
}

private int partition(int[] arr, int l, int r) {
  SortTestUtil.swap(arr, l, random.nextInt(Integer.MAX_VALUE) % (r - l + 1) + l );
  int v = arr[l];
  int i, j; //i,j分别记录当前小于v值的位置和当前大于v值的位置
  i = l + 1;//i初始化为左边界加1位置
  j = r;   //j最右边位置
  while(true) {
   while(i <= r && arr[i] < v) i++;
   while(j >= l + 1 && arr[j] > v) j--;
   if(i > j) break;
   SortTestUtil.swap(arr, i, j);
   i++;
   j--;
  }
  SortTestUtil.swap(arr, l, j);
  return j;
}
}

以下是相关测试程序

import cn.zjut.util.SortTestUtil;

public class Main {

public static void main(String[] args){
  int n = 100000;
  System.out.println("Test for Random Array, size = " + n + ", random range [0, " + n + ']');
  int[] arr1 = SortTestUtil.generateRandomArray(n, 0, n);
  int[] arr2 = SortTestUtil.copyIntArray(arr1, n);
  int[] arr3 = SortTestUtil.copyIntArray(arr1, n);
  SortTestUtil.testSort("MergeSortImprove", "cn.zjut.sort.MergeSortImprove", "mergeSort", arr1, n);
  SortTestUtil.testSort("QuickSort", "cn.zjut.sort.QuickSort", "quickSort", arr2, n);
  SortTestUtil.testSort("QuickSortDoubleWay", "cn.zjut.sort.QuickSortDoubleWay", "quickSort", arr3, n);

  System.out.println("--------------------------------");

  System.out.println("Test for Random Array, size = " + n + ", random range [0, " + 10 + ']');
  arr1 = SortTestUtil.generateRandomArray(n, 0, 10);
  arr2 = SortTestUtil.copyIntArray(arr1, n);
  arr3 = SortTestUtil.copyIntArray(arr1, n);
  SortTestUtil.testSort("MergeSortImprove", "cn.zjut.sort.MergeSortImprove", "mergeSort", arr1, n);
  SortTestUtil.testSort("QuickSort", "cn.zjut.sort.QuickSort", "quickSort", arr2, n);
  SortTestUtil.testSort("QuickSortDoubleWay", "cn.zjut.sort.QuickSortDoubleWay", "quickSort", arr3, n);

  System.out.println("--------------------------------");

  int swapTime = 10;
     System.out.println("Test for Random Nearly Ordered Array, size = " + n + ", swap time = " + swapTime);
     arr1 = SortTestUtil.generateNearlyOrderedArray(n, swapTime);
     arr2 = SortTestUtil.copyIntArray(arr1, n);
     arr3 = SortTestUtil.copyIntArray(arr1, n);
  SortTestUtil.testSort("MergeSortImprove", "cn.zjut.sort.MergeSortImprove", "mergeSort", arr1, n);
  SortTestUtil.testSort("QuickSort", "cn.zjut.sort.QuickSort", "quickSort", arr2, n);
  SortTestUtil.testSort("QuickSortDoubleWay", "cn.zjut.sort.QuickSortDoubleWay", "quickSort", arr3, n);
}
}

相关测试结果如下

十大排序算法之快速排序

从结果上看，二路快速排序对于大量重复元素的排序时间效率得到很大的提高，其他类型的数据效果也是很好。双路快排将整个数组分成了小于v，大于v的两部分，而三路快排则是将数组分成了小于v，等于v，大于v的三个部分，当递归处理的时候，遇到等于v的元素直接不用管，只需要处理小于v，大于v的元素。这是一类比较经典的优化过程，以下是其具体实现过程

import java.util.Random;

import cn.zjut.util.SortTestUtil;

public class QuickSortTribleWay {
Random random;

public void quickSort(int[] arr, int n) {
random = new Random(0xff);
quickSort(arr, 0, n - 1);
}

private void quickSort(int[] arr, int l, int r) {
  if (r - l <= 15) {
   new InsertSort().insertSort(arr, l, r);
   return;
  }
  SortTestUtil.swap(arr, l, random.nextInt(Integer.MAX_VALUE) % (r - l + 1) + l);
  int v = arr[l]; //保存分割值
  int lt = l;     //arr[l+1...lt] < v arr[lt+1...i-]==v arr[gt...r]>v
  int gt = r + 1;
  int i = l + 1;
  while(i < gt) {
   if(arr[i] < v) {
    SortTestUtil.swap(arr, i, lt + 1);
    lt++;
    i++;
   } else if(arr[i] > v) {
    SortTestUtil.swap(arr, i, gt - 1);
    gt--;
   } else {
    i++;
   }
  }
  SortTestUtil.swap(arr, l, lt);
  quickSort(arr, l, lt - 1);
  quickSort(arr, gt, r);
}
}

以下是测试代码

import cn.zjut.util.SortTestUtil;

public class Main {

public static void main(String[] args){
  int n = 100000;
  System.out.println("Test for Random Array, size = " + n + ", random range [0, " + n + ']');
  int[] arr1 = SortTestUtil.generateRandomArray(n, 0, n);
  int[] arr2 = SortTestUtil.copyIntArray(arr1, n);
  int[] arr3 = SortTestUtil.copyIntArray(arr1, n);
  int[] arr4 = SortTestUtil.copyIntArray(arr1, n);
  SortTestUtil.testSort("MergeSortImprove", "cn.zjut.sort.MergeSortImprove", "mergeSort", arr1, n);
  SortTestUtil.testSort("QuickSort", "cn.zjut.sort.QuickSort", "quickSort", arr2, n);
  SortTestUtil.testSort("QuickSortDoubleWay", "cn.zjut.sort.QuickSortDoubleWay", "quickSort", arr3, n);
  SortTestUtil.testSort("QuickSortTribleWay", "cn.zjut.sort.QuickSortTribleWay", "quickSort", arr4, n);

  System.out.println("--------------------------------");

  System.out.println("Test for Random Array, size = " + n + ", random range [0, " + 10 + ']');
  arr1 = SortTestUtil.generateRandomArray(n, 0, 10);
  arr2 = SortTestUtil.copyIntArray(arr1, n);
  arr3 = SortTestUtil.copyIntArray(arr1, n);
  arr4 = SortTestUtil.copyIntArray(arr1, n);
  SortTestUtil.testSort("MergeSortImprove", "cn.zjut.sort.MergeSortImprove", "mergeSort", arr1, n);
  SortTestUtil.testSort("QuickSort", "cn.zjut.sort.QuickSort", "quickSort", arr2, n);
  SortTestUtil.testSort("QuickSortDoubleWay", "cn.zjut.sort.QuickSortDoubleWay", "quickSort", arr3, n);
  SortTestUtil.testSort("QuickSortTribleWay", "cn.zjut.sort.QuickSortTribleWay", "quickSort", arr4, n);

  System.out.println("--------------------------------");

  int swapTime = 10;
     System.out.println("Test for Random Nearly Ordered Array, size = " + n + ", swap time = " + swapTime);
     arr1 = SortTestUtil.generateNearlyOrderedArray(n, swapTime);
     arr2 = SortTestUtil.copyIntArray(arr1, n);
     arr3 = SortTestUtil.copyIntArray(arr1, n);
     arr4 = SortTestUtil.copyIntArray(arr1, n);
  SortTestUtil.testSort("MergeSortImprove", "cn.zjut.sort.MergeSortImprove", "mergeSort", arr1, n);
  SortTestUtil.testSort("QuickSort", "cn.zjut.sort.QuickSort", "quickSort", arr2, n);
  SortTestUtil.testSort("QuickSortDoubleWay", "cn.zjut.sort.QuickSortDoubleWay", "quickSort", arr3, n);
  SortTestUtil.testSort("QuickSortTribleWay", "cn.zjut.sort.QuickSortTribleWay", "quickSort", arr4, n);
}
}

以下是测试结果

十大排序算法之快速排序

从结果可知三路快速排序针对大量重复元素的素组优化效果也比较好，对于随机数组和近乎有序的数组会损失一些性能。以上整个过程就是快速排序的全过程。

十大排序算法之快速排序

相关推荐