面试必问-排序算法实现全面解析

灬沙师弟

发布于 2025-11-12 13:28:17

950

文章被收录于专栏：Java面试教程Java面试教程

面试必考排序

为什么排序是面试必考？

编程第一课都回讲到

软件 = 算法 + 数据结构

排序是算法基础

考察逻辑思维和代码能力

同时兼顾了数据和逻辑

光是一个排序

就有快排、归并、堆排、冒泡、插入等

加分点包括时间复杂度、空间复杂度、边界值处理

比如我面试的时候

就喜欢提问

如何高效对一亿数据排序？

这类问题对于没有准备的人

可能就蒙了

支支吾吾说出个sort

那面试只能惨淡收场

入门级：冒泡排序

基本上大家都知道这个词

但冒泡的实现很多人说不出个所以然

他仅通过交换相邻元素的方式

每轮将最大元素冒泡到末尾

类似于穷举法的方式

时间复杂度 O(n²) 空间复杂度 1

来看个示范

public void sort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        boolean swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
        if (!swapped) break; 
    }
}

一句话评价

简单且低效

是所有人必须掌握的基础算法

进阶版：插入排序

对于数据规模少

或者部分有序的场景很适合

每次挑选一个元素

插入到有序队列中合适的位置

时间复杂度 O(n²) 空间复杂度 1

来看个示范

public void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

代码量略少于冒泡

两者效率相当

换了一个新思路

Java默认的sort就是采用这种方案

高效：快速排序

这是一种分治的排序思想

先从列表中选一个数作为基准值

将列表划分为两个子列表

所有小于基准的元素放在基准左侧

所有大于基准的元素放在基准右侧

然后递归对两个子列表继续做分治

直到子列表元素 < 2 个

时间复杂度 O(n log n) 空间复杂度 O(n)

示范代码如下：

public void sort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    sort(arr, left, mid);
    sort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    System.arraycopy(temp, 0, arr, left, temp.length);
}

在数字排序领域

快速排序已经做到比较极致了

但它不适合对象类型

附加题：基数排序

这是一种不常见的做法

他不比较具体每个元素的数字大小

而是逐位排序

时间复杂度 O(kn) 空间复杂度 O(n + k) k为最大位数

示范如下：

public void sort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    int maxDigit = String.valueOf(max).length();
    int[][] bucket = new int[10][arr.length];
    int[] count = new int[10];
    for (int digit = 0, mod = 10, div = 1; digit < maxDigit; digit++, mod *= 10, div *= 10) {
        for (int num : arr) {
            int bucketIndex = (num % mod) / div;
            bucket[bucketIndex][count[bucketIndex]++] = num;
        }
        int index = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < count[i]; j++) {
                arr[index++] = bucket[i][j];
            }
            count[i] = 0;
        }
    }
}

它按数字的个位、十位、百位等

从最低位到最高位依次排序

将元素按当前位的值分配到不同的桶中

再按桶的顺序收集回原数组

通过位数的权重进行排序

适合整数、日期字符串、IP字符串等固定格式的数据