数据结构（第八章）

排序

一、插入排序

1.1、直接插入排序

• 直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

代码展示：

#define MaxSize 100
//定义一个顺序表结构
typedef struct {
    int data[MaxSize+1]; //定义一个排序数组，data[0]位用作哨兵或临时变量
    int length; // 用来记录顺序表的长度
}SqList;
//直接插入排序
void InsertSort( SqList &L ){
         int i ,j;
    for (i = 2; i <=L.length ; ++i) { //从二号位开始，0号位为哨兵 ， 1号位当初始的时候默认为有序
        if (L.data[i]<L.data[i-1]) //按照升序的排列方式排序
        {
            L.data[0]=L.data[i]; //将小的这个元素，放到哨兵位置临时存储
            for (j = i-1; L.data[j]>L.data[0] ; --j)  //从后往前查找待插入的位置
                    L.data[j+1]=L.data[j]; //将元素依次向后移动
            L.data[j+1]=L.data[0]; //将哨兵处的元素插入到正确的位置
        }
    }
}

• 时间复杂度：O（n^2）
• 稳定性：由于每次插入元素时，总是从后向前先比较再移动，所以不会出现相同元素相对位置发生变化的情况，即直接插入排序是一个比较稳定的算法。
• 适用性：顺序和链式存储的线性表。

1.2、折半插入排序

• 从直接插入排序算法中，不难看出每趟插入的过程中都进行了两项工作：①从前面的有序子表中查找出待插入元素应该被插入的位置；②给插入位置腾出空间，将待插入元素复制到表中的插入位置。注意到在该算法中，总是边比较边移动元素。下面将比较和移动操作分离，即先折半查找出元素的待插入位置，然后统一地移动待插入位置之后的所有元素即折半插入排序。

代码展示：

//折半插入排序
void BinaryInsertSort(int A[] , int n){ //A表示待排数组，n表示数组中元素个数
    int i , j ,low ,high ,mid;
    for ( i = 2; i <=n ; ++i) { //依次将A[2]~A[n]的元素排序插入到数组中
        A[0]=A[i]; //将带排元素存入到哨兵中
        low=1;
        high=i-1; //设置折半查找的范围
        while(low<=high) //折半查找，默认递增序列
        {
            mid=(low+high)/2; //取中间值
            if (A[0]>mid)
                low=mid+1;
            else
                high=mid-1;
        }
        for ( j = i-1; j>=high+1 ; j) //统一后移元素
            A[j+1]=A[j];
        A[j+1]=A[0]; //将元素插入到正确位置
    }
}

• 时间复杂度：O（n^2）
• 稳定性：稳定的算法

1.3、希尔排序

• 希尔排序又称缩小增量排序，其思想是将原本有大量记录数的记录进行分组。分割成若干子序列，此时每个子序列待排序的记录个数就比较少，然后在这些子序列中分别进行直接插入排序，当整个序列基本有序时，再对全体进行一次直接插入排序。
• 基本有序：就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。

代码展示：

//希尔排序
//对顺序表 L 进行一趟希尔排序, 增量为 d
void ShellSort(int L[],int n,int d)
{
    for(int j=d+1;j<=n;j++)
    {
        L[0]=L[j];//用L[0]来存储我们待排序的数据,此时的L[0]只用作存储临时元素，不用做哨兵
        int k=j-d; //前一位元素的下标
        while(k>=0&&L[0]<L[k])//从下标为0开始存储
        {
            L[k+d]=L[k];
            k=k-d;//依次移动d个位置
        }
        L[k+d]=L[0];
    }
}

• 时间复杂度： O（n^3/2）

二、交换排序

2.1、冒泡排序

• 冒泡排序：从后往前（从前往后）两两比较相邻元素的值，若为逆序（A[i]>A[i-1]）则进行交换,直到没有逆序的记录为止。

代码展示：

