当前位置：首页 > article >正文

lec9-Sortings

article 2025/2/22 15:18:56

lec9-Sorting 排序

1. 概述

2. 插入排序

插入排序这一个大类的思想，是v0, … vi-1都插入好了，考虑 vi 插入进去

2.1. 直接插入排序

void sort(int arr[], int n){
    for(int i = 1;i < n;i++){
        int temp = arr[i];
        // 1 2 3 4 2
        for(int j = i-1; j >= 0;j--){
            if(arr[j] > temp){
                arr[j + 1] = arr[j]
            }else{
                arr[j] = temp;
                break;
            }
        }
    }
}

直接插入排序的手动模拟？可能会考到
算法分析部分：
- 最好情况：已经有序，比较次数只需要 n-1，移动次数只需要 0
- 最坏情况：刚好逆序，比较次数需要 1 + 2 +… + n - 1 = n(n-1) / 2，移动次数 $\frac {n^2 + 3n - 4} 2$
稳定性：是稳定的（手写排序的时候可以验证一下）

2.2. 折半插入排序

虽然比较次数减少，但是移动次数还是 $O(n^2)$
一般少用
稳定性： 稳定的

2.3. 希尔排序

也叫做缩小增量排序
算法：取出一个增量，gap < n，按增量分组，对每组使用直接插入排序或其他方法进行排序，然后缩小增量

public static void shellsort(Comparable []a){
    for(int gap = a.length / 2;gap > 0;gap /= 2){
        for(int i = gap; i < a.length; i++){ // 这里i = gap， 实际上就相当于第 0 组 的 一号（第二个）元素，然后类似与插入排序过程
            Comparable tmp = a[i];
            int j = i;
            
            // 此处暂时略去
        }
    }
}

稳定性： 不稳定
平均比较次数和移动次数大约是 $n^{1.3}$

3. 交换排序

方法的本质：不断地交换反序的对偶，直到不再有反序的对偶为止
冒泡排序和 快速排序

3.1. 冒泡排序

冒泡排序的一个重要的特点是：每一轮冒泡彻底完成后，必然将一个最大或最小值冒泡到最边上
比较次数的问题
- 最小比较次数： n-1 次比较，移动次数是0
- 最大比较次数：n（n-1） / 2
稳定性： 稳定的

3.2. 快速排序

关键是，考虑一个基准值，让小的都放在基准值左面，大的都放在基准值右面

public int partition(int []arr, int left, int right){
    int pivot = arr[left];
    int i = left, j = right;
    while(i != j){
        while(arr[j] > pivot) j--;
        if(i < j) {arr[i] = arr[j]; i++;}
        
        while(arr[i] < pivot) i++;
        if(i < j) {arr[j] = arr[i]; j--;}
    }
    arr[i] = pivot;
    return i;
}

public void quickSort(int []arr, int left, int right){
    int mid = partition(arr, left, right);
    quickSort(arr, left, mid - 1);
    quickSort(arr, mid + 1, right);
}