import java.util.Arrays;

public class SortConclusion {

    // 插入排序，每趟都把最大的放在相应的位置上
    public static void bubbleSort(int[] nums) {
        int n = nums.length;
        if (nums == null || n < 2) {
            return;
        }
        for (int i = n - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }

    // 选择排序，每趟都选择出当前是最小的元素，放在相应的位置
    public static void selectionSort(int[] nums) {
        int n = nums.length;
        if (nums == null || n < 2) {
            return;
        }
        for (int i = 0; i < n; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            swap(nums,i,minIndex);
        }
    }

    // 插入排序，每趟都从i位置开始，依次向前比较
    public static void insertionSort(int[] nums) {
        int n = nums.length;
        if (nums == null || n < 2) {
            return;
        }
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j - 1, j);
                }
            }
        }
    }

    // 归并排序
    public static void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, hi);
    }

    public static void merge(int[] nums, int lo, int hi) {
        int mid = lo + (hi - lo) / 2;
        int left = lo, right = mid + 1;
        int[] tmpArr = new int[hi - lo + 1];
        int index = 0;
        while (left <= mid && right <= hi) {
            tmpArr[index++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
        }
        while (left <= mid) {
            tmpArr[index++] = nums[left++];
        }
        while (right <= hi) {
            tmpArr[index++] = nums[right++];
        }
        for (int i = 0; i < tmpArr.length; i++) {
            nums[lo + i] = tmpArr[i];
        }
    }

    // 快速排序，选择轴点，左右递归
    public static void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = partition(nums, lo, hi);
        quickSort(nums, lo, pivot - 1);
        quickSort(nums, pivot + 1, hi);
    }

    public static int partition(int[] nums, int lo, int hi) {
        swap(nums, lo, (int) (lo + Math.random() * (hi - lo + 1)));
        int pivot = nums[lo];
        while (lo < hi) {
            while (lo < hi && pivot <= nums[hi]) hi--;
            nums[lo] = nums[hi];
            while (lo < hi && pivot >= nums[lo]) lo++;
            nums[hi] = nums[lo];
        }
        nums[lo] = pivot;
        return lo;
    }

    // 因为这里索引值是从0开始的，所以父节点的索引值为(index - 1) / 2，左孩子和右孩子的索引值分别为2 * index + 1, 2 * index + 2
    public static void heapSort(int[] arr) {
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            // 构造大根堆
            heapInsert(arr, i);
        }
        // 将最大的元素放到最后，即最大的元素位置已经确定下来
        swap(arr, 0, --size);
        // 对剩下的n-1个元素进行调整
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    // 上滤
    public static void heapInsert(int[] arr, int index) {
        // 如果到了0位置，那么自然也不满足循环的条件，因此会跳出循环
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 下滤， 0-size-1的位置形成堆，由于index的值发生改变需要下滤，即size用于表示标识是否越界
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        while (left < size) {
            // 取出左右孩子中大的那个下标
            int largest = left + 1 < size && arr[left + 1] > arr[left]
                    ? left + 1
                    : left;
            if (arr[index] > arr[largest]) break;
            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void shellSort(int[] nums) {
        int n = nums.length;
        int h = 1;
        // 设置希尔的增量排序
        while (h < n / 3) {
            h = 3 * h + 1;
        }
        // 对数组每次按照原先设置的增量进行排序
        while (h >= 1) {
            for (int i = h; i < n; i++) {
                // 对于每一个增量，每相邻的2个数进行比较
                for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) {
                    swap(nums, j, j - h);
                }
            }
            h /= 3;
        }
    }

    public static void swap(int[] nums, int m, int n) {
        int tmp = nums[m];
        nums[m] = nums[n];
        nums[n] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{9, 8, 6, 5, 3, 1, 2};
        //bubbleSort(arr);
        //insertionSort(arr);
        //selectionSort(arr);
        //quickSort(arr, 0, arr.length - 1);
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}