package com.algorithm;

import java.util.Arrays;

public class SortRunner {
    public static void main(String args[]) {

        // int data[] = new int[] { 12, 5, 9, 8, 16, 3, 1, 7, 4, 0, 11, 2,
        // 19,
        // 14, 13, 15, 6, 18, 20, 17, 10 };

        long baseSize = 1000000L;
        int n = (int) (Math.random() * baseSize);
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = (int) (Math.random() * baseSize);
        }

        int[] commonData = data.clone();
        long commonBefore = System.currentTimeMillis();
        // commonSort(commonData);
        long commonAfter = System.currentTimeMillis();
        System.out.println("CommonSort " + (commonAfter - commonBefore));

        int[] quickData = data.clone();
        long quickBefore = System.currentTimeMillis();
        quickSort(quickData, 0, quickData.length - 1);
        long quickAfter = System.currentTimeMillis();
        System.out.println("QuickSort " + (quickAfter - quickBefore));

        int[] shellData = data.clone();
        long shellBefore = System.currentTimeMillis();
        shellSort(shellData);
        long shellAfter = System.currentTimeMillis();
        System.out.println("ShellSort " + (shellAfter - shellBefore));

        int[] mergeData = data.clone();
        long mergeBefore = System.currentTimeMillis();
        mergeSort(mergeData, 0, mergeData.length - 1);
        long mergeAfter = System.currentTimeMillis();
        System.out.println("MergeSort " + (mergeAfter - mergeBefore));

        int[] heapData = data.clone();
        long heapBefore = System.currentTimeMillis();
        heapSort(heapData);
        long heapAfter = System.currentTimeMillis();
        System.out.println("HeapSort " + (heapAfter - heapBefore));

        System.out.println();

        // print(data);
        // print(commonData);
        // print(quickData);
        // print(shellData);
        // print(mergeData);
        // print(heapData);
    }

    /**
     * 冒泡排序
     */
    public static void commonSort(int[] data) {
        for (int i = 0; i < data.length; i++) {
            for (int j = 0; j < i; j++) {
                if (data[j] > data[i]) {
                    int temp = data[j];
                    data[j] = data[i];
                    data[i] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     */
    public static void quickSort(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }
        int n = data[left];
        int l = left;
        int r = right;

        while (l < r) {
            while (data[r] >= n && l < r) {
                --r;
            }
            data[l] = data[r];

            while (data[l] <= n && l < r) {
                ++l;
            }
            data[r] = data[l];
        }
        data[r] = n;
        quickSort(data, left, r - 1);
        quickSort(data, r + 1, right);
    }

    /**
     * 希尔排序
     */
    public static void shellSort(int[] data) {
        int length = data.length;
        int n = length;
        while ((n = n / 2) >= 1) {
            for (int i = 0; i < n; i++) {
                for (int j = i; j < length; j += n) {
                    int k = j;
                    while (k >= 0 && k + n < length && data[k] > data[k + n]) {
                        int temp = data[k + n];
                        data[k + n] = data[k];
                        data[k] = temp;
                        k -= n;
                    }
                }
            }
        }
    }

    /**
     * 合并排序
     */
    public static void mergeSort(int[] data, int left, int right) {
        if (left >= right) {
            return;
        }

        int middle = (left + right) / 2;
        mergeSort(data, left, middle);
        mergeSort(data, middle + 1, right);

        int[] temp = new int[right - left + 1];

        int i = left;
        int j = middle + 1;
        int k = 0;
        while (k <= right) {
            if (i > middle) {
                while (j <= right) {
                    temp[k++] = data[j++];
                }
                break;
            } else if (j > right) {
                while (i <= middle) {
                    temp[k++] = data[i++];
                }
                break;
            }
            if (data[i] < data[j]) {
                temp[k++] = data[i++];
            } else {
                temp[k++] = data[j++];
            }
        }
        k = 0;
        for (i = left; i <= right; i++) {
            data[i] = temp[k++];
        }
    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] data) {
        int length = data.length;

        // 建堆
        for (int i = length / 2 - 1; i >= 0; i--) {
            adjustHeap(i, data, length);
        }

        for (int i = length - 1; i >= 0; i--) {
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;
            adjustHeap(0, data, i);
        }
    }

    private static void adjustHeap(int parent, int[] data, int length) {
        int left = parent * 2 + 1;
        int right = left + 1;
        int max_index = parent;
        if (left < length && data[left] > data[max_index]) {
            max_index = left;
        }
        if (right < length && data[right] > data[max_index]) {
            max_index = right;
        }
        if (max_index != parent) {
            int temp = data[parent];
            data[parent] = data[max_index];
            data[max_index] = temp;
            adjustHeap(max_index, data, length);
        }
    }

    public static void print(int[] data, int left, int right) {
        for (int i = left; i <= right; i++) {
            System.out.print(data[i] + " ");
        }
        int[] array = new int[] { 1, 2, 3, 4 };
        Arrays.sort(array);
        System.out.println();
    }

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