QuickSort

一般的快排，效率是稍微低一点的。

public void quickSort(int[] arr, int begin, int end) {
	if (begin < end) {
		int partition = partition(arr, begin, end);
		quickSort(arr, begin, partition - 1);
		quickSort(arr, partition + 1, end);
	}

}

public int partition(int[] arr, int begin, int end) {
	int pivot = arr[end];
	int start = begin;

	for (int i = begin; i < end; i++) {
		if (arr[i] < pivot) {
			swap(arr, i, start);
			start++;
		}
	}
	swap(arr, start, end);
	return start;
}

所以可以有两个标记i，j,从两边靠拢。初始的i = begin，j = end，用k来扫描整个序列。
始终保持序列中[start,i] < pivot; [i,k] = pivot; [j ,end] > pivot的。
因此当遇到小于pivot的元素，swap(arr,i,k),i++
当遇到大于pivot的元素，swap(arr,j,k),j–

public int partition(int[] arr, int begin, int end) {
	int pivot = arr[begin];
	int i = begin;
	int j = end - 1;
	int k = begin + 1;
	while(k <= j){
		if(arr[k] < pivot){
               swap(arr, i, k);
               i++;
               k++;
           } else if (arr[k] > pivot) {
               swap(items, j, k);
               j--;
           } else {
               k++;
           }
	
	}		
	swap(arr, start, end);
	return start;
}

还有另一种实现方式，也就是双轴快排(DualPivotQuickSort)，也是JDK1.8对基本数据类型排序的实现。
看一下源码是怎么实现的。可以看出是分成了三段，取两个中心点。pivot1，pivot2，且pivot <= pivot2，可将序列分成三段：x < pivot1、pivot1 <= x <= pivot2，x > pivot2

/*
          *   left part           center part                   right part
          * +--------------------------------------------------------------+
          * |  < pivot1  |  pivot1 <= && <= pivot2  |    ?    |  > pivot2  |
          * +--------------------------------------------------------------+
          *               ^                          ^       ^
          *               |                          |       |
          *              less                        k     great
 */

根据这个，大概实现了一下。

public void quickSort(int[] arr) {
	partition(arr,0,arr.length-1);
}
public void partition(int[] arr, int begin, int end) {

       if (begin < end) {

           int pivot1 = arr[begin];
           int pivot2 = arr[end];
           if (pivot1 > pivot2) {
               swap(arr, begin, end);
               int temp = pivot1;
               pivot1 = pivot2;
               pivot2 = temp;
           }
           int i = begin, j = end, k = begin + 1;

           outer:
           while (k < j) {
               if (arr[k] < pivot1) {
                   i++;
                   swap(arr, i, k);
                   k++;
               } else if (arr[k] <= pivot2) {
                   k++;
               } else { // arr[k] > pivot2

                   while (arr[--j] > pivot2) {
                       if (j == k) {
                           break outer;
                       }
                   }
                   if (arr[j] < pivot1) {
                       swap(arr, j, k);
                       i++;
                       swap(arr, i, k);
                   } else { // pivot1 <= x <= pivot2
                       swap(arr, j, k);
                   }
                   k++;
               }
           }
           swap(arr, begin, i);
           swap(arr, end, j);

           partition(arr, begin, i - 1);
           partition(arr, i + 1, j - 1);
           partition(arr, j + 1, end);
       }

   }