数据结构学习笔记-十大排序算法

1.插入排序

直接插入排序

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

2.希尔排序

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

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++){
        bool flag=false;    //表示本趟冒泡是否发生交换的标志
        for(int j=n-1;j>i;j--)    //一趟冒泡过程
            if(A[j-1]>A[j]){    //若为逆序
                swap(A[j-1],A[j]);    //交换
                flag=true;
            }
        if(flag==false)
            return;    //本趟遍历后没有发生交换，表明已经有序
    }
}

4.快速排序

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

5.简单选择排序

//简单选择排序
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;
}

6.堆排序

//建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--)    //从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}
 
//将以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];    //被筛选结点的值放入最终位置
}

7.归并排序

归并：把两个或多个已经有序的序列进行排序

核心操作：把数组内的两个有序序列归并为一个

int *B=(int *)malloc(n*sizeof(int));    //辅助数组B
 
//A[low...mid]和[mid+1...high]各自有序，将两个部分归并
void Merge(int A[],int low,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++];
    }//for
    while(i<=mid)
        A[k++]=B[j++];
    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);    //归并
    }//if
}

8.基数排序

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

初始化：设置r个空队列，Qr-1，Qr-2，... ，Q0

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

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

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

9.外部排序

“归并排序”要求各个子序列有序，每次读入两个块的内容，进行内部排序后写回磁盘。

步骤：生成r个初始归并段（对L个记录进行内部排序，组成一个有序的初始归并段）

进行S趟k路归并，把k个归并段的块读入k个输入缓冲区，用“归并排序”的方法从k个归并段中选出几个最小记录，暂存到输出缓冲区中，当输出缓冲区满时，写出外存。

10.置换-选择排序

步骤：

设初始待排文件为FI，初始归并段输出文件为FO，内存工作区为WA，FO和WA的初始状态为空，WA可容纳w个记录到工作区WA。

1）从FI输入w个记录到工作区WA。

2）从WA中选出其中关键字取最小值的记录，记为MINIMAX记录。

3）将MINIMAX记录输出到FO中去。

4）若FI不空，则从FI输入下一个记录到WA中。

5）从WA中所有关键字比MINMAX记录的关键字大的记录中选出最小关键字记录，作为新的MINIMAX记录。

6）重复3）~5），直至在WA中选不出新的MINIMAX记录为止，由此得到一个初始归并段，输出一个归并段的结束标志到FO中去。

7）重复2）~6），直至WA为空。由此得到全部初始归并段。