6种常见排序算法实现

import java.util.Arrays;


/**
 * 解法1：冒泡排序
 * 解法2：插入排序
 * 解法3：选择排序
 * 解法4：归并排序
 * 解法5：快速排序
 * 解法6：堆排序
 */
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] sortArray(int[] nums) {
        return mergeSort(nums);
    }

    /**
     * 解法1：冒泡排序
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 原地排序，稳定排序
     */
    public int[] bubbleSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {           // 两两相邻比较，最多比较n-1次
            for (int j = 0; j < n - 1 - i; j++) {   // 比较的元素从后向前越来越少
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
        return nums;
    }

    /**
     * 解法1.1：冒泡排序优化
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 原地排序，稳定排序
     * #思路
     * 如果某一轮所有元素都没有发生交换，那么后续也不需要交换了，使用一个isSorted变量来判断
     */
    public int[] bubbleSort2(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {           // 两两相邻比较，最多比较n-1次
            boolean isSorted = true;
            for (int j = 0; j < n - 1 - i; j++) {   // 比较的元素从后向前越来越少
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
        return nums;
    }

    /**
     * 解法2：插入排序
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 原地排序，稳定排序
     * #思路
     * 遍历未排序区间的元素(外层)在已排序区间（从后向前遍历）找到对应的位置插入；
     * 如果已经排序好，后面的元素只需要和已排序区间的末尾元素作一次比较；
     */
    public int[] insertionSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int n = nums.length;

        for (int i = 1; i < n; i++) {
            int num = nums[i];
            int j = i - 1;  // 定义在外面，方便最后一步交换

            for (; j >= 0 && nums[j] > num; j--) {  // 所有比当前元素大的元素后移一位空出位置，这里比较的核心元素是相邻的后一个元素
                nums[j + 1] = nums[j];
            }
            nums[j + 1] = num;  // 注意j=0并且j--之后j=-1，所以这里使用j+1
        }
        return nums;
    }

    /**
     * 解法3：选择排序
     * 时间复杂度 O(n^2)
     * 空间复杂度 O(1)
     * 原地排序，不稳定的排序算法
     * #思路
     * 在未排序区间选择一个最小的元素插入到已排序区间的末尾；
     * 即使已经排序好，还是需要遍历比较后面的所有元素才能拿到最小元素；
     */
    public int[] selectionSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int min = i;    // 找到未排序区间最小的元素下标，用于和已排序区间的末尾作交换

            for (int j = i + 1; j < n; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }

            if (i != min) {
                swap(nums, i, min);
            }
        }
        return nums;
    }

    /**
     * 解法4：归并排序
     * 时间复杂度 O(nlog(n))
     * 空间复杂度 O(n)
     * 非原地排序，稳定的排序算法
     * #思路
     * 先分解成小问题，执行递归，到最后执行两个最小已排序数组的合并；
     * 临时数组的目的在于存放两个已排序数组合并后的数据；
     */
    public int[] mergeSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int n = nums.length;
        int[] temp = new int[nums.length];
        doMegeSort(nums, 0, n - 1, temp);
        return nums;
    }

    // 分治处理
    private void doMegeSort(int[] nums, int p, int q, int[] temp) {
        if (p >= q) {
            return;
        }
        int mid = p + ((q - p) >> 1);
        doMegeSort(nums, p, mid, temp);
        doMegeSort(nums, mid + 1, q, temp);

        // 可以提前退出
        if (nums[mid] <= nums[mid + 1]) {
            return;
        }

        mergeTwoSortedArr2(nums, p, mid + 1, q, temp);
    }

    // 合并两个有序数组 方式1
    private void mergeTwoSortedArr1(int[] nums, int p, int mid, int q, int[] temp) {
        int tempIndex = p;
        int tempLength = q - p + 1;
        int pEnd = mid - 1;
        int qStart = mid;

        while (p <= pEnd && qStart <= q) {
            if (nums[p] < nums[qStart]) {
                temp[tempIndex++] = nums[p++];
            } else {
                temp[tempIndex++] = nums[qStart++];
            }
        }
        while (p <= pEnd) {
            temp[tempIndex++] = nums[p++];
        }
        while (qStart <= q) {
            temp[tempIndex++] = nums[qStart++];
        }

        for (int i = 0; i < tempLength; i++) {
            nums[q - i] = temp[q - i];
        }
    }

    // 合并两个有序数组 方式2 参考 [剑指 Offer 51]数组中的逆序对
    private void mergeTwoSortedArr2(int[] nums, int l, int mid, int r, int[] temp) {

        mid = mid - 1;
        for (int i = l; i <= r; i++) {
            temp[i] = nums[i];
        }

        int i = l;
        int j = mid + 1;

        int idx = l;
        while (i <= mid || j <= r) {
            if (i == mid + 1) {
                nums[idx++] = temp[j++];
            } else if (j == r + 1) {
                nums[idx++] = temp[i++];
            } else if (temp[i] <= temp[j]) {
                nums[idx++] = temp[i++];
            } else {
                nums[idx++] = temp[j++];
            }
        }
    }
    
    /**
     * 解法5：快速排序
     * 时间复杂度 O(nlog(n))
     * 空间复杂度 O(logn)
     * 原地排序，不稳定的排序算法
     * 分区算法的时间复杂度 partition1 <= partition2 < partition3
     * #思路
     * 选择一个分区，找到这个分区的合适位置，然后从这个合适位置向左和向右扩展，分解成子问题
     */
    public int[] quickSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        int n = nums.length;
        doQuickSort(nums, 0, n - 1);
        return nums;
    }

    // 递归实现
    private void doQuickSort(int[] nums, int p, int q) {
        if (p >= q) {
            return;
        }
        int pivot = partition2(nums, p, q);
        doQuickSort(nums, p, pivot - 1);
        doQuickSort(nums, pivot + 1, q);
    }

    // partition实现方式1
    private int partition1(int[] nums, int p, int q) {
        int num = nums[p];  // 选择一个分区元素，这里选择p处的元素
        while (p < q) {
            while (p < q && nums[q] >= num) {   // 因为选择了p元素，所以先从q元素开始处理，下面用p处元素替换q处元素
                q--;
            }
            nums[p] = nums[q];
            while (p < q && nums[p] <= num) {
                p++;
            }
            nums[q] = nums[p];
        }
        nums[p] = num;
        return p;
    }

    // partition实现方式2
    private int partition2(int[] nums, int p, int q) {
        int num = nums[p];  // 选择一个分区元素，这里选择p处的元素
        while (p < q) {
            while (p < q && nums[q] >= num) {
                q--;
            }
            swap(nums, p, q);
            while (p < q && nums[p] <= num) {
                p++;
            }
            swap(nums, p, q);
        }
        return p;
    }

    // 定义一个分区元素，遍历未排序区间，找到所有比这个分区元素小的元素和"已排序区间"的末尾交换
    // 有点类似于插入排序，但是这里的"已排序区间"是比分区元素小的元素，并不一定有序
    private int partition3(int[] nums, int p, int q) {
        int num = nums[q];  // 选取一个分区元素
        int i = p;  // "已排序区间"的末尾

        for (int j = p; j < q; j++) {       // 这里是<，q定义为分区元素，本身没有比较的必要
            if (nums[j] < num) {
                swap(nums, i, j);
                i++;    // 维护已排序区间的末尾
            }
        }
        swap(nums, i, q);
        return i;
    }

    /**
     * 解法6：堆排序
     * 时间复杂度 O(nlog(n))
     * 空间复杂度 O(n)
     * 原地排序，不稳定的排序算法
     * 对比快速排序，数据是跳着访问的，所以对于cpu缓存不友好
     * #思路
     * 分为建堆(O(n)复杂度)和排序(On(logn))两个过程
     * 建堆：构建一个大顶堆，将n/2-1的元素和0的元素向下堆化
     * 排序：从数组的末尾开始遍历，将堆顶元素和末尾元素替换，并且对堆顶元素进行向下堆化
     */
    public int[] heapSort(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return nums;
        }
        buildMaxHeap(nums);

        int len = nums.length - 1;      // 比较n-1次
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);
            maxHeapify(nums, len, 0);
            len--;
        }
        return nums;
    }

    // 建堆 O(n)
    private void buildMaxHeap(int[] nums) {
        int n = nums.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, n, i);
        }
    }

    // 向下堆化，注意这里的n是最后一个元素的位置
    private void maxHeapify(int[] nums, int n, int parent) {
        while (true) {
            int maxPos = parent;
            int leftChild = 2 * parent + 1;
            if (leftChild < n && nums[leftChild] > nums[maxPos]) {
                maxPos = leftChild;
            }
            int rightChild = 2 * parent + 2;
            if (rightChild < n && nums[rightChild] > nums[maxPos]) {
                maxPos = rightChild;
            }
            if (maxPos == parent) {
                break;
            }
            swap(nums, maxPos, parent);
            parent = maxPos;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}