package lib;

import java.util.concurrent.*;

public class Sort {
 private int[] intArray = null;

 public Sort(int[] array) {
 if (array == null) throw new NullPointerException();
 intArray = array;
 }

 //插入排序
 public static void insertionSort(int arr[]) {
 insertionSort(arr, 0, arr.length);
 }

 //对数组的一部分进行插入排序
 //函数处理数组的[left,right-1]部分
 private static void insertionSort(int[] arr, int left, int right) {
 if (right <= left) throw new IllegalArgumentException("Right index less than or equals to left index.");
 int i, j;
 for (i = left + 1; i <= right - 1; i++) {
 int key = arr[i];
 for (j = i - 1; j >= 0; j--) {
 if (arr[j] > key) arr[j + 1] = arr[j];
 else break;
 }
 arr[j + 1] = key;
 }
 }

 //逆向插入排序
 public static void reverseInsertionSort(int arr[]) {
 int i, j;
 for (i = arr.length - 2; i >= 0; i--) {
 int key = arr[i];
 for (j = i + 1; j <= arr.length - 1; j++) {
 if (arr[j] > key) arr[j - 1] = arr[j];
 else break;
 }
 arr[j - 1] = key;
 }
 }

 //快速排序
 //函数处理数组的[left,right-1]部分
 private static void qsort(int[] arr, int left, int right) {
 if (right <= left) throw new IllegalArgumentException("Right index less than or equals to left index.");
 if (right - left <= 20) {
 insertionSort(arr);
 return;
 }
 int low = left;
 int high = right - 1;
 int medium = (low + high) / 2;

 // Medium-of-Three方法选择枢轴
 //目标: arr[medium] <= arr[high]
 if (arr[medium] > arr[high]) {
 swap(arr, medium, high);
 }
 //目标: arr[low] <= arr[high]
 if (arr[low] > arr[high]) {
 swap(arr, low, high);
 }
 //目标: arr[low] >= arr[medium]
 if (arr[medium] > arr[low]) {
 swap(arr, medium, low);
 }

 //分割数组
 int pivot = arr[low];
// while (low != high) {
// while (low != high) {
// if (arr[high] >= pivot) high--;
// else {
// arr[low] = arr[high];
// break;
// }
// }
// while (low != high) {
// if (arr[low] <= pivot) low++;
// else {
// arr[high] = arr[low];
// break;
// }
// }
// }
 while (true) {
 while (low != high && arr[high] >= pivot) high--;
 if (low != high) arr[low] = arr[high];
 else break;
 while (low != high && arr[low] <= pivot) low++;
 if (low != high) arr[high] = arr[low];
 else break;
 }
 int pivotIndex = low;
 arr[pivotIndex] = pivot;

 //递归
 qsort(arr, left, pivotIndex);
 qsort(arr, pivotIndex + 1, right);
 }

 //快速排序
 //调用qsort(int[] arr, int left, int right)
 public static void qsort(int[] arr) {
 qsort(arr, 0, arr.length);
 }

 //并行快速排序
 //基于ForkJoin框架
 public void parallelQSort() {
 ForkJoinPool pool = new ForkJoinPool();
 ParallelQSortTask masterTask = new ParallelQSortTask(0, intArray.length);
 pool.invoke(masterTask);
 }

 //交换数组中两个元素的位置
 private static void swap(int[] arr, int indexA, int indexB) {
 int tmp = arr[indexA];
 arr[indexA] = arr[indexB];
 arr[indexB] = tmp;
 }

 //用于并行快速排序的内部类
 class ParallelQSortTask extends RecursiveAction {
 private final int left;
 private final int right;

 public ParallelQSortTask(int left, int right) {
 if (right <= left) throw new IllegalArgumentException("Right index less than or equals to left index.");
 this.left = left;
 this.right = right;
 }

 public void compute() {
 //问题规模小,串行解决
 if (right - left <= 20) {
 insertionSort(intArray, left, right);
 return;
 }
 int low = left;
 int high = right - 1;
 int medium = (low + high) / 2;

 // Medium-of-Three方法选择枢轴
 //目标: arr[medium] <= arr[high]
 if (intArray[medium] > intArray[high]) {
 swap(intArray, medium, high);
 }
 //目标: arr[low] <= arr[high]
 if (intArray[low] > intArray[high]) {
 swap(intArray, low, high);
 }
 //目标: arr[low] >= arr[medium]
 if (intArray[medium] > intArray[low]) {
 swap(intArray, medium, low);
 }

 //分割数组
 int pivot = intArray[low];
 while (true) {
 while (low != high && intArray[high] >= pivot) high--;
 if (low != high) intArray[low] = intArray[high];
 else break;
 while (low != high && intArray[low] <= pivot) low++;
 if (low != high) intArray[high] = intArray[low];
 else break;
 }
 int pivotIndex = low;
 intArray[pivotIndex] = pivot;

 ParallelQSortTask leftTask = new ParallelQSortTask(left, pivotIndex);
 ParallelQSortTask rightTask = new ParallelQSortTask(pivotIndex + 1, right);
 leftTask.invoke();
 rightTask.invoke();
 }
 }
}