排序算法

排序算法

    public static int[] swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return nums;
    }

• 快速排序

    /**
     * 快速排序
     * <p>
     * 核心的思路是取第一个元素（或者最后一个元素）作为分界点，把整个数组分成左右两侧，左边的元素小于或者等于分界点元素，
     * 而右边的元素大于分界点元素，然后把分界点移到中间位置，对左右子数组分别进行递归，最后就能得到一个排序完成的数组。
     * 当子数组只有一个或者没有元素的时候就结束这个递归过程。
     */
    public static void quickSort(int[] nums, int left, int right) {
        if (left > right) return;
        int key = nums[left];
        int l = left;
        int r = right;
        while (l < r) {
            while (nums[r] >= key && l < r)
                r--;
            while (nums[l] <= key && l < r)
                l++;
            if (l < r)
                swap(nums, r, l);
        }

        nums[left] = nums[r];
        nums[r] = key;

        quickSort(nums, left, r - 1);
        quickSort(nums, r + 1, right);
    }

• 归并排序

• 冒泡排序

    /**
     * 冒泡排序
     * 冒泡排序从左到右依次比较两个相邻的元素，如果前一个元素比较大，就把前一个元素和后一个元素交换位置，
     * 完成一趟循环后保证了最大的元素在最后一位。接下来进行第二趟排序，第二趟排序完成后第二大的元素在倒数第二位。
     * 依次遍历直至整个数组排序完成。
     * <p>
     * 冒泡排序的时间复杂度是O(n2),空间复杂度为
     *
     * @param nums
     * @return
     */
    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
    }