排序（数据结构）

同样是复习总结。

基本概念

概念：就是重新排列列表中的元素，使表中的元素满足按关键字递增或递减的过程。
算法的稳定性：简单来说就是原本列表中的两个相同元素经过排序算法后，如果没有发生位置变化，则称该算法是稳定的；反之则不稳定。
注：
1.算法是否具有稳定性并不能衡量一个算法的优劣，它主要是对算法的性质进行描述。
2.对于不稳定的排序算法，只需举出一组关键字的实例，说明它的不稳定性即可。
排序根据数据元素是否完全在内存中，可分为内部排序和外部排序。
内部排序：在排序期间元素全部存放在内存中的排序。
外部排序：在排序期间元素无法全部同时存放在内存中，必须在排序过程中根据要求不断地在内、外存之间移动的排序。

在今天只是对内部排序进行复习。

内部排序的操作：比较和移动。（并不是所有的内部排序算法都要基于比较，例如：基数排序）
内部排序算法的性能却决于算法的时间复杂度和空间复杂度，而时间复杂度一般是由移动的次数来决定的。

直接插入排序（插入排序）

算法

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

性能分析

空间效率：O(1)
时间效率：O(n²)
稳定性：稳定
适用性：顺序储存和链式储存

折半插入排序（插入排序）

算法

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

性能分析

空间效率：O(1)
时间效率：O(n²)
稳定性：稳定
适用性：顺序储存

希尔排序（插入排序）

算法

//希尔排序
void ShellSort(ElemType A[],int n){
    //对顺序表作写入插入排序，本算法和直接插入排序相比，做了以下修改：
    //1.券后记录位置的增量是dk，不是1
    //2.r[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(dk=n/2;dk>=1;dk=dk/2){                  //步长变化
        for(i=dk+1;i<=n;kd=dk/2){
            if(A[i].key<A[i-dk].key){           //需将A[i]插入有序增量子表
                A[0] = A[i];                    //暂存在A[0]
                for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk){
                    A[j+dk] = A[j];
                }
                A[j+dk] = A[j];
            }//if
        }
    }
}

性能分析

空间效率：O(1)
时间效率：O(n²)
稳定性：不稳定
适用性：顺序储存

冒泡排序（交换排序）

算法

//冒泡排序
void BubbleSort(ElemType A[],int n){
    for(i=0;i<n-1;i++){
        flag = false;
        for(j=n-1;j>i;j--){
            if(A[j-1].key>A[j].key){
                swap(A[j-1],A[j]);
                flag = true;
            }
        }
        if(flag==false){
            return;
        }
    }
}

性能分析

空间效率：O(1)
时间效率：O(n²)
稳定性：稳定
适用性：顺序储存
特点：每一趟排序都会将一个元素放置到其最终的位置上。

快速排序（交换排序）

算法

//快速排序
void QuickSort(Element 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 Partition(ElemType A[],int low,int high){
    //一趟排序过程
    ElemType  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;                                  //返回存放数轴的最终位置
}

性能分析

空间效率：最坏情况O(n)；平均情况O(log2n)
时间效率：O(n²)
稳定性：不稳定
适用性：顺序储存
特点：每一趟排序都会将一个元素放置到其最终的位置上。

简单选择排序（选择排序）

算法

//简单选择排序
void SelectSort(ElemType A[],int n){
    //对表A作简单选择排序，A[]从0开始存放元素
    For(i=0,i<n-1;i++){                         //一共进行n-1趟
        min = i;                                //记录最小元素位置
        for(j=i+1;j<n;j++)                      //在A[1···n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
        if(min!=i)
            swap(A[i],A[min]);
    }
}

性能分析

空间效率：O(1)
时间效率：O(n²)
稳定性：不稳定
适用性：顺序储存

堆排序（选择排序）

这是一种树形选择排序方法，特点：子啊排序过程中，将L[1…n]看成是一棵完全二叉树的顺序储存结构，利用完全二叉树中双亲结点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。
小根堆（小定堆）
大根堆（大定堆）

建立大根堆的算法

//建立大根堆
void BuildMaxHeap(ElemType A[],int len){
    for(int i=len/2;i>0;i--){                     //从i=[n/2]~1,反复调整堆
        AdjustDown(A,i,len);
    }
}

向下调整算法

//向下调整算法
void AdjustDown(ElemType A[],int k,int len){
    A[0] = A[k];                                  //A[0]暂存
    for(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值，以便继续向下筛选
        }
    }//for
    A[k] = A[0];                                  //被筛选结点的值放入最终位置
}

向上调整算法

//向上调整算法
void AdjustUp(ElemType A[],int k){
    A[0] = A[k];
    int i = k/2;                                  //若结点值大于双亲结点，则将双亲结点向下调，并继续向上比较
    while(i>0&&A[i]<A[0]){                        //循环跳出条件
        A[k] = A[i];                              //双亲结点下调
        k = i;
        i = k/2;                                  //继续向上比较
    }//while
    A[k] = A[0];                                  //复制到最终位置
}

堆排序的算法

// 堆排序算法
void HeapSort(ElemType A[],int len){
    BuildMaxHeap(A,len);                          //初始创建
    for(i=len;i>1;i--){                           //n-1趟的交换和建堆过程
        swap(A[i],A[1]);                          //输出堆顶元素（和堆低元素交换）
        AdjustDown(A,1,i-1);                      //整理，把剩余的i-1个元素整理成堆
    }//for
}

性能分析

空间效率：O(1)
时间效率：O(nlog2n)
稳定性：不稳定
适用性：顺序储存

归并排序

Merge算法

//Merge函数
ElemType *B = (ElemType *)malloc((n + 1) * sizeof(ElemType));      //辅助数组B
void Merge(ElemType A[],int low,int mid,int high){
    //表A的两段各自有序，将它们合成一个有序表
    for(int 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])                            //比较B的左右两段中的元素
            A[k] = B[i++];                        //将较小值复制到A中
        else
            A[k] = B[j++];
    }//for
    while(j<=mid)
        A[k++] = B[i++];                          //若第一个表未检测完，复制
    while(j<=high)
        A[k++] = B[j++];                          //若第二个表未检测完，复制
}//注：这里最后的两个while循环只有一个会执行

排序算法

//排序算法（2路）
void MergeSort(ElemType A[],int low,int high){
    if(low<high){
        int mid = (low + high)/2;                 //从中间划分两个子序列 
        MergeSort(A,low,high);                    //对左侧子序列进行递归排序
        MergeSort(A,mid+1,high);                  //对右侧子序列进行递归排序
        Merge(A,low,mig,high);                    //归并
    }
}

性能分析

空间效率：O(n)
时间效率：O(nlog2n)
稳定性：稳定
适用性：顺序储存

基数排序

性能分析

空间效率：O(r)（r是队列的个数）
时间效率：O(d(n+r))（特点：跟序列的初始状态无关）
稳定性：稳定
适用性：顺序储存

各种排序的比较及应用

各种排序算法的性质

算法种类	时间复杂度			空间复杂度	是否稳定
算法种类	最好情况	平均情况	最坏情况	空间复杂度	是否稳定
直接插入排序	O(n)	O(n²)	O(n²)	O(1)	是
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	是
简单选择排序	O(n²)	O(n²)	O(n²)	O(1)	否
希尔排序	O(n²)	O(n²)	O(n²)	O(1)	否
快速排序	O(nlog2n)	O(nlog2n)	O(n²)	O(log2n)	否
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	否
2-路归并排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	是
基数排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O(r)	是