作业解答

昨天的作业都比较简单，力扣的题解也解释比较清楚，我就不在啰嗦了，今天我们来看快速排序和插入排序，其中快排，更是在面试中频频出现，整体难度也更上一层楼

快速排序

《信息学奥赛一本通》中讲到：快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

具体时间复杂度分析：快速排序时间复杂度分析

1. 算法步骤

   • 从数列中挑出一个元素，称为 “基准”（pivot）;

   • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

   • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

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

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

插入排序

对于少量元素的排序，它是一个有效的算法。插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。在其实现过程使用双层循环，外层循环对除了第一个元素之外的所有元素，内层循环对当前元素前面有序表进行待插入位置查找，并进行移动。

像斗地主插入一样，简单的来说就是将一个记录插入到已经排好的有序表中，从而得到一个新的，记录数据+1的有序表

void insertionSort(int *arr, int len) {
    if (len<2) {
        return ;
    }
    
    for (int i=1; i<len; i++) {
        int insertValue = arr[i];//暂存需要插入元素
        int j = i-1;
 
        //从右向左比较元素
        for (; j>=0 && insertValue<array[j]; j--) {
            arr[j+1] = arr[j];
        }
 
        arr[j+1] = insertValue;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

插入排序的平均时间复杂度也是 O(n^2)，空间复杂度为常数阶 O(1)，具体时间复杂度和数组的有序性也是有关联的。

插入排序中，当待排序数组是有序时，是最优的情况，只需当前数跟前一个数比较一下就可以了，这时一共需要比较 N-1 次，时间复杂度为 O(N)。最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏的情况是 O(n^2)。

动图：