您现在的位置是:首页 > 正文

算法入门之排序算法

2024-04-01 05:10:14阅读 6

1. 概述

排序算法分为基础和进阶版的,我这里区分的一点主要是根据(平均)时间复杂度

  • 基础:冒泡排序、选择排序
  • 进阶:堆排序、快速排序、归并排序

其实对于进阶排序来说,大家不光要掌握排序的应用,在排序之外的思想也需要掌握:

  • 堆是一种很有用的数据结构,在 Java 里也叫优先级队列,在做“最大”、“最小”相关的题目时我们应该首先想到堆这种数据结构,在存入数据的时候就按照一定的顺序排列,且时间复杂度为 O(logK) 这里的 K 是堆的容量,取堆顶(最大或者最小值)的时间复杂度为 O(1)
  • 快速排序的分治思想在解决 TopK 的问题时有奇效,因为我们求 TopK 的问题时不需要将整个序列排序且求出前的这 K 个元素之间也不需要有序。分治思想简单说就是经过处理之后,当前位置之前的数字都比当前位置的数小(比当前数字小的这些数之间可能是无序的),当前位置之后的数字都比当前位置的数字大(比当前数字大的这些数之间也可能是无序的)。比如我们要求数组 [5, 3, 2, 1, 4, 6] ,当前的数字为4,则分治后的数组可能是这样的: [3, 2, 1, 4, 6, 5] ,4 之前的数字 [3, 2, 1] 都比 4小,4 之后的数字 [6, 5] 都比4大。回到 TopK 的问题上来,如果我们要求 [5, 3, 2, 1, 4, 6] 中前 3 小的数字,我们只需要找到第 3 个位置的数字即可,因为第 3 个位置前面的两个数字肯定比第 3 个位置的数小,第 3 个位置后面的数字肯定比第 3 个位置的数字大(不可能是前3小的),所以最终的结果是第 3 个位置加上前两个比它小的数字!
  • 归并排序在求逆序对的时候比较有效:

2. 堆排序

相较于堆排序这种排序算法,堆这种数据结构更为重要

/**
 * @Author Jason
 * @Date 2021/9/11 11:09 上午
 * @Description 堆排序
 * 1、 建立(大根)堆,每一个元素跟其父元素进行比较,如果比父元素大就替换父元素
 * 2、 得到堆顶元素,为最大元素
 * 3、 去掉堆顶,将堆最后一个元素放置到堆顶
 * 4、 调整堆结构,堆顶为第二大元素
 * 5、 重复3、4步骤,直至堆变空
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {-4, 0, 7, 4, 9, -5, -1, 0, -7, -1};
        heapSort(arr);
        for (int i : arr) {
            System.out.printf("%3d", i);
        }
    }

    public static void heapSort(int[] arr) {
        int length = arr.length;

        if (length < 1) return;

        // 建立堆
        for (int i = 0; i < length; i++) {
            heapInsert(arr, i);
        }

        // 堆的大小
        int size = length;

        // 3~5的步骤
        while (size > 0) {
            // 交换首尾元素,相当于去掉堆顶
            int last = arr[size - 1];
            arr[size - 1] = arr[0];
            arr[0] = last;
            // 堆结构-1
            size--;
            // 调整新堆结构
            adjustHeap(arr, 0, size);
        }

    }


    /**
     * 建立大根堆
     *
     * @param arr   数组
     * @param index 下标,会一直向上找父、父的父...
     */
    public static void heapInsert(int[] arr, int index) {
        // 父元素的下标
        int fatherIndex = (index - 1) / 2;
        while (fatherIndex >= 0 && arr[index] > arr[fatherIndex]) {
            // 交换index和其父元素
            int temp = arr[index];
            arr[index] = arr[fatherIndex];
            arr[fatherIndex] = temp;
            // 更新父元素下标
            index = fatherIndex;
            fatherIndex = (index - 1) / 2;
        }
    }

    public static void adjustHeap(int[] arr, int start, int end) {
        int left = 2 * start + 1; // start节点的左孩子的下标
        int right = left + 1; // start节点的右孩子的下标
        int largest = 0;
        while (left < end) {
            // 找到左右孩子中最大的
            if (right < end && arr[right] > arr[left]) {
                largest = left + 1;
            } else {
                largest = left;
            }
            // 如果start比左右孩子中最大的还要大,已经是大根堆
            if (arr[start] > arr[largest]) break;

            // 否则交换start和largest
            int temp = arr[start];
            arr[start] = arr[largest];
            arr[largest] = temp;

            // 更新start
            start = largest;
            left = (start << 1) + 1;
            right = left + 1;
        }
    }
}

3. 快速排序

import java.util.Arrays;
import java.util.Random;

/**
 * @Author Jason
 * @Date 2021/10/1 11:55 上午
 * @Description
 */
public class quickSort {
    static Random random = new Random(System.currentTimeMillis());

    public static void main(String[] args) {
        for (int i = 0; i < 30; i++) {
            int len = random.nextInt(20) + 1;
            int[] arr = new int[len];
            for (int j = 0; j < len; j++) {
                arr[j] = random.nextInt(30) + 1;
            }
            int[] stand = new int[len];
            System.arraycopy(arr, 0, stand, 0, len);
            QuickSort(arr, 0, len - 1);
            Arrays.sort(stand);
            for (int j = 0; j < len; j++) {
                if (arr[j] != stand[j]) {
                    System.out.println("wrong!");
                }
            }
        }
        System.out.println("Done");

    }

    public static void QuickSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = Partition(arr, left, right);
            QuickSort(arr, left, mid - 1);
            QuickSort(arr, mid + 1, right);
        }
    }


    public static int Partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        while (left < right) {
            // 先从最后开始向左找小于pivot的点
            while (left < right && arr[right] >= pivot) right--;
            // 如果下标没越界,则将从右往左找到的大于小于pivot的点置于left位置
            if (left < right) arr[left++] = arr[right];

            // 从左往右找大于pivot的点
            while (left < right && arr[left] <= pivot) left++;
            // 如果下标没越界,则将从左右往右找到的大于pivot的点置于right的位置
            if (left < right) arr[right--] = arr[left];
        }
        // left和right相等时,将pivot的值置到该位置,则此时pivot左侧的点都比它小,其右侧的点都比它大
        arr[left] = pivot;
        return left;
    }
}

4. 归并排序

/**
 * @Author Jason
 * @Date 2022/1/19 1:13 下午
 * @Description
 */
public class mergeSort {
    public static void main(String[] args) {
        int[] nums = {8, 4, 5, 7, 1, 3, 6, 2};
        mergeSort(nums, 0, nums.length - 1, new int[nums.length]);
        System.out.println(nums);
    }

    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) { // left >= right 说明待排序的区间为空或者只有一个元素,不需要排序
            int mid = left + ((right - left) >> 1);
            mergeSort(arr, left, mid, temp);
            mergeSort(arr, mid + 1, right, temp);
            merge(arr, left, mid, right, temp);
        }
    }


    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int l = left, r = mid + 1, idx = 0;
        System.out.println("left=" + left + ", right =" + right + ", mid =" + mid);
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                temp[idx++] = arr[l++];
            } else {
                temp[idx++] = arr[r++];
            }
        }

        while (l <= mid) {
            temp[idx++] = arr[l++];
        }

        while (r <= right) {
            temp[idx++] = arr[r++];
        }

        // 将 temp 数组的值拷贝到 arr 中
        for (int i = 0; i < idx; i++) {
            arr[left + i] = temp[i];
        }
    }
}

网站文章