力扣刷题篇之排序算法

系列文章目录

前言

本系列是个人力扣刷题汇总，本文是排序算法。刷题顺序按照[力扣刷题攻略] Re：从零开始的力扣刷题生活 - 力扣（LeetCode）

这个之前写的左神的课程笔记里也有：左程云算法与数据结构代码汇总之排序（Java）-CSDN博客

本来想看按照这个分类一个个解题的，但是好多都不是最优解甚至会超过时间限制，所以要看较为系统一点的排序算法还是看上面那个之前的汇总吧，只是没有希尔排序，看看这个：

【算法】排序算法之希尔排序 - 知乎 (zhihu.com)

其实我有个想法，之后可以看看各个库里面的排序算法里面的源码怎么写的，因为老是想偷懒。。。。

排序的一些基本题

912. 排序数组 - 力扣（LeetCode）

这里虽然写的冒泡排序，但是超出时间复杂度了

冒泡：

class Solution {
    public int[] sortArray(int[] nums) {
        bubbleSort(nums);
        return nums;
    }

    private void bubbleSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    // Swap nums[j] and nums[j + 1]
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}

同样，快排也超过了，很离谱

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }

    private void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(nums, low, high);
            quickSort(nums, low, pivotIndex - 1);
            quickSort(nums, pivotIndex + 1, high);
        }
    }

    private int partition(int[] nums, int low, int high) {
        int pivot = nums[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (nums[j] < pivot) {
                i++;
                swap(nums, i, j);
            }
        }

        swap(nums, i + 1, high);
        return i + 1;
    }

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

希尔排序

可以看【算法】排序算法之希尔排序 - 知乎 (zhihu.com)

public class Solution {
    /**
     * 使用希尔排序对整数数组进行升序排序。
     *
     * @param nums 待排序的整数数组
     * @return 升序排序后的数组
     */
    public int[] sortArray(int[] nums) {
        shellSort(nums);
        return nums;
    }

    /**
     * 希尔排序算法的具体实现。
     *
     * @param arr 待排序的整数数组
     */
    private void shellSort(int[] arr) {
        // 初始化步长
        int step = arr.length;
        step = step >> 1;

        // 根据步长进行希尔排序
        while (step >= 1) {
            for (int count = 0; count < step; count++) {
                // 对每个子数组进行插入排序
                for (int i = step + count; i < arr.length; i += step) {
                    int insert = i;
                    int temp = arr[insert];

                    // 插入排序
                    while (insert > step - 1 && temp < arr[insert - step]) {
                        arr[insert] = arr[insert - step];
                        insert -= step;
                    }
                    arr[insert] = temp;
                }
            }
            // 更新步长
            step = step >> 1;
        }
    }
}

215. 数组中的第K个最大元素 - 力扣（LeetCode）

还得是快排

class Solution {
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private int quickSelect(int[] nums, int left, int right, int target) {
        int index = partition(nums, left, right);
        if (index == target) {
            return nums[index];
        } else {
            return index > target ? 
                quickSelect(nums, left, index - 1, target) : 
                quickSelect(nums, index + 1, right, target);
        }
    }

    private int partition(int[] nums, int left, int right) {
        swap(nums, left, left + new Random().nextInt(right - left + 1));
        int pivot = nums[left];
        while (left < right) {
            while (left < right && nums[right] > pivot) {
                right--;
            }
            if (left < right) {
                nums[left++] = nums[right];
            }
            while (left < right && nums[left] < pivot) {
                left++;
            }
            if (left < right) {
                nums[right--] = nums[left];
            }
        }
        nums[left] = pivot;
        return left;
    }

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