图解Java排序算法之快速排序的三数取中法

基本步骤

三数取中

在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。

根据枢纽值进行分割

代码实现

package sortdemo;
import java.util.Arrays;
/**
* Created by chengxiao on 2016/12/14.
* 快速排序
*/
public class QuickSort {
   public static void main(String[] args) {
       int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
       quickSort(arr, 0, arr.length - 1);
       System.out.println("排序结果：" + Arrays.toString(arr));
   }
   /**
    * @param arr
    * @param left  左指针
    * @param right 右指针
    */
   public static void quickSort(int[] arr, int left, int right) {
       if (left < right) {
           //获取枢纽值，并将其放在当前待处理序列末尾
           dealPivot(arr, left, right);
           //枢纽值被放在序列末尾
           int pivot = right - 1;
           //左指针
           int i = left;
           //右指针
           int j = right - 1;
           while (true) {
               while (arr[++i] < arr[pivot]) {
               }
               while (j > left && arr[--j] > arr[pivot]) {
               }
               if (i < j) {
                   swap(arr, i, j);
               } else {
                   break;
               }
           }
           if (i < right) {
               swap(arr, i, right - 1);
           }
           quickSort(arr, left, i - 1);
           quickSort(arr, i + 1, right);
       }
   }
   /**
    * 处理枢纽值
    *
    * @param arr
    * @param left
    * @param right
    */
   public static void dealPivot(int[] arr, int left, int right) {
       int mid = (left + right) / 2;
       if (arr[left] > arr[mid]) {
           swap(arr, left, mid);
       }
       if (arr[left] > arr[right]) {
           swap(arr, left, right);
       }
       if (arr[right] < arr[mid]) {
           swap(arr, right, mid);
       }
       swap(arr, right - 1, mid);
   }
   /**
    * 交换元素通用处理
    *
    * @param arr
    * @param a
    * @param b
    */
   private static void swap(int[] arr, int a, int b) {
       int temp = arr[a];
       arr[a] = arr[b];
       arr[b] = temp;
   }
}

排序结果

[1, 2, 3, 4, 5, 6, 7, 8]

来源：https://www.cnblogs.com/chengxiao/p/6262208.html