import java.util.Stack;

public class ArraySort {
    /*
        冒泡排序：
        时间复杂度： 最好，最差，平均都是：O(n^2)
        空间复杂度： 由于是in-place，故O(1)
        稳定
     */
    public static void bubbleSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }

    /*
        插入排序：
        时间复杂度： 最好：O(n)  最差：O(n^2)  平均：O(n^2)
                   最好情况为已经排序，每个元素只需比较一次即可
                   最差情况为倒序
        空间复杂度： O(1)
        稳定
     */
    public static void insertSort(int[] a) {
        if (a.length <= 1) return;
        int len = a.length;
        for (int i = 1; i < len; i++) {
            // 下一个for循环中j > 0的判断条件是可以的，因为
            for (int j = i;  j > 0 && a[j-1] > a[j]; j--) {
                swap(a, j-1, j);
            }
        }
    }

    /*
        希尔排序：
        时间复杂度： 平均：O(n^1.3)
        空间复杂度： O(1)
        不稳定。例如[7, 5, 5, 8]，第一次时比较第二个5和7交换
     */
    public static void shellSort(int[] a) {
        if (a.length <= 1) return;
        int len = a.length;
        int h = 1;
        while (h < len/3) {
            h = h*3+1;
        }

        // 注意：这里h >= 1，有等号。因为当h=1时，退化为直接插入排序
        while (h >= 1) {
            for (int i = h; i < len; i++) {
                for (int j = i; j-h >= 0 && a[j-h] > a[j]; j = j-h) {
                    swap(a, j, j-h);
                }
            }
            h = h/3;
        }
    }


    /*
        选择排序：
        时间复杂度： 最好，最差，平均都是O(n^2)
        空间复杂度： O(1)
        不稳定。例如[5, 4, 5, 2, 9]，第一次选择最小的2和前面的5进行交换
     */
    public static void selectSort(int[] a) {
        int len = a.length;
        // 每次找到最小的放在前面，共需a.length次
        for (int i = 0; i < len; i++) {
            int min = i;
            // 每轮比较时比上一轮次数少1
            for (int j = i+1; j < len; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            // 由于最小的和前面的进行了交换，所以不稳定
            swap(a, min, i);
        }
    }

    /*
        堆排序：
        时间复杂度： 最好，最差，平均都是O(nlogn)
        空间复杂度： O(1)
        不稳定。例如[36, 27, 27(2), 3].已经是大根堆，如下：
                36
               /  \
              27  27(2)
             /
            3
        第一次交换3和36，输出36。此时3在堆顶，不符合大根堆定义，将3下沉，
        与27交换得到新的大根堆：
                27
               /  \
              3   27(2)

           36
        第二次交换27(2)和27，输出27，此时27(2)在堆顶，符合大根堆，无需调整：
               27(2)
               /
              3    27

            36
        第三次交换27(2)和3，输出27(2)，此时只剩3一个节点。最终输出如下：
                3

            27(2)    27

          36
        即最终排序结果是[3, 27(2), 27, 36]。可见两个27与排序之前的位置不同。
        故堆排序不稳定。
     */
    public static void heapSort(int[] a) {
        int len = a.length;
        // len/2-1是最后一个非叶子节点的位置，注意这里的len指的是节点个数
        // 而非最后一个元素的下标
        for (int i = len/2-1; i >= 0; i--) {
            adjustHeap(a, i, len); // 每次要从0~len-1进行调整
        }

        for (int i = len-1; i > 0; i--) {
            swap(a, 0, i);
            adjustHeap(a, 0, i);  // 第一次调整的范围是0~len-2，因为len-1已经和0交换过了
        }
    }

    /**
     *
     * @param a 数组
     * @param i 要从第i个节点下沉调整
     * @param len 调整范围右界，不包括len
     */
    public static void adjustHeap(int[] a, int i, int len) {
        int tmp = a[i];
        for (int k = 2*i+1; k < len; k = k*2+1) {
            if (k+1 < len && a[k] < a[k+1]) { // 左子节点小于右子节点，k指向右子节点
                k++;
            }

            if (a[k] > tmp) { // 如果子节点比父节点大
                // 其实下面应该交换a[i]与a[k]，即a[i] = a[k], a[k] = tmp
                // 如果这样的话，将if从句中的判断条件改为a[k] > a[i]更容易理解
                // 但如果下一次又需要交换的话，这次的a[k] = tmp相当于白执行了
                // i在这里每次调整，相当于往下走，每次的i为交换后的子节点下标
                // 因此用tmp来记录父节点的值，直到不需要交换时，再将tmp赋值给a[i]
                a[i] = a[k];  // 将子的节点的值赋给根节点，之后继续看子节点的子节点是否符合要求
                i = k; // 从这里可以看出调整大顶堆是从上至下的一个过程
            } else {
                break; // 如果该节点没有任何问题，则退出循环。即堆调整的前提是子堆都是正确的
            }
        }
        a[i] = tmp; // 调整结束后，将tmp放回结束为止
    }

    /*
        归并排序：
        时间复杂度： 最好，最差，平均都是O(nlogn)
        空间复杂度： O(n) 因为要用到数组来暂存归并元素
     */
    public static void mergeSort(int[] a) {
        mergeSort(a, 0, a.length-1);
    }

    public static void mergeSort(int[] a, int l, int r) {
        if (l < r) {
            int mid = (l+r)/2;
            mergeSort(a, l, mid);
            mergeSort(a, mid+1, r);
            merge(a, l, mid, r);
        }
    }

    public static void merge(int[] a, int l, int mid, int r) {
        int[] tmp = new int[r-l+1];
        int i = l;
        int j = mid+1;
        int t = 0;
        while (i <= mid && j <= r) {
            tmp[t++] = a[i] <= a[j] ? a[i++] : a[j++];
        }

        while (i <= mid) {
            tmp[t++] = a[i++];
        }

        while (j <= r) {
            tmp[t++] = a[j++];
        }

        t = 0;
        while (l <= r) {
            a[l++] = tmp[t++];
        }
    }

    public static void mergeSortIterative(int[] a) {
        if (a == null || a.length <= 1) {
            return;
        }
        int len = a.length;
        for (int size = 1; size < len; size = size+size) {
            for (int low = 0; low < len-size; low = low+2*size) {
                merge(a, low, low+size-1, Math.min(low+2*size-1, len-1));
            }
        }
    }


    public static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    /*
        快速排序
        时间复杂度：最好：O(nlogn)   最差：O(n^2)   平均：  O(nlogn)
                  最差情况对应于正序和逆序
                  如果数组所有元素都相同，则在findPivot中进行比较时，
                  遇到和a[left]相等的元素也交换，可以避免最差情况发生
        空间复杂度：O(logN)
     */
    public static void quickSortIterative(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(a.length-1);
        stack.push(0);
        while (!stack.isEmpty()) {
            int left = stack.pop();
            int right = stack.pop();
            int pivot = findPivot(a, left, right);
            if (pivot+1 < right) {
                stack.push(right);
                stack.push(pivot+1);
            }
            if (left < pivot-1) {
                stack.push(pivot-1);
                stack.push(left);
            }
        }
    }

    public static void quickSort(int[] a) {
        if (a == null || a.length == 0) {
            return;
        }
        quickSort(a, 0, a.length-1);
    }

    public static void quickSort(int[] a, int left, int right) {
        if (left < right) {
            int pivot = findPivot(a, left, right);
            quickSort(a, left, pivot-1);
            quickSort(a, pivot+1, right);
        }
    }

    public static int findPivot(int[] a, int left, int right) {
        int i = left;
        int j = right;
        int tmp = a[left];
        while (i < j) {
            while (i < j && a[j] > tmp) {
                j--;
            }
            if (i < j) {
                a[i++] = a[j];
            }
            while (i < j && a[i] < tmp) {
                i++;
            }
            if (i < j) {
                a[j--] = a[i];
            }
        }
        a[i] = tmp;
        return i;
    }

    public static void showArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = new int[]{6, 4, 7, 3, 9, 1, 0, 2};
        bubbleSort(arr);
        showArray(arr);
        arr = new int[]{6, 4, 7, 3, 9, 1, 0, 2};
        insertSort(arr);
        showArray(arr);
        arr = new int[]{6, 4, 7, 3, 9, 1, 0, 2};
        shellSort(arr);
        showArray(arr);
        arr = new int[]{6, 4, 7, 3, 9, 1, 0, 2};
        selectSort(arr);
        showArray(arr);
        arr = new int[]{6, 4, 7, 3, 9, 1, 4, 0, 2, 11, 5};
        heapSort(arr);
        System.out.println("Heap sort:");
        showArray(arr);
        arr = new int[]{6, 4, 7, 3, 9, 1, 0, 2};
        mergeSortIterative(arr);
        showArray(arr);
        arr = new int[]{6, 4, 7, 3, 9, 1, 4, 0, 2, 11, 5};
        quickSort(arr);
        showArray(arr);
    }
}