首页 计算机科学 数据结构

选择排序：分为简单选择排序和堆排序

选择排序：每一趟在待排序元素中选择关键字最小

# 简单选择排序

每一趟在待排序元素中选取关键字最小的元素加入有序子序列

算法实现

//交换
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
//简单选择排序
void SelectSort(int A[],int n){
    for(int i=0;i<n-1;i++){      //一共进行n-1趟
        int min=i;               //记录最小元素位置
        for(int j=i+1;j<n;j++)   //在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])      //更新最小元素位置
                min=j;
        if(min!=i)
            swap(A[i],A[min]);  //封装swap函数移动元素
    }
}

空间复杂度：O (1)

时间复杂度：O(n2)O(n^2)

稳定性：不稳定

适用性：既可以用于顺序表，也可用于链表

# 堆排序

若 n 个关键字序列 (1...n) 满足下面某一条性质，则称为堆

  • 若满足：L (i)>=L (2i) 且 L (i)>=L (2i+1)(1<=i<=n/2)—— 大根堆
    • 完全二叉树中，根 >= 左右
  • 若满足：L (i)<=L (2i) 且 L (i)<=L (2i+1)(1<=i<=n/2)—— 小根堆
    • 完全二叉树中，根 <= 左右

建立大根堆：

  • 思路：把所有非终端节点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整

  • 在顺序存储的完全二叉树中，非终端节点编号i≤⌊n/2⌋i\le \lfloor n/2\rfloor

  • 检查当前结点是否满足根 >= 左右，若不满足，将当前结点与更大的一个孩子互换

  • 若元素互换破坏了下一级的堆，则采用相同的方法继续往下调整 (小元素不断下坠)

代码实现：

//建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)  //从后往前调整所有非终端结点
        HeadAjust(A,i,len);
}

//将以K为根的子树调整为大根堆
void HeapAdjust(int A[],int k,int len){
	A[0]=A[k];                //A[0]暂存子树的根节点
    for(int i=2*k;i<=len;i*=2){ //沿key较大的子节点向下筛选
        if(i<len && A[i]<A[i+1])
            i++;    //取key较大的子节点的下标
        if(A[0]>=A[i])   //筛选结束
            break;
        else{
            A[k]=A[i];  //把A[i]调整到双亲结点上
            k=i;        //修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];          //被筛选结点的值放入最终位置
}

基于大根堆进行排序

堆排序：每一趟将堆顶元素加入有序子序列 (与待排序序列中的最后一个元素交换)，并将待排序元素序列再次调整为大根堆 (小元素不断下坠)

代码：

//堆排序的完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);       //初始建堆
    for(int i=len;i>1;i--){    //n-1趟的交换和建堆的过程
        swap(A[i],A[1]);       //堆顶元素和堆底元素交换
        HeadAdjust(A,1,i-1);   //把剩余的待排序元素整理成堆
    }
}

结论：一个结点，每下坠一层，最多只需要对比关键字 2 次

建堆的过程，关键字的对比次数不超过 4n，建堆的时间复杂度 = O (n)

每一趟排序复杂度不超过 O (h)=O (log2n)

总共 n-1 趟，总的时间复杂度为 O (nlogn)

空间复杂度为 O (1)

结论：堆排序是不稳定的

# 堆的插入和删除

在堆中插入新元素：

对于小根堆，新元素放到表尾，与父节点对比，若新元素比父节点更小，则将二者交换。新元素就这样一路上升，直到无法上升为止

每次上升只需要对比关键字 1 次

在堆中删除元素：

被删除元素用堆底元素替代，然后让该元素不断下坠，直到无法下坠为止

每次下坠调整可能需要对比关键字 2 次，也可能只需要对比 1 次

# 归并排序

归并：把两个或多个已经有序的序列合并成一个

只剩一个子表未合并时，可以将该表中剩余元素全部加到总表中

结论：m 路归并，每选出一个元素需要对比关键字 m-1 次

代码实现：

int *B=(int *)malloc(n*sizeof(int));  //辅助数组B

//A[low...mid]和A[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    for(k=low;k<=high;k++)
        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++];   //将较小值复制到A中
        else
            A[k]=B[j++];
    }
    while(i<=mid)
        A[k++]=B[i++];
    while(j<=high)
        A[k++]=B[j++];
}

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

结论：n 个元素进行 2 路归并排序，归并趟数 =⌈log2n⌉\lceil log_2n\rceil

每趟归并排序时间复杂度为 O (n)，算法时间复杂度为 O (nlogn)

空间复杂度 = O (n)，来自于辅助数组 B

稳定性：稳定的

# 基数排序

第一趟收集：得到按个位递减排序的序列

第二趟收集：得到按十位递减排序的序列，十位相同的按个位递减排序

第三趟收集分配、收集：得到一个按百位递减排列的序列，若百位相同则按十位递减排列，若十位相同则按个位递减排列

假设长度为 n 的线性表中每个结点 ai 的关键字由 d 元组(kjd−1,kjd−2,...,kj1,kj0)(k_j^{d-1},k_j^{d-2},...,k_j^1,k_j^0) 组成，其中0≤kji≤r−10\le k_j^i\le r-1，r 称为基数

基数排序得到递减序列的过程如下：

初始化：设置 r 个空队列，Q1,Q2,...Qr

按照各个关键字位权重递增的次序 (个、十、百)，对 d 个关键字位分别做分配和收集

分配：顺序扫描各个元素，若当前处理的关键字位 = x，则将元素插入 Qx 队尾

收集：把 Qr-1,Qr-2,...Q0 各个队列中的结点依次出队并链接

复杂度分析：

空间复杂度：O (r)

d 趟分配，一趟手机需要 O (r)，总的时间复杂度为 O (d (n+r))

稳定性：基数排序是稳定的

基数排序擅长解决的问题：

  • 数据元素的关键字可以方便地拆分成 d 组，且 d 较小
  • 每组关键字的取值范围不大，即 r 较小
  • 数据元素个数 n 较大