整理下常见的排序算法

import java.util.Arrays;
import java.util.Stack;

public class Sort {
    public static void main(String args[]) {
        int[] arr = { 2, 1, 5, 7, 8, 9, 6, 4, 3, 0 };
        HeapSort.sort(arr);
        Arrays.stream(arr).forEach(x -> System.out.print(x + " "));
    }

    /**
     * 冒泡排序
     * 
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int len = arr.length;
        // 冒泡趟数
        for (int i = 0; i < len - 1; ++i) {
            // 每趟都把最大的数浮上去
            for (int j = 0; j < len - i - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    arr[j] ^= arr[j + 1];
                    arr[j + 1] ^= arr[j];
                    arr[j] ^= arr[j + 1];
                }
            }
        }
    }

    /**
     * 选择排序
     * 
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        int len = arr.length;
        // 排序趟数，间接表示已经有序数的个数
        for (int i = 0; i < len; ++i) {
            // 每趟找到最小的数，放在下标i上
            for (int j = i + 1; j < len; ++j) {
                if (arr[i] > arr[j]) {
                    arr[i] ^= arr[j];
                    arr[j] ^= arr[i];
                    arr[i] ^= arr[j];
                }
            }
        }
    }

    /**
     * 快速排序 - 递归实现 (直接交换法,还有个挖坑法,思想一样的)
     * 
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }
        // 左右指针
        int l = left, r = right;
        // 基准数，默认第一个数
        int std = arr[left];
        // 循环直到指针相遇
        while (l != r) {
            // 先从右指针开始，保证相遇时所指的数比基准数小，直接交换
            for (; arr[r] >= std && l < r; --r);
            for (; arr[l] <= std && l < r; ++l);
            if (l < r) {
                arr[l] ^= arr[r];
                arr[r] ^= arr[l];
                arr[l] ^= arr[r];
            }
        }
        // 相遇时的数必然比基准数小，直接交换
        arr[left] = arr[l];
        arr[l] = std;
        // 左右递归分治
        quickSort(arr, left, l - 1);
        quickSort(arr, l + 1, right);
    }

    /**
     * 快速排序 - 非递归实现
     * 
     * @param arr
     */
    public static void quickSortNoRecursion(int[] arr) {
        int len = arr.length;
        Stack<Integer> func = new Stack<>();
        // 参数入栈
        func.push(0);
        func.push(len - 1);
        int left, right;
        // 模拟函数栈调用
        while (!func.isEmpty()) {
            right = func.pop();
            left = func.pop();
            if (left < right) {
                int std = arr[left];
                int l = left, r = right;
                while (l != r) {
                    for (; arr[r] >= std && l < r; --r);
                    for (; arr[l] <= std && l < r; ++l);
                    if (l < r) {
                        arr[l] ^= arr[r];
                        arr[r] ^= arr[l];
                        arr[l] ^= arr[r];
                    }
                }
                arr[left] = arr[l];
                arr[l] = std;
                // 注意入参顺序
                func.push(l + 1);
                func.push(right);
                func.push(left);
                func.push(l - 1);
            }
        }
    }

    /**
     * 归并排序
     * 
     * @author Qug_
     *
     */
    public static class MergeSort {
        static int[] tmp;

        static void sort(int[] arr) {
            int len = arr.length;
            tmp = new int[len];
            sort(arr, 0, len - 1);
        }

        static void sort(int[] arr, int left, int right) {
            if (left < right) {
                int mid = (left + right) / 2;
                sort(arr, left, mid);
                sort(arr, mid + 1, right);
                merge(arr, left, mid, right);
            }
        }

        static void merge(int[] arr, int left, int mid, int right) {
            int l = left;
            int r = mid + 1;
            int tmpIndex = 0;
            while (l <= mid && r <= right) {
                if (arr[l] <= arr[r]) {
                    tmp[tmpIndex++] = arr[l++];
                } else {
                    tmp[tmpIndex++] = arr[r++];
                }
            }
            while (l <= mid) {
                tmp[tmpIndex++] = arr[l++];
            }
            while (r <= right) {
                tmp[tmpIndex++] = arr[r++];
            }
            tmpIndex = 0;
            while (left <= right) {
                arr[left++] = tmp[tmpIndex++];
            }
        }
    }

    /**
     * 插入排序
     * 
     * @param arr
     */
    public static void insertionSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; ++i) {
            for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; --j) {
                arr[j] ^= arr[j + 1];
                arr[j + 1] ^= arr[j];
                arr[j] ^= arr[j + 1];
            }
        }
    }

    /**
     * 堆排序
     * 
     * @author Qug_
     *
     */
    public static class HeapSort {
        static void sort(int arr[]) {
            heapInsert(arr);
            int size = arr.length;
            while (size > 1) {
                // 将范围内最大的数放到后边
                swap(arr, 0, size - 1);
                --size;
                heapify(arr, 0, size);
            }
        }

        /**
         * 建大根堆
         * 
         * @param arr
         */
        static void heapInsert(int[] arr) {
            for (int i = 0; i < arr.length; ++i) {
                int curIndex = i;
                int fatherIndex = (curIndex - 1) / 2;
                while (arr[curIndex] > arr[fatherIndex]) {
                    swap(arr, curIndex, fatherIndex);
                    curIndex = fatherIndex;
                    fatherIndex = (curIndex - 1) / 2;
                }
            }
        }

        /**
         * 调整大根堆
         * 
         * @param arr
         * @param index
         * @param size
         */
        static void heapify(int[] arr, int index, int size) {
            int left = (index * 2) + 1;
            int right = (index * 2) + 2;
            while (left < size) {
                int largeIndex;
                // 顺序不能倒
                if (arr[left] < arr[right] && right < size) {
                    largeIndex = right;
                } else {
                    largeIndex = left;
                }
                if (arr[largeIndex] < arr[index]) {
                    largeIndex = index;
                    break;
                }
                // 父节点不是最大的，调整最大堆
                swap(arr, largeIndex, index);
                index = largeIndex;
                left = (index * 2) + 1;
                right = (index * 2) + 2;
            }
        }

        static void swap(int[] arr, int a, int b) {
            arr[a] ^= arr[b];
            arr[b] ^= arr[a];
            arr[a] ^= arr[b];
        }
    }
}