# Ch8

# 冒泡排序

直接看代码

bubbleSort

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {   // j从0开始到n-i-1，原因是每次遍历之后第i大的元素已经被放到后面了，从后往前的顺序是对的
            if(a[j] > a[j + 1]){
                swap(a[j], a[j + 1]);
            }
        }
    }
    return;
}

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$

# 选择排序

每次找最小的和循环的第一个元素交换

selectionSort

void selectionSort(int a[], int n) {
    for(int i = 0l i < n; i++){
        int min_index = i;
        for(int j = i; j < n; j++){
            if(a[j] < a[min_index]){
                min_index = j;
            }
        }
        swap(a[i], a[min_index]);
    }
}

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$

# 插入排序

将列表分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含剩余元素，从未排序部分中取出第一个元素，插入已排序部分合适位置。

insertionSort

void insertionSort(int a[], int n) {
    for(int i = 1; i < n; i++){
        int j = i;
        int key = a[i];
        while(j > 0 && key < a[j - 1]){
            a[j] = a[j - 1];
            j--;
        }
        a[j] = key;
    }
}

时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$

# 希尔排序

将待排序的列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表的间隔，常见的增量序列有希尔增量（n/2, n/4, …, 1）

shellSort

void shellSort(int a[], int n) {
    for(int gap = n / 2; gap > 0; gap /= 2){
        for(int i = gap; i < n; i++){
            int j = i; 
            int key = a[i];
            while(j >= gap && key < a[j - gap]){
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = key;
        }
    }
}

best time complexity $O(nlog_n)$ , worst time complexity $O(n^2)$ ，空间复杂度 $O(1)$

# 归并排序

每次分成两半，像把两个有序链表合并成一个有序链表一样，将两个有序的子序列合并成一个有序的序列，然后递归处理每个子序列，直到处理完所有元素

mergeSort

1
2
3

void mergeSort(int &a[], int left, int right) {

}

时间复杂度 $O(nlog_n)$ , 空间复杂度 $O(n)$

# 快速排序

从列表中选择一个元素作为基准（pivot）。选择方式可以是第一个元素、最后一个元素、中间元素或随机元素，使得所有小于基准元素的元素都在基准的左侧，所有大于基准元素的元素都在基准的右侧

选择 pivot
分割列表：把小于 pivot 的元素放在 pivot 的左侧，大于 pivot 的元素放在 pivot 的右侧，最终 pivot 的位置是正确的
递归处理

quickSort

void quickSort(int a[], int left, int right) {
    if (left >= right) return;
    
    int pivot = a[(left + right) / 2];
    int i = left, j = right;
    
    while (i <= j) {
        while (a[i] < pivot) i++;
        while (a[j] > pivot) j--;
        if (i <= j) {
            // 交换
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }
    quickSort(a, left, j);
    quickSort(a, i, right);
}

时间复杂度 $O(nlog_n)$ , 空间复杂度 $O(log_n)$

# 堆排序

建立一个堆，让它自己排序（shift_down 和 shift_up）
最大堆用于升序排序，最小堆用于降序排序

heapSort

1	void heapSort(int a[], int n) {} // 有待补充

时间复杂度 $O(nlog_n)$ , 空间复杂度 $O(n)$

# 桶排序

将数据分到若干个桶中，每个桶再进行排序，最后将各个桶的元素合并

bucketSort

1
2
3

void bucketSort(int a[], int n) {

}

时间复杂度 $O(n+k)$ , 空间复杂度 $O(n+k)$

排序

# Ch8

# 冒泡排序

# 选择排序

# 插入排序

# 希尔排序

# 归并排序

# 快速排序

# 堆排序

# 桶排序

ch7

20251015力扣刷题笔记