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

【从零开始学习计算机科学】算法分析（二）排序算法与分治法

article 2025/3/26 7:11:14

【从零开始学习计算机科学】算法分析（二）排序算法与分治法

排序算法
- 插入排序
- 冒泡排序
- 快速排序
- 希尔（Shell）排序
- 选择排序
- 堆排序
- 归并排序
- 计数排序
- 基数排序
- 桶排序
分治法

排序算法

这一部分主要介绍一些常用的基础排序算法，并从稳定性，时间、空间复杂度进行分析。

插入排序

插入排序将待排序的数据分成两个区域：有序区和无序区，每次将一个无序区中的数据按其大小插入到有序区中的适当位置，直到所有无序区中的数据都插入完成为止。

伪代码如下：

void insertsort(Elemtype a[], int n){
    int i, j;
    for(int i = 2; i<=n; i++){
        if(a[i] < a[i-1]){
            a[0] = a[i];
            for(int j = i-1; a[0] < a[j]; --j){
                a[j+1] = a[j];
            }
            a[j+1] = a[0];
        }
    }
}

分析：稳定性：稳定；时间复杂度：O( $n^2$ )；空间复杂度：O(1)。

冒泡排序

冒泡排序最多进行n-1趟排序，每趟排序时，按相同的方向扫描，一旦发现两个相邻的元素不符合规则，则交换。

伪代码如下：

void bubblesort(Elemtype a[], int n){
    for(int i = 0; i<n-1; i++){
        for(int j = 0; j<n-1-i; j++){
            if(a[j] < a[j+1]){
                swap(a[j], a[j+1]);
            }
        }
    }
}

分析：稳定性：稳定；时间复杂度：O( $n^2$ )；空间复杂度：O(1)。

改进方法：每趟排序时，记住最后一次发生交换的位置，则该位置之前的记录均已有序。

快速排序

在A[1, $\ldots$ ,n]中任取一个数据元素作为比较的基准（记为X），将数据区划分为左右两个部分：A[1, $\ldots$ ,i-1]和A[i+1, $\ldots$ ,n]，且A[1, $\ldots$ ,i-1] $\leq$ X $\leq$ A[i+1, $\ldots$ ,n](1 $\leq$ i $\leq$ n)，当A[1, $\ldots$ ,i-1]和A[i+1, $\ldots$ ,n]非空时，分别对它们进行上述的划分过程，直至所有数据元素均已排序为止。

伪代码如下：

int partition(Elemtype a[], int low, int high){
    Elemtype p = a[low];
    while(low < high){
        while(high>low && a[high]>=p) high--;
        a[low] = a[high];
        while(low<high && a[low]<=p) low++;
        a[high] = a[low];
    }
    a[low] = p;
    return low;
}

void quicksort(Elemtype a[], int low, int high){
    if(low < high){
        int mid = partition(a, low, high);
        quicksort(a, low, mid-1);
        quicksort(a, mid+1, high);
    }
}

分析：稳定性：不稳定。

时间复杂度：每趟排序所需的比较次数为待排序区间的长度-1，排序趟数越多，占用时间越多。

最坏情况：每次划分选取的基准恰好都是当前序列中的最小(或最大)值，划分的结果A[low， $\ldots$ ，i-1]为空区间或A[i+1， $\ldots$ ，high]是空区间，且非空区间长度达到最大值。这种情况下，必须进行n-1趟快速排序，第i次趟区间长度为n-i+1，总的比较次数达到最大值：n(n-1)/2 = O( $n_2$ )。