//冒泡排序
void BubbleSort( int A[] , int n){
    bool flag; //用于记录本次冒泡是否发生过交换
    for (int i = 0; i < n - 1; ++i) {
        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 ; // 如果遍历后没有发生交换，说明已经有序
        }
    }
}

• 时间复杂度：O（n^2）
• 空间复杂度：O（1）
• 稳定性：不稳定的算法

2.2、快速排序

• 快速排序的基本思想：通过一趟排序将待记录分割成独立的两部分，其中一部分记录关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

代码展示：

//快速排序
//1. 对表中元素进行划分
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; //将枢轴元素插入到特定位置，即low==high的位置处
    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);
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：Q(logn)(平均)
• 稳定性：不稳定

三、选择排序

3.1、简单选择排序

• 简单选择排序思想：每一趟从总选出关键字最小的元素，作为有序子序列的第i个元素（i=1,2,···）,依次循环选择。

代码展示：

//简单选择排序
void SelectSort(int A[],int n){
    int i ,j;
    int min; //用于记录最小元素的位置
    for ( i = 0; i <n-1 ; ++i) { //一共进行n-1次
        min=i;
        for ( j = i+1; j <n ; ++j)//选择其中最小的元素
            if (A[j]<A[min])
                min=j; //交换最小元素的位置
        if (min!=i) //如果最小元素的位置不等，则交换位置
            swap(A[i],A[min]);
    }
}

• 时间复杂度：O(n^2)
• 空间复杂度：O（1）
• 稳定性：不稳定

3.2、堆排序

• 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大根堆；每个结点的值都小于或等于其左右孩子结点的值称为小根堆。
• 堆排序的基本思想：堆排序就是利用堆（假设利用大顶堆）进行排序的方法。将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

代码展示：

//堆排序
//采用大根堆的方式进行堆排序
void HeapSort(int A[] , int len){
    //构建大根堆
    for (int i = len/2; i >0 ; i--) { //len/2表示的所有非终端结点中的最大值，即前len/2项都为非终端结点
         HeadAdjust(A,i,len);
    }
    for (int i = len; i >1 ; i--) {
        swap(A[1],A[i]);  //将当前栈顶元素与最后一位元素交换位置
        HeadAdjust(A,i,i-1); //将剩余的前i-1项元素再次创建成大根堆
    }
}
void HeadAdjust(int A[] ,int k, int len){ //len表示数组长度
     A[0]=A[k]; //A[0]暂存子树的根结点，防止被覆盖
     int i;
    for ( i =2*k; i <=len ; i*=2) { //2*k代表这k的左孩子结点，沿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];  //被筛选结点的值放入最终位置
}

• 时间复杂度：O（nlogn）
• 空间复杂度：O（1）
• 稳定性：不稳定

四、归并排序和基数排序

4.1、归并排序

• 定义：归并排序（Merging Sort）就是利用归并的思想实现的排序方法。它的原理是假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（x表示不小于x的最小整数）个长度为2或1的有序子序列；再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止，这种排序方法称为2路归并排序

代码展示（二路归并）：

递归版

//归并排序(递归版)
#define MaxSize 100 //定义临时数组的最大范围
int B[MaxSzie+1];
void Merge(int A[], int low,int mid , int high){
    int i ,j,n;
    for (int k = low; k <=high ; k++) {
        B[k]=A[i]; //将A数组中的元素全部存入到临时数组中，对临时数组B进行归并操作
    }
    for ( i = low, j=mid+1, n=i ;i<=mid&&j<=high;n++ ) {
        if (B[i]<=B[j]) //比较左右两段中的元素，选择较小的插入到元素组中
            A[n]=B[i++];
        else
            A[n]=B[j++];
    }
    while(i<=mid)A[n++]=B[i++]; //检测两表中未检测完的元素
    while(j<=high)A[n++]=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); //归并
    }
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O（n）
• 稳定性：稳定

4.2、基数排序（了解）

• 定义：基数排序是一种借助多关键字排序的思想对单逻辑关键字排序的方法。

考到的概率很小，这里就不再赘述。