【计算机考研（408）- 数据结构】排序
登录 / 注册
【计算机考研（408）- 数据结构】排序
美丽新科技BLOG

【计算机考研（408）- 数据结构】排序

刘纪彤
刘纪彤
4天前发布
0 0 0

排序

排序（Sort），就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

稳定性：相同的元素，排完后相对顺序不变

内部排序：所有元素都在内存中进行排序

外部排序：元素无法都放在内存中，必须在排序的过程中根据要求不断地在内、外存之间移动的排序

本节默认非严格递增排序。

插入排序

思路

每次将⼀个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

过程

初始      (49) 38 65 97 76 13 27 49.
i=2：     (38 49) 65 97 76 13 27 49.
i=3：     (38 49 65) 97 76 13 27 49.
i=4：     (38 49 65 97) 76 13 27 49.
i=5：     (38 49 65 76 97) 13 27 49.
i=6：     (13 38 49 65 76 97) 27 49.
i=7：     (13 27 38 49 65 76 97) 49.
i=8：     (13 27 38 49 49 65 76 97)
这里没有体现出哨兵，就是index=0位置不存储任何东西，充当哨兵。

代码

//带哨兵的直接插入排序
void InsertSort(int A[],int n){
  int i,j;
  for(i =2;i<=n;i++){
    if(A[i]<A[i-1]){
      A[0] = A[i];//哨兵
      for(j = i-1;A[0]<A[j];j--)//从后往前查找应该插入的地方
        A[j+1] = A[j];
      A[j+1] = A[0];//插入
    }
  }
}
//优化版本（折半插入）
void BinaryInsertSort(int A[],int n){
  int i,j,low,high,mid;
  for(i = 2;i <= n;i++){
    if(A[i] < A[i-1]){
      A[0] = A[i];//哨兵
      /* 先找到插入位置 */
      low = 1; high = i-1;
      while(low <= high){
        mid = (low + high) / 2;
        if(A[0] < A[mid])
          high = mid - 1;
        else
          low = mid + 1;
      }
      /* 再执行插入 */
      for(j = i-1; j >= low; j--)
        A[j+1] = A[j];
      A[low] = A[0];
    }
  }
}

复杂度分析

时间复杂度：O(n^2)，最坏情况下需要进行n次插入，每次插入需要移动O(n)个元素。

空间复杂度：O(1)，只使用了常数级别的额外空间。

稳定性：稳定

当 $A[mid]==A[0]$ 时，为了保证算法的“稳定性”，应继续在 mid 所指位置右边寻找插入位置

希尔排序

思路

将排序表分割成$L[i,i+d,i+2d,..,i+kd]$的特殊形式。先取一个小于n的步长$d_1$,把表中的全部记录分成$d_1$组，所有距离为$d_1$的倍数的记录放在同一组中，各组中进行直接插入排序；然后取$d_2 < d_1$，最后的增量一定是1。

过程

希尔排序过程

代码

void ShellSort(ElemType A[],int n){
    for(dk=n/2;dk>=1;dk=dk/2){//增量不是死的,也就是说这个循环会变化的
        for(i=dk+1;i<=n;++i){
            if(A[i]<A[i-dk]){
                A[0]=A[i];//只是暂存
                for(j=i-dk;j>0&&A[0]<A[j];j-=dk){
                    A[j+dk]=A[j]; // 后移
                }
                A[j+dk]=A[0];
            }
        }
    }
}

复杂度分析

空间复杂度：O(1)，只使用了常数级别的额外空间。
时间复杂度：$O(n^{1.3})$，最坏情况下$O(n^2)$。
稳定性：不稳定。

冒泡排序

思路

一趟冒泡，将最小的元素交换到待排序列的第一个位置.冒泡排序中所产生的有序子序列一定是全局有序的。冒泡排序算法的结束条件时在一趟排序过程中没有发生关键字交换。

过程

冒泡排序示例

代码

void BubbleSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        flag=false;  // 本趟是否发生交换
        for(j=n-1;j>i;j--){
            if(A[j-1].key>A[j].key){
                swap(A[j-1],A[j]);
                flag=true;
            }
        }
        if(flag==false){
            return; // 没有发生交换，结束
        }
    }
}

