数据结构【排序篇】

数据结构【排序篇】

---

---

前言

为什么突然想学算法了？

> 用较为“官方”的语言讲，是因为算法对计算机科学的所有分支都非常重要。 在绝大多数的计算机科学分支领域中，要想完成任何实质性的工作，理解算法的基础知识并掌握与算法密切相关的数据结构知识是必不可少的。
> 但从实际而言，是因为当下竞争压力逐渐增大，无论走哪一条路，都不免需要一些相对丰富的算法知识，是故，便产生了一个寒假巩固速成算法的计划，可能对于像我这种算法竞赛小白而言，几乎很难，但我仍然还是想尝试一下，毕竟，梦想还是要有的，万一实现了呢？～(￣▽￣～)~

---

为什么选择码蹄集作为刷题软件？

码蹄集，是在全国高等学校计算机教学与产业实践资源建设专家委员会(TIPCC) 指导下建设的，其依托全国各大名校计算机系和清华大学出版社等单位的强大资源，旨在为计算机学习爱好者提供全面和权威的计算机习题。
.

---

目录

一、插入排序

#include<iostream>

using namespace std;

//直接插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++)                            //将各元素插入已排好序的序列中
        if(A[i]<A[i-1]){                        //若A[i]关键字小于前驱
            temp=A[i];                          //用temp暂存A[i]
            for(j=i-1;j>=0 && A[j]>temp;--j)    //检查所有前面已排好序的元素
                A[j+1]=A[j];                    //所有大于temp的元素都向后挪位
            A[j+1]=temp;                        //复制到插入位置
        }
}

//直接插入排序（带哨兵）
void InsertSortS(int A[],int n){
    int i,j;
    for(i=2;i<=n;i++)                           //依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){                        //若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0]=A[i];                          //复制为哨兵，A[0]不存放元素
            for(j=i-1;j>=0 && A[0]<A[j];--j)    //从后往前查找待插入位置
                A[j+1]=A[j];                    //向后挪位
            A[j+1]=A[0];                        //复制到插入位置
        }
}

//二者本质上都是做了一个临时变量，哨兵A[0]在其中充当temp的作用

//折半插入排序
void MidInsertSort(int A[],int n){
    int i,j,high,low,mid,temp;
    for(i=1;i<n;i++){                           //依次将A[1]~A[n-1]插入前面的已排序序列
        temp=A[i];                              //将A[i]暂存到temp;
        low=0;high=i-1;                         //设置折半查找的范围
        while(low<=high){                       //折半查找（默认递增有序）
            mid=(low+high)/2;                   //取中间点
            if(A[mid]>temp) high=mid-1;         //查找左半子表
            else low=mid+1;                     //查找右半子表
        }
        for(j=i-1;j>=high+1;--j)
            A[j+1]=A[j];                        //统一后移元素，空出插入位置
        A[high+1]=temp;                         //插入操作
    }
}

//希尔排序
void ShellSort(int A[],int n){
    int d,i,j,temp;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到(这里用temp代替)
    for(d=n/2;d>=1;d=d/2)           //增量变化（无统一规定）
        for(i=d+1;i<n;++i)
            if(A[i]<A[i-d]){        //需将A[i]插入有序增量子表
                temp=A[i];          //暂存在A[0]
                for(j=i-d;j>0&&temp<A[j];j-=d)
                    A[j+d]=A[j];     //记录后移，查找插入的位置
                A[j+d]=temp;         //插入
            }
}

int main(){
    int B[10]={10,7,76,5,98,43,2,18,9,10};

    //带哨兵的直接插入排序(从输出结果和理解上看，还是建议用不带哨兵的)
//    InsertSortS(B,10);
//    for(int i=1;i<10;i++) cout<<B[i]<<" ";
//    cout<<endl;

    //不带哨兵的直接插入排序
//    InsertSort(B,10);
//    for(int i=0;i<10;i++) cout<<B[i]<<" ";

    //折半查找
//    MidInsertSort(B,10);
//    for(int i=0;i<10;i++) cout<<B[i]<<" ";



    return 0;
}

---

二、交换排序

#include<iostream>
using namespace std;

