package cn.llnn.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author llnn
 * @create 2019-09-26 18:01
 **/
public class InsertSort {
    public static void main(String[] args) {
        int[] a = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        System.out.println("待排序:" + Arrays.toString(a));
        insertSort(a);
        System.out.println("结果:" + Arrays.toString(a));
    }

    private static void insertSort(int[] a) {
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i;
            while (j > 0 && a[j - 1] > temp) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = temp;
        }

    }

}

package cn.llnn.sort;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author llnn
 * @create 2019-09-26 17:41
 **/
public class BubbleSort {
    public static void main(String[] args) {
        int[] a = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        System.out.println("待排序:" + Arrays.toString(a));
        bubbleSort(a);
        System.out.println("结果:" + Arrays.toString(a));
    }

    private static void bubbleSort(int[] a) {
        for (int i = 0; i <= a.length - 2; i++) {
            for (int j = i + 1; j <= a.length - 1; j++) {
                if (a[i] > a[j]) {
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
}

package cn.llnn.sort;

import java.util.Arrays;

/**
 * 堆排序,最大堆
 *
 * @author llnn
 * @create 2019-09-26 12:57
 **/
public class HeapSort {
    private static int heapSize;

    public static void main(String[] args) {
        int[] a = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        System.out.println("待排序:" + Arrays.toString(a));
        heapSort(a);
        System.out.println("结果:" + Arrays.toString(a));
    }

    private static void heapSort(int[] a) {
        heapSize = a.length;
        buildMaxHeap(a);
        System.out.println("最大堆:" + Arrays.toString(a));
        System.out.println("==============");
        for (int i = a.length - 1; i >= 0; i--) {
            int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            // 调整数组大小
            heapSize--;
            adjustHeap(a, 0);
            System.out.println(Arrays.toString(a));
        }
        System.out.println("==============");
    }

    private static void buildMaxHeap(int[] a) {
        for (int i = heapSize / 2; i >= 0; i--) {
            adjustHeap(a, i);
        }
    }

    private static void adjustHeap(int[] a, int root) {
        int large = root;
        int leftChild = 2 * root + 1;
        int rightChild = 2 * root + 2;
        // 最小堆 a[leftChild] < a[root]
        if (leftChild < heapSize - 1 && a[leftChild] > a[root]) {
            large = leftChild;
        }
        // 最小堆 a[leftChild] < a[root]
        if (rightChild < heapSize - 1 && a[rightChild] > a[large]) {
            large = rightChild;
        }


        if (large != root) {
            int temp = a[root];
            a[root] = a[large];
            a[large] = temp;
            adjustHeap(a, large);
        }
    }
}

package cn.llnn.sort;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author llnn
 * @create 2019-09-23 21:47
 **/
public class MergeSort {

    private static void merge(int[] a, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int l = low;
        // 这里为什么要加1
        int h = mid + 1;
        int k = 0;
        // 为什么要小于等于
        while (l <= mid && h <= high) {
            if (a[l] < a[h]) {
                temp[k++] = a[l++];
            } else {
                temp[k++] = a[h++];
            }

        }
        // 因为要遍历到最后一个元素,所以是小于等于
        while (l <= mid) {
            temp[k++] = a[l++];
        }
        while (h <= high) {
            temp[k++] = a[h++];
        }
        if (temp.length >= 0) {
            System.arraycopy(temp, 0, a, low, temp.length);
        }
        System.out.println(Arrays.toString(a));
    }

    private static void mergeSort(int[] a, int low, int high) {
        /*
          递归实现，自顶向下,between top down merge
         */
        if (low >= high) {
            return;
        }
        int mid = (low + high) / 2;
        // 为啥high是mid,不是mid -1
        mergeSort(a, low, mid);
        mergeSort(a, mid + 1, high);
        merge(a, low, mid, high);
    }

    private static void mergeSort2(int[] a) {
        /*
          非递归,自底向上,bottom up merge sort
         */
        int N = a.length;
        /* 第一层循环 表示归并排序子数组的长度 从1 , 2 , 4 ,8 ..... */
        for (int sz = 1; sz < N; sz *= 2) {
            System.out.println("sz" + sz);
            //第二层循环表示每两个自数组之间归并排序，确定起始和终止INDEX
            for (int lo = 0; lo < N - sz; lo += 2 * sz) {
                System.out.println("low:" + lo + "mid" + (lo + sz - 1) + "high" + Math.min(lo + 2 * sz - 1, N - 1));
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {51, 46, 20, 18, 65, 97, 82, 30, 77, 50};
        mergeSort(a, 0, a.length - 1);
//        mergeSort2(a);
        System.out.println("排序结果：" + Arrays.toString(a));
    }

}