本文共 3573 字，大约阅读时间需要 11 分钟。

一、基本概念

排序是数据处理的核心技能之一，其基本概念是理解算法工作原理的基础。

二、插入排序

插入排序通过逐步将元素插入有序序列中，逐步建立有序表。

2.1 直接插入排序

伪代码：

void insertSort(elementType A[n+1]) {    for(int i = 2; i <= n; i++) {        //I表示待插入元素的下标        A[0] = A[I]; //设置监视哨保存待插入元素，以腾出A[i]的空间        j = I - 1; //j表示当前空位置的前一个        while(A[j].key > A[0].key) {            //搜索插入位置并腾出空位            A[j+1] = A[j];            j = j - 1;        }        A[j+1] = A[0]; //插入元素    }}

算法分析：

• 稳定性：稳定排序。
• 空间复杂度：仅需一个临时存储空间（监视哨）。
• 时间复杂度：在一般情况下为$O(N^2)$，但在数据已经近似有序的情况下复杂度会更优。

2.2 带，有希尔排序

希尔排序通过分组插入排序实现更高效的性能。其关键在于选择合适的步长，分组后对每组进行直接插入排序。

伪代码（简化版本）：

void ShellSort(elementType A[n+1], int dh) {    while(dh >= 1) {        for(int I = dh + 1; I <= n; I++) {            int temp = A[I];            for(int j = I; j > dh && A[j].key > temp.key; j--) {                A[j] = A[j-1];            }            A[dh] = temp;        }        dh--;    }}

算法分析：

• 稳定性：不稳定排序。
• 空间复杂度：无需额外空间即可完成。
• 时间复杂度：通常达到$O(n \log^2 n)$，在部分情况下性能优于直接插入排序。

三、交换排序

通过元素交换实现排序，适用于简单场景。

3.1 冒泡排序

与水泵工作方式类似，元素逐个交换至位序。

伪代码：

void bubbleSort(int A[n+1]) {    int exchanged = FALSE;    do {        exchanged = FALSE;        for(int j = n; j >= 1; j--) {            if(A[j].key < A[j-1].key) {                swap(A[j], A[j-1]);                exchanged = TRUE;            }        }    } while(exchanged && n > 1);}

算法分析：

• 稳定性：稳定排序。
• 空间复杂度：仅需常数额外空间。
• 时间复杂度：最优情况$O(n)$，最差情况$O(n^2)$。

3.2 快速排序

快速排序采用分治法以划分数据集，常用中的选择中值为枢杆元素。

伪代码：

void QuickSort(int A[n], int low, int high) {    int mid;    while(low < high) {        Partition(A, low, high, mid);        low++;        high--;    }}

算法分析：

• 稳定性：不稳定排序。
• 时间复杂度：理想情况下为$O(n \log n)$，最差情况下为$O(n^2)$。
• 空间复杂度：需要额外存储空间用于分区。

四、选择排序

选择排序通过每次选择最小或最大元素放置到底部或顶部完成排序。

4.1 简单选择排序

每次选择当前未排序区间中的最小或最大元素放置到适当位置。

伪代码：

void SelectSort(int A[n+1]) {    for(int i = 1; i < n; i++) {        int min_pos = i;        for(int j = i+1; j < n; j++) {            if(A[j] < A[min_pos]) {                min_pos = j;            }        }        if(min_pos != i) {            swap(A[min_pos], A[i]);        }    }}

算法分析：

• 稳定性：不稳定排序。
• 时间复杂度：$O(n^2)$，由于需要n-1次选择并交换元素。

4.2 堆排序

堆排序利用二叉树结构进行排序，先建立大根堆，再通过筛选调整顺序。

伪代码：

void sift(int A[], int k, int m) {    int x = A[k];    bool finished = FALSE;    int i = k;    while((j = 2*i) <= m && !finished) {        if(j < m && A[j] < A[j+1]) {            j++;        }        if(x >= A[j]) {            finished = TRUE;        } else {            A[i] = A[j];            i = j;            j = 2*j;        }    }    A[i] = x;}void HeapSort(int A[n]) {    int i = n/2;    while(i > 0) {        sift(A, i, n);        i--;    }    for(i = n; i > 1; i--) {        A[0] = A[i];        A[i] = A[0];        sift(A, 0, i-1);    }}

算法分析：

• 稳定性：不稳定排序。
• 时间复杂度：$O(n \log n)$。
• 空间复杂度：需要额外存储空间。

五、归并排序

归并排序通过分拆和合并实现，适合大规模数据排序。

5.1 归并操作

伪代码：

void merge(int A[], int B[], int C[], int la, int lb, int rc) {    //将A和B按顺序合并到C中，默认是递增排序    int ia = la, ib = lb;    while(ia <= la && ib <= lb) {        if(A[ia] <= B[ib]) {            C[ia + ib] = A[ia];            ia++;        } else {            C[ia + ib] = B[ib];            ib++;        }    }    while(ia <= la) {        C[ia + ib] = A[ia];        ia++;    }    while(ib <= lb) {        C[ia + ib] = B[ib];        ib++;    }}

算法分析：

• 时间复杂度：$O(n \log n)$。
• 稳定性：稳定排序。

通过以上内容，我们可以清晰地看到各类排序算法的工作原理、优缺点以及时间复杂度等关键考量因素。

转载地址：http://dumez.baihongyu.com/