复杂度分析

时间复杂度：$O(n^2)$，最坏情况下需要进行n次插入，每次插入需要移动O(n)个元素。平均也是$O(n^2)$。

空间复杂度：O(1)，只使用了常数级别的额外空间。

稳定性：稳定

快速排序

思路

每次取一个基准元素pivot。每趟排序后，pivot位置确定。

过程

确定枢轴位置的过程：

枢轴

快排整体过程：

整体过程

代码

void QuickSort(ElemType A[], int low, int high) {
    if (low < high) {
        int pivot = Partition(A, low, high);
        QuickSort(A, low, pivot - 1);
        QuickSort(A, pivot + 1, high);
    }
}

int Partition(ElemType A[], int low, int high) {
    ElemType pivot = A[low];
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

复杂度分析

时间复杂度：$O(n \log _2 n)$，平均情况下，快速排序的时间复杂度为 $O(n \log_2 n)$，最坏情况下为 $O(n^2)$。

空间复杂度：$O(\log_2 n)$，主要是递归调用栈的空间。

稳定性：不稳定。

简单选择排序

思路

假设排序表为$L[1...n]$ ，第i趟排序从$L[i...n]$中选择关键字最小的元素与L(i)交换。

代码

void SelectionSort(ElemType A[], int n) {
    for (int i = 1; i < n; i++) {
        int minIndex = i;
        for (int j = i + 1; j <= n; j++) {
            if (A[j] < A[minIndex]) {
                minIndex = j;
            }
        }
        swap(A[i], A[minIndex]);
    }
}

复杂度分析

时间复杂度：$O(n^2)$，最坏情况下需要进行n次选择，每次选择需要遍历O(n)个元素。

空间复杂度：O(1)，只使用了常数级别的额外空间。

稳定性：不稳定。

堆排序

思路

将待排序的数组看作一个完全二叉树，只要满足了父节点大于等于子节点，就是大根堆，反之亦然，经常用此来实现优先队列

过程

自下而上调整为大根堆：

自下往上调整为大根堆

之后，把根节点与最后一个节点交换，然后再对除最后一个结点以外的所有元素进行调整，直到整个堆有序。

删除：

删除

插入：

插入

代码

代码不是那么重要哈~
void HeapSort(ElemType A[], int n) {
    BuildMaxHeap(A, n);
    for (int i = n - 1; i > 0; i--) {
        swap(A[0], A[i]);
        MaxHeapify(A, 0, i);
    }
}

void BuildMaxHeap(ElemType A[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        MaxHeapify(A, i, n);
    }
}

void MaxHeapify(ElemType A[], int i, int n) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && A[left] > A[largest]) largest = left;
    if (right < n && A[right] > A[largest]) largest = right;
    if (largest != i) {
        swap(A[i], A[largest]);
        MaxHeapify(A, largest, n);
    }
}

复杂度分析

时间复杂度：$O(n \log_2 n)$，主要是建堆和调整堆的时间复杂度。

空间复杂度：$O(1)$，只使用了常数级别的额外空间。

稳定性：不稳定。

归并排序

思路

二路归并：将待排序序列分为两部分，分别对这两部分进行归并排序，然后将已排序的两部分合并成一个整体有序序列。

过程

二路归并

代码

void MergeSort(ElemType A[], int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(A, left, mid);
        MergeSort(A, mid + 1, right);
        Merge(A, left, mid, right);
    }
}

void Merge(ElemType A[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    ElemType* temp = new ElemType[right - left + 1];
    while (i <= mid && j <= right) {
        if (A[i] < A[j]) {
            temp[k++] = A[i++];
        } else {
            temp[k++] = A[j++];
        }
    }
    while (i <= mid) temp[k++] = A[i++];
    while (j <= right) temp[k++] = A[j++];
    for (i = left, k = 0; i <= right; i++, k++) {
        A[i] = temp[k];
    }
    delete[] temp;
}

复杂度分析

时间复杂度：$O(n \log_2 n)$，主要是分割和合并的时间复杂度。

空间复杂度：$O(n)$，需要额外的空间来存放合并后的结果。

稳定性：稳定。

基数排序

思路

基数排序并不基于比较和移动进行排序，而是基于关键字的值进行排序，将所有数据收集到一个数组中，然后根据关键字的某一位进行排序，直到所有的关键字都排序完成。

为实现多关键字排序，通常有两种方法：第一种是最高位优先（MSD）法，按关键字位权重递减依次逐层划分成若干更小的子序列，最后将所有子序列依次连接成一个有序序列；第二种是最低位优先（LSD）法，按关键字位权重递增依次进行排序，最后形成一个有序序列。。

过程

通常采用链式基数排序，假设对如下10个记录进行排序：278 109 063 930 589 184 505 269 008 083

这个时候基数r=10，把每一个整数分为个位，十位，百位三个子关键字，进行三趟分配和收集，如下图所示：

基础排序过程

复杂度分析

空间复杂度：r个队列（r个队头指针，r个队尾指针），故为$O(r)$

时间复杂度：d趟，每趟都要遍历整个数组，还要合并r个队列，故为$O(d(n+r))$

稳定性：稳定

适用：顺序存储和链式存储的线性表。

计数排序

不在大纲内，但是思想很重要！

思路

计数排序的基本思想是：对于待排序的数组，首先找出其中的最大值和最小值，然后统计每个元素出现的次数，最后根据统计结果将元素放回原数组中。

过程

  1. 找到待排序数组的最大值和最小值。
  2. 创建一个计数数组，大小为最大值与最小值之差加一，用于统计每个元素出现的次数。
  3. 遍历待排序数组，将每个元素的出现次数存入计数数组中。
  4. 根据计数数组的统计结果，将元素放回原数组中。

代码

void CountingSort(ElemType A[], int n) {
    if (n <= 0) return;

    // 找到最大值和最小值
    ElemType maxVal = A[0];
    ElemType minVal = A[0];
    for (int i = 1; i < n; i++) {
        if (A[i] > maxVal) maxVal = A[i];
        if (A[i] < minVal) minVal = A[i];
    }

    // 创建计数数组
    int range = maxVal - minVal + 1;
    int* count = new int[range]();
    for (int i = 0; i < n; i++) {
        count[A[i] - minVal]++;
    }

    // 将元素放回原数组
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            A[index++] = i + minVal;
            count[i]--;
        }
    }

    delete[] count;
}

复杂度分析

时间复杂度：$O(n + k)$，其中 n 是待排序数组的长度，k 是计数数组的长度。

空间复杂度：$O(k)$，需要额外的空间来存放计数数组。

稳定性：稳定。

内部排序算法性能分析

算法种类最好情况平均情况最坏情况空间复杂度是否稳定每次能否固定一个位置比较次数与初始状态有关
直接插入排序$O(n)$$O(n^2)$$O(n^2)$O(1)是否是
冒泡排序$O(n)$$O(n^2)$$O(n^2)$O(1)是是是
简单选择排序$O(n^2)$$O(n^2)$$O(n^2)$O(1)否是否
希尔排序 O(1)否否是
快速排序$O(nlog_2n)$$O(nlog_2n)$$O(n^2)$$O(log_2n)$否是是
堆排序$O(nlog_2n)$$O(nlog_2n)$$O(nlog_2n)$$O(1)$否是是
2路归并排序$O(nlog_2n)$$O(nlog_2n)$$O(nlog_2n)$$O(n)$是否-
基数排序$O(d(n+2))$$O(d(n+r))$$O(d(n+r))$$O(r)$是否-

外部排序

外部排序暂时不整理

在一般情况下，对于 k–路平衡归并来说，若 (m-1)%(k-1)=0，则不需要增加虚段；否则需附加 k-(m-1)%(k-1)-1 个虚段。

数据结构
喜欢就支持一下吧
点赞 0 分享 收藏
版权属于：刘纪彤
本文链接：https://www.mlxkj.xyz/index.php/archives/156/
作品采用《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
评论 抢沙发
OωO
取消