//简单选择排序
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()函数共移动元素3次
    }
}
//交换
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

//冒泡排序
void BubbleSort(int A[],int n){
    for(int i=0;i<n-1;i++){
        for(int j=n-1;j>i;j--)      //一趟冒泡过程
            if(A[j-1]>A[j]){        //若为逆序
                swap(A[j-1],A[j]);  //交换
            }
    }
}

//用第一个元素将排序序列划分成左右两个部分
int Partition(int A[],int low,int high){
    int pivot=A[low];           //用第一个元素作为枢轴
    while(low<high){            //用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;                 //返回存放枢轴的最终位置
}

//快速排序
void QuickSort(int A[],int low,int high){
    if(low<high){               //递归跳出的条件
        int pivotpos= Partition(A,low,high);    //划分
        QuickSort(A,low,pivotpos-1);    //划分左子表
        QuickSort(A,pivotpos+1,high);    //划分右子表
    }
}


int main(){
    int A[10]={49,38,65,97,76,13,27,49,12,32};

    //冒泡排序
//    BubbleSort(A,10);
//    for(int i=0;i<10;i++) cout<<A[i]<<" ";

    //快速排序
    QuickSort(A,0,9);
    for(int i=0;i<10;i++) cout<<A[i]<<" ";
    return 0;
}

---

三、 选择排序

#include<iostream>
using namespace std;

//简单选择排序
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()函数共移动元素3次
    }
}

//堆排序
//将以k为根的子树调整为大根堆
void HeadAdjust(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 BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)        //从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}


//堆排序的完整逻辑
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); //把剩余的待排序元素整理成堆
    }
}

int main(){
    int A[10]={49,38,65,97,76,13,27,49,12,32};

//    SelectSort(A,10);
//    for(int i=0;i<10;i++) cout<<A[i]<<" ";

    //堆排序
    HeapSort(A,10);
    for(int i=0;i<10;i++) cout<<A[i]<<" ";
    return 0;
}

---

四、归并排序和基数排序

#include<iostream>
#include <cstring>
#include <valarray>

using namespace std;

int n=10;
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];              //将A中所有元素复制到B中
    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);      //归并
    }
}

//基数排序(往年没考过，王道书上也没有对应代码)
void RadixSort(int a[],int n){
    int cnt[15][100005];                          //进行基数排序比较的二维数组
    int max_a=0;
    for(int i=0; i<n; i++){
        max_a = max(max_a, a[i]);                 //寻找最大关键字
    }
    int p=1;                                      //用于进行位数切割
    while(max_a){
        memset(cnt, 0, sizeof cnt);          //用于对数组进行初始化
        for(int i=0; i<n; i++)
            cnt[(a[i]/p) % 10][i] = a[i];         //对数组中的元素进行基数排序
        int l = 0;
        for (int i = 0; i < 10; i ++ ) {          //一列一列放
            for (int j = 0; j < n; j ++ ) {
                if (cnt[i][j]) a[l++] = cnt[i][j];//将结果放回a数组中
            }
        }
        p *= 10;
        max_a /= 10;
    }
}


int main(){
    int A[10]={11,43,10,7,89,10,23,78,9,10};

//    //归并排序
//    MergeSort(A,0,9);
//    for(int i=0;i<10;i++) cout<<A[i]<<" ";

    //基数排序（没考过，大概率不考代码）
    RadixSort(A,10);
    for(int i=0;i<10;i++) cout<<A[i]<<" ";
    return 0;
}

---

结语

感谢大家一直以来的不断支持与鼓励，码题集题库中的进阶塔350题正在逐步更新，之后会逐步跟进星耀，王者的题，尽请期待！！！
同时，也希望这些题能帮助到大家，一起进步，祝愿每一个算法道路上的“苦行僧”们，都能够历经磨难，终成正果，既然选择了这条路，走到了这里，中途放弃，岂不是太过可惜？

另附中国计算机学会的杰出会员、常务理事轩哥博士的B站视频讲解链接https://space.bilibili.com/518554541/?spm_id_from=333.999.0.0，供大家更好的进行学习与刷题～(￣▽￣～)~

愿你的结局，配得上你一路的颠沛流离。