【408篇】C语言笔记-第十七章（考研必会的排序算法（下））-创新互联

• • 第一节：选择排序
  • • 1. 选择排序原理解析
    • 2. 选择排序代码实战
    • 3. 时间复杂度与空间复杂度
  • 第二节：堆排序
  • • 1. 堆排序原理解析
    • 2. 堆排序代码实战
    • 3. 时间复杂度与空间复杂度
  • 第三节：归并排序
  • • 1. 归并排序原理解析
    • 2. 归并排序代码实战
    • 3. 时间复杂度与空间复杂度
  • 第四节：小结
  • • 所有排序算法时间与空间复杂度汇总

选择排序分为：1.简单选择排序。2.堆排序（重要）。

简单选择排序原理：假设排序表为L[1,2,……n]，第i趟排序即从L[i……n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可使得整个排序表有序。

首先嘉定第0个元素是最小的，把下标0赋给min（min记录最小的元素的下标），内层比较时，从1号元素一直比较到9号元素，谁更小，就把它的下标赋给min，一轮比较结束后，将min对应的位置的元素与元素i交换。第一轮确认2最小，将2与数组开头的元素3交换，第二轮我们最初认为87最小，经过一轮比较，发现3最小，将87与3交换。持续进行，最终使数组有序。

动画演示：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html

步骤：随机10个元素->打印->选择排序->打印。

#include#include#includetypedef int ElemType;
typedef struct {
    ElemType *elem; // 整型指针
    int TableLen; // 存储动态数组里边元素的个数，相当于之前的len
}SSTable;

// 初始化链表
void ST_Init(SSTable &ST,int len){
    ST.TableLen=len;
    ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand(time(NULL));// 生成随机数
    for(i=0;i
F:\Computer\Project\practice\17\17.3-selectSort\cmake-build-debug\17_3_selectSort.exe
  5  8 65 13 26 38 40 65 82 97
  5  8 13 26 38 40 65 65 82 97

进程已结束，退出代码为 0
3. 时间复杂度与空间复杂度
时间复杂度O(
    
     
      
       
        
         n
        
        
         2
        
       
      
      
       n^2
      
     
    n2)。
空间复杂度O(1)。
第二节：堆排序 
1. 堆排序原理解析
堆（Heap）是计算机科学中的一种特殊的树状数据结构。若满足以下特性，则可称为堆：“给定堆中任意节点P和C，若P是C的父结点，则P的值小于等于（或大于等于）C的值。”若父结点的值恒小于等于子结点的值，则该堆称为最小堆（min heap），反之，称为大堆（max heap）。堆中最顶端的那个结点称为根结点（root node），根结点本身没有父结点（parent node）。平时工作中，我们将最小堆称为小根堆或小顶堆，把大堆称为大根堆或大顶堆。
假设我们有3,87,2,93,78,56,61,38,12,40共10个元素，我们将这10个元素建成一棵完全二叉树，这里采用层次建树法，虽然只有一个数组存储元素，但是我们能将二叉树中任意一个位置的元素对应到数组下标上，我们将二叉树中每个元素到数组下标的这种数据结构称为堆。比如最后一个父元素的下标是n/2-1，也就是a[4]，对应的值是78。可以这样记忆：如果父结点的下标是dad，那么父结点对应的左子结点的下标值是2*dad+1。接着，依次将没棵子树都调整为父结点大，最终整棵树将变成一个大根堆。
动画演示：
https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
2. 堆排序代码实战
堆排序的步骤是首先把堆调整为大根堆，然后我们交换根部元素也就是A[0]和最后一个元素，这样大的元素就放到了数组最后，接着我们将剩余9个元素继续调整成大根堆，然后交换A[0]和9个元素最后一个，循环往复，直到有序。
#include#include#include#includetypedef int ElemType;
typedef struct {
    ElemType *elem; // 整型指针
    int TableLen; // 存储动态数组里边元素的个数，相当于之前的len
}SSTable;

// 初始化链表
void ST_Init(SSTable &ST,int len){
    ST.TableLen=len;
    ST.elem= (ElemType*)malloc(sizeof(ElemType)*ST.TableLen);
    int i;
    srand(time(NULL));// 生成随机数
    for(i=0;i=0;i--){
        AdjustDown(A,i,len);
    }
    swap(A[0],A[len]);// 交换顶部和数组最后一个元素
    // 下面的策略是，不断调整剩余元素为大根堆，因为根部大，所以再次与A[i]交换，相当于放数组后面，循环往复
    for(i=len-1;i>0;i--){
        AdjustDown(A,0,i);// 剩余元素调整为大根堆
        swap(A[0],A[i]);
    }
}
int main() {
    SSTable ST;
    ST_Init(ST,10);
    ElemType A[10]={3,87,2,93,78,56,61,38,12,40};
    memcpy(ST.elem,A, sizeof(A));
    ST_print(ST);
    HeapSort(ST.elem,9); // 所有元素参与排序
    ST_print(ST);
    return 0;
}
F:\Computer\Project\practice\17\17.5-heapSort\cmake-build-debug\17_5_heapSort.exe
  3 87  2 93 78 56 61 38 12 40
  2  3 12 38 40 56 61 78 87 93

进程已结束，退出代码为 0
3. 时间复杂度与空间复杂度
第三节：归并排序 
1. 归并排序原理解析
如图所示，我们把每两个元素归为一组，进行小组内排序，然后再次把两个有序小组合并为一个有序小组，不断进行，最终合并为一个有序数组。
动画演示：
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
2. 归并排序代码实战
归并排序的代码是采用递归思想实现的。首先，最小下标值和大下标值相加并除以2，得到中间下标值mid，用MergeSort对low到mid排序，然后用MergeSort对mid+1到high排序。当数组的前半部分和后半部分都排好序，使用Merge函数对两个有序数组进行合并。为了提高合并有序数组效率，在Merge函数内定义了B[N]。首先，我们通过循环把数组A中从low到high的元素全部复制到B中，这是游标i从low开始，游标j从mid+1开始，谁小就将谁放入数组A，对其游标加1，并在每轮循环时对数组A的计数游标k加1。
#include#include#define N 7
typedef int ElemType;
// 49,38,65,97,76,13,27

// 合并数组
void Merge(ElemType A[],int low,int mid,int high){
    static ElemType B[N]; // 加static的目的是无论递归调用多少次，都只有一个B[N]
    int i,j,k;
    for(k=low;k<=high;k++){ // 赋值元素到B中
        B[k]=A[k];
    }
    for(i=low,j=mid+1,k=i;i<=mid&& j<=high;k++){ // 合并两个有序数组
        if(B[i]<=B[j]){
            A[k]=B[i++];
        } else{
            A[k]=B[j++];
        }
    }
    while (i<=mid){ // 如果右剩余，直接放入即可
        A[k++]=B[i++]; // 前一半有剩余的放入
    }
    while (j<=high){
        A[k++]=B[j++];//后一半的有剩余的放入
    }
}
// 归并排序
void MergeSort(ElemType A[],int low,int high){
    if(low
F:\Computer\Project\practice\17\17.6-mergeSort\cmake-build-debug\17_6_mergeSort.exe
 49 38 65 97 76 13 27
 13 27 38 49 65 76 97

进程已结束，退出代码为 0
3. 时间复杂度与空间复杂度
第四节：小结 
所有排序算法时间与空间复杂度汇总
稳定性是指排序前后，相等元素位置是否会被交换。
复杂性是指代码编写的难度。
                
     
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
                

                当前题目：【408篇】C语言笔记-第十七章（考研必会的排序算法（下））-创新互联                

                标题来源：http://www.wjwzjz.com/article/ccooep.html