排序

1.基本概念

排序：就重新排列表汇总的元素，使表中的元素满足按关键字有序的过程

稳定性

算法的稳定性，若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi = keyj，且在排序前Ri在Rj的前⾯，若使⽤某⼀排序算法排序后，Ri仍然在Rj的前⾯，则称这个排序算法是稳定的，否则称排序算法是不稳定的

2.插入排序

算法思想

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

实现代码

//直接插入排序法一
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;
    for(i=2;i<n;i++)     //将各个元素插入到已经排好序的序列中
    {
        if(A[i]<A[i-1])   //若A[i]关键字小于前驱
        {
            A[0]=A[i];     //用A[0]暂存A[i]
            for(j=i-1;A[0]<A[j];--j)   //检查所有前面已排号序的元素
                A[j+1]=A[j];   //所有大于A[0]的元素都往后挪
            A[j+1]=A[0];    //复制到插入的位置
        }
    }
}

算法效率分析

算法优化——折半插入查找

//直接插入排序法二  哨兵法
void InsertSort(int A[],int n)
{
    int i,j,low,high,mid;
    for(i=2;i<n;i++)     //将各个元素插入到已经排好序的序列中
    {
        A[0]=A[i];
        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];     
    }
}

3.希尔排序

算法思想

希尔排序：先将待排序表分割成若⼲形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”⼦表，对各个⼦表分别进⾏直接插⼊排序。缩⼩增量d，重复上述过程，直到d=1为⽌。

实现代码（考察频率不高）

//希尔排序
void ShellSort(int A[],int n)
{
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d=d/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[j];   //记录后移，查找插入的位置
                }
                A[j+d]=A[0];    //插入
            }
        }
    }
}

算法效率分析

稳定性

4.冒泡排序

算法思想

基于“交换”的排序：根据序列中两个元素关键字的⽐较结果来对换这两个记录在序列中的位置

实现代码

//交换
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=ture
            }
        }
        if(flag==false)
            return;   //本次遍历后没有发生交换，说明表是已经有序的了
    }
}

算法效率分析

5.快速排序（重点）

算法思想

在待排序表L[1…n]中任取⼀个元素pivot作为枢轴（或基准，通常取⾸元素），通过⼀趟排序将待排序表划分为独⽴的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素⼩于pivot，L[k+1…n]中的所有元素⼤于等于 pivot，则pivot放在了其最终位置L(k)上，这个过程称为⼀次“划分”。然后分别递归地对两个⼦表重复上述过程，直⾄每部分内只有⼀个元素或空为⽌，即所有元素放在了其最终位置上。

实现代码

//用第一个元素将待排序序列划分成左右两个部分
int Partiton(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=Partiton(A,low,high);   //划分
        QuickSort(int A[],int low,int high);  //划分左子表
        QuickSort(int A[],int low,int high)  //划分右字表
    }
}

算法效率分析

6.简单选择排序

算法思想

每⼀趟在待排序元素中选取关键字最⼩的元素加⼊有序⼦序列

实现代码

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

算法效率分析

7.堆排序

堆的定义

若n个关键字序列L[1…n] 满⾜下⾯某⼀条性质，则称为堆（Heap）：

① 若满⾜：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 ）—— ⼩根堆（⼩顶堆）

建立大根堆实现代码

//建立大根堆
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];           //被筛选结点的值放入最终位置
}

基于大根堆的排序代码实现

//建立大根堆
void BuildMaxHeap(int A[],int len)
    
//将 以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int 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);   //把剩余的待排序元素整理成堆
    }
}

算法效率分析

堆的插入

堆的删除

8.归并排序

算法思想

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

实现代码

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);   //归并
    }
}

算法效率分析

9.基数排序

算法思想

假设长度为n的线性表中每个结点aj的关键字由d元组组成，其中：

0≤kij≤r-1(0≤j＜n，0≤i≤d-1)，r称为“基数”

实现举例

实现代码

typedef struct LinkNode
{
    ElemType data;
    struct LinkNode *next;
}LinkNode,*LinkList;

typedef struct   //链式队列
{
    LinkNode *front,*rear;   //队列的队头和队尾指针
}LinkQueue;