Sort

todo

• 桶排序

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 复习排序算法
 */
public class Sort {
    //比较类排序-------------------------------------------------------------
    //交换类----------------------

    /**
     * 冒泡排序(稳定)：每次走完一趟，最大的值就会到最后
     *
     * @param arr 数组
     */
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean flag;
        for (int i = 0; i < n - 1; i++) {
            flag = true;
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    flag = false;
                    swap(arr, j, j + 1);
                }
            }
            if (flag) break;
        }
    }

    /**
     * 快速排序(不稳定)
     *
     * @param arr 数组
     */
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int index = partition(arr, left, right);
            quickSort(arr, left, index - 1);
            quickSort(arr, index + 1, right);
        }
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int index = left + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < pivot) {
                swap(arr, i, index);
                ++index;
            }
        }
        swap(arr, left, index - 1);
        return index - 1;
    }
    //插入类---------------------

    /**
     * 插入排序
     *
     * @param arr 数组
     */
    public static void insertSort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            while (j > 0 && arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
                j--;
            }
        }
    }

    /**
     * 希尔排序
     *
     * @param arr 数组
     */
    public static void shellSort(int[] arr) {
        int len = arr.length;
        for (int gap = len / 2; gap > 0; gap = gap / 2) {
            for (int i = gap; i < len; i++) {
                int j = i;
                int cur = arr[i];
                while (j >= gap && cur < arr[j - gap]) {
                    arr[j] = arr[j - gap];
                    j = j - gap;
                }
                arr[j] = cur;
            }
        }
    }

    //选择类---------------------
    //选择排序
    public static void selectSort(int[] arr) {
        int len = arr.length;
        int minIndex;
        for (int i = 0; i < len - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;
            }
            swap(arr, i, minIndex);
        }
    }

    // 堆排序
    public static void heapify(int[] tree, int n, int i) {
        if (i >= n) return;
        int max = i;
        int c1 = 2 * i + 1, c2 = 2 * i + 2;
        if (c1 < n && tree[c1] > tree[max]) max = c1;
        if (c2 < n && tree[c2] > tree[max]) max = c2;
        if (max != i) {
            swap(tree, max, i);
            heapify(tree, n, max);
        }
    }

    public static void buildHeap(int[] arr) {
        int len = arr.length;
        int last_parent = (len) / 2;
        for (int i = last_parent; i >= 0; --i) {
            heapify(arr, len, i);
        }
    }

    public static void heapSort(int[] arr) {
        int len = arr.length;
        buildHeap(arr);
        for (int i = len - 1; i >= 0; --i) {
            swap(arr,0,i);
            heapify(arr,i,0);
        }
    }

    //归并类---------------------
    //归并
    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        int[] tmp = new int[right - left + 1];
        int index = 0, index1 = left, index2 = mid + 1;
        while (index1 <= mid && index2 <= right) {
            if (arr[index1] < arr[index2]) {
                tmp[index++] = arr[index1++];
            } else tmp[index++] = arr[index2++];
        }
        while (index1 <= mid) tmp[index++] = arr[index1++];
        while (index2 <= right) tmp[index++] = arr[index2++];
        System.arraycopy(tmp, 0, arr, left, tmp.length);
    }


    //非比较排序--------------------------------------------------------------
    //计数排序
    public static void countingSort(int[] arr, int maxValue) {
        int[] counts = new int[maxValue + 1];
        for (int i : arr) {
            counts[i]++;
        }
        int index = 0;
        for (int i = 0; i < maxValue + 1; i++) {
            int count = counts[i];
            while (count > 0) {
                count--;
                arr[index++] = i;
            }
        }
    }

    //TODO 桶排序
    public static void bucketSort(int[] arr, int bucketSize) {
        int maxValue = arr[0], minValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxValue) maxValue = arr[i];
            else if (arr[i] < minValue) minValue = arr[i];
        }
        int bucketCount = (maxValue - minValue) / bucketSize + 1;

    }

    //基数排序
    public static void radixSort(int[] arr, int maxDigit) {
        Map<Integer, Queue<Integer>> map = new HashMap<>();
        int mod = 10, dev = 1;
        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            for (int value : arr) {
                int bucket = (value % mod) / dev;
                if (!map.containsKey(bucket)) {
                    map.put(bucket, new LinkedList<>());
                }
                map.get(bucket).add(value);
            }
            int pos = 0;
            for (int j = 0; j < 10; j++) {
                if (map.containsKey(j)) {
                    int len = map.get(j).size();
                    for (int k = 0; k < len; k++) {
                        arr[pos++] = map.get(j).poll();
                    }
                }
            }
        }
    }

    /**
     * 交换数组的值
     *
     * @param arr 数组
     * @param i   下标
     * @param j   另一个下标
     */
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 4, 5, 11, 2};
//        Sort.radixSort(arr, 2);
        heapSort(arr);
        for (int i : arr) {
            System.out.printf("%d ", i);
        }
    }
}