快速排序

快排思想比较好理解, 每次找到一个元素的最终位置, 并把所有小于这个元素的值放在左边, 所有大于这个元素的值放在右边.

public static void quickSort(int[] nums) {
    if (nums == null || nums.length < 2) {
        return;
    }
    quickSortCore(nums, 0, nums.length - 1);
}

private static void quickSortCore(int[] nums, int low, int high) {
    if (low <= high) {
        int pivot = nums[low];
        int i = low, j = high;
        while (i < j) {
            while (i < j && nums[j] >= pivot) {
                --j;
            }
            nums[i] = nums[j];
            while (i < j && nums[i] <= pivot) {
                ++i;
            }
            nums[j] = nums[i];
        }
        nums[i] = pivot;
        quickSortCore(nums, low, i - 1);
        quickSortCore(nums, i + 1, high);
    }
}

/**
* 无监督快排 (无监督思想可以在很多算法场景进行优化)
*/
private static void ungradedQuickSort(int[] nums, int low, int high) {
    if (low >= high) return;

    int pivot = nums[low + high >> 1];
    int i = low - 1, j = high + 1;
    while (i < j) {
        do i++; while (nums[i] < pivot);
        do j--; while (nums[j] > pivot);
        if (i < j) swap(nums, i, j);
    }
    ungradedQuickSort(nums, low, j);
    ungradedQuickSort(nums, j + 1, high);
}

/**
* 无监督快速排序 + 单边递归优化
*/
private static void ungradedQuickSort2(int[] nums, int low, int high) {
    while (low < high) {
        int pivot = nums[low];
        int i = low, j = high;
        do {
            while (nums[i] < pivot) ++i;
            while (nums[j] > pivot) --j;
            if (i <= j) {
                swap(nums, i, j);
                ++i;
                --j;
            }
        } while (i < j);
        ungradedQuickSort2(nums, low, j);
        low = i; // 单边递归优化
    }
}

堆排序

堆排的过程主要分为两步, 第一步初始化堆, 从最后一个非叶子节点开始从后往前做堆化调整, 第二步是将堆头与堆尾元素交换, 从而确定得到一个最大数或者最小数(所确定的数不参与下次迭代), 依次迭代到堆只剩最后一个元素即可.

public static void heapSort(int[] nums) {
    if (nums == null || nums.length < 2) {
        return;
    }
    int n = nums.length;
    for (int i = n / 2 - 1; i >= 0; --i) {
        heapify(nums, i, n);
    }
    for (int i = n - 1; i > 0; --i) {
        swap(nums, 0, i);
        heapify(nums, 0, i);
    }
}

private static void heapify(int[] nums, int parent, int len) {
    int child = parent * 2 + 1;
    while (child < len) {
        if (child + 1 < len && nums[child] < nums[child + 1]) {
            ++child;
        }
        if (nums[parent] >= nums[child]) {
            break;
        } else {
            swap(nums, parent, child);
            parent = child;
        }
    }
}

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

归并排序

归并的思想就是分治, 大问题化为小问题, 大数组化为小数组, 每个子问题都是将数组一分为两个有序数组, 然后再按序合并.
下面的代码是逆序对题目的代码, 是基于归并排序的, 代码只多了一个判断.

// 统计逆序对个数
private static int cnt = 0;
public static void mergeSort(int[] nums) {
    if (nums == null || nums.length < 2) {
        return;
    }
    mergeSort(nums, 0, nums.length - 1);
}

private static void mergeSort(int[] nums, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, high);
    }
}

private static void merge(int[] nums, int low, int high) {
    int[] help = new int[high - low + 1];
    int mid = low + (high - low) / 2;
    int i = 0, left = low, right = mid + 1;
    while (left <= mid && right <= high) {
        if (nums[right] < nums[left]) {
            // 这个判断是为了统计逆序对个数，单纯归并排序并不需要
            cnt += mid - left + 1;
        }
        // 相等情况取左边是为了方便统计逆序对
        help[i++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
    }
    while (left <= mid) {
        help[i++] = nums[left++];
    }
    while (right <= high) {
        help[i++] = nums[right++];
    }
    for (int j = 0; j < i; ++j) {
        nums[low + j] = help[j];
    }
}

总结

• 三个 nlogn 的排序算法需要熟记, 面试经常让手撕代码.

• 常见排序算法的总结
  

• 工程中的排序算法结合了多种排序算法的特点, 下图是 Java 中的 sort 函数选择合适排序算法的逻辑.