数据结构-排序

数据结构

发布日期: 2023-11-03

更新日期: 2023-11-11

文章字数: 8.1k

排序的基本概念

排序算法的稳定性：若进行排序算法后，关键字相同的元素在排序之后相对位置保持不变，就称算法是稳定的，反之为不稳定。

1-1

如图1-1，若3的元素相对位置发生改变即为不稳定。

插入排序

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

直接插入排序

直接插入排序算法就是，就是一个个从左往右比较大小，将大的放在后面，小的放在前面。

算法实现代码：

void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){
        if(A[i]<A[i-1]){	//若后一位小于前一位则交换位置
            temp = A[i];
            for(j= i-1; j>=0 && A[j] > temp;--j) //检查排好序中是否有更大的数
                A[j+1] = A[j];
            A[j+1] = temp;
        }
    }
}

直接插入排序的空间复杂度为O(1)，最坏情况下时间复杂度为$O(n^2)$。

折半插入排序

由于结构是顺序存储的线性表，所以查找有序子表时可以用折半查找来实现。确定待插入位置后，就可同一地向后移动元素。

代码实现：

//该算法空出A[0]作为哨兵，A[0]不存放元素
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[0]
        low = 1;				//设置折半查找的范围
        high = i - 1 ;			//默认递增，从i后的数进行排序
        //折半查找核心代码，仅当low小于high时进行循环
        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];		//插入操作
        }
    }
}

当low>high时，折半查找停止，应将[low,i-1]内的元素全部右移，并将A[0]赋值到low所指位置。当A[mid]==A[0]时，为了保证算法的”稳定性”，应继续在mid所指位置右边寻找插入位置。

希尔排序

希尔排序的基本思想是：先将待排序表分割成若干形如$L[i,i+d,i+2,\dots,i+kd]$的“特殊”子表，即把相隔某个“增量”的记录组成一个子表，对各个子表分别进行直接插入排序，当整个表中的元素已经是“基本有序”时，再对全体记录进行一次直接插入排序。

例：

1-2

若想将图1-2进行排序，设第一趟的，$d_1=n/2=4$（n为表长，0不算做元素，为暂存单元）。则可将相离为$d_1=4$的看为同一个子表，即49和76为同一子表，38和13为同一子表，65和27为同一子表，97和49为同一子表。

1-3

然后再对各个子表进行字节插入排序，可得图1-4：

1-4

最后再放回原先表中。

1-5

再进行第二趟的处理，在原先基础上$d_2=d_1/2=4/2=2$，第二趟每个元素相隔2个元素，即49、27、76、65为同一子表，13、49、38、97为同一子表。然后再对子表进行直接插入排序，排序后可得图1-6。

1-6

后再放回原表中。

1-7

再进行第三趟，此时$d_3=d_2/2=1$，则每个元素间隔为1为一个子表，显然就是无序再拆分表，而直接对整个表进行直接插入排序。

1-8

最后就成功获得一个全局有序的递增排序的表。

希尔排序代码实现：

void ShellSort(ElemType A[],int n){
    int dk,i,j;						//dk为增量
    for(dk=n/2;dk>=1;dk=dk/2){		//假设dk=n/2为每次的缩小增量
        for(i=dk+1;i<=n;++i){
            if(A[i]<A[i-dk]){		//将A[i]插入到有序增量子表中
                A[0]=A[i];			//暂存再A[0]
                for(j=i-dk;j>0&&A[0]<A[j];j-=dk){
                    A[j+dk]=A[j];	//记录后移，查找插入的位置
                }
                A[j+dk]=A[0];		//插入
            }
        }
    }
}

希尔排序算法性能分析：

空间效率：仅使用了常数个辅助单元，空间复杂度为O(1)。

时间效率：当n在某个特定范围内，希尔排序的时间复杂度约为$O(n^{1.3})$。在最坏情况下希尔排序的时间复杂度为$O(n^2)$。

稳定性：当相同关键字的记录被划分到不同的子表时，可能会改变他们之间的相对次序，因此希尔排序是一种不稳定排序方法。

适用性：希尔排序算法仅适用于线性表为顺序存储的情况。

交换排序

冒泡排序

冒泡排序的基本思想：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即A[i-1]>A[i]），则交换他们，直到排序比较完。称这样过程为“一趟”冒泡排序。

冒泡排序算法实现：

void BubbleSort(ElemType 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]){		//若后值比前置小，则交换
                ElemType temp = A[j-1];
                A[j-1] = A[j];
                A[j] = temp;
                flag = true;
            }
        }
        if(flag==false)		//若没有进行交换，则说明表已经有序
            return;
    }
}

冒泡排序性能分析：

空间复杂度：O(1)。

时间复杂度：在最坏情况下（所有值都为逆序）则需要进行n-1趟排序，第i趟排序要进行n-i次关键字的比较。则
$$
比较次数=\sum^{n-1}{i=1}(n-i)=\frac{n(n-1)}{2}，移动次数=\sum^{n-1}{i=1}3(n-i)=\frac{3n(n-1)}{2}
$$
因此，最坏时间复杂度为$O(n^2)$，平均时间复杂度为$O(n^2)$ .

稳定性：由于i>j且A[i]=A[j]时，不会发生交换，因此冒泡排序是一种稳定的排序方法。

快速排序

快速排序的基本思想是基于分治法：在待排序表$L[1\dots n]$中任取一个元素pivot作为枢轴（或称基准，通常取首元素），通过一趟排序将待排序表划分为独立的两部分$L[1\dots k-1]$和$L[k+1\dots n]$，使得$L[1\dots k-1]$中的所有元素小于pivot，$L[k+1\dots n]$中的所有元素大于或等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一次划分。然后重复上述过程，直至每部分内只有一个元素或空为止。

例：

2-1

在图2-1中，将49设为枢轴，要将其他小于49的放在49的左半部分，大于的放在49的右半部分，从而完成一次划分。

2-2

通过low和high指针来进行，保证high指针的右边都是大于等于枢轴49的值，low指针左边都是小于枢轴49的值。

此时high指针所指元素为49，等于枢轴元素，所以high指针往左移，移到27。

2-3

而27要小于枢轴元素49，则需要放在low所指为止，即0为27，且low指针往右移。

2-4

显然此时low所指元素38也小于基准元素49，则low指针再次右移，到指向65的元素，而65要大于基准元素49，则需放到high所指位置（即6），后high指针向左移。

2-5

此时high所指元素13要小于基准49，则放到low所指位置，然后low指针右移。

2-6

而low所指元素97要大于基准49，需将97放到high所指位置，后high左移到76元素位置，而76元素也大于49，则high指针继续左移。

2-7

当low=high时，说明元素已经排序完成，可以将基准元素49放到low所指的位置。此时就完成了一次划分。接下来就是对左子表和右子表进行划分，过程基本相同，就不再过多赘述。

快速排序代码实现

void QuickSort(ElemType A[], int low , int high){
    if(low<high){		//递归结束条件
        int pivotpos = Partition(A,low,high);	//Partition()就是划分操作，将表A划分为满足上述条件的两个子表
        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(log_2n)$；最坏情况下，因为要进行n-1次递归调用，所以栈的深度为O（n）；平均情况下，栈的深度为$O(log_2n)$。

时间效率：快排的运行时间与划分是否对称有关，快排最坏情况下，对应区域基本不对称，时间复杂度为$O(n^2)$。快排的时间复杂度和递归深度息息相关，若Partition()可能做道最平衡的划分，得到两个子问题的大小都不可能大于n/2，这种情况下，平均时间复杂度为$O(nlog_2n)$。

稳定性：在划分算法中，有可能会将两个相同的值的相对位置发生变化，即快排是一种不稳定的排序算法。

选择排序

简单选择排序

简单选择排序的思想：假设排序表为$L[1\dots n]$，第i趟排序即从$L[i\dots n]$中选择关键字最小的元素与L(i)交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。

简单选择排序代码实现：

void SelectSort(ElemType A[],int n){
    for(int i=0; i<n-1; i++){		//一共进行n-1趟
        int min = i;				//记录最小元素位置
        for(int j = i+1; j<n; j++)	//在[i..n-1]中选择最小的元素
            if(A[j]<A[min]) min=j;	//更新最小元素位置
        if(min !=i){				//若当前位置的元素和最小值不同就移动位置
            int temp = A[i];
            A[i] = A[min];
            A[min] = temp;
        }
    }
}

简单选择排序效率：

空间效率：仅使用常熟个辅助单元，故空间效率为O(1)。

时间效率：在简单排序过程中不会超过3(n-1)次。但元素间比较的次数与序列的初始状态无关，始终是n(n-1)/2次，因此时间复杂度始终是$O(n^2)$。

稳定性：在第i趟找到最小元素后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。

堆排序

堆的定义如下，n个关键字序列$L[1\dots n]$称为堆，当且仅当该序列满足：

$L(i)\geq L(2i)且L(i)\geq L(2i+1)$ （大根堆）或
$L(i)\leq L(2i)且L(i) \leq L(2i+1)$ （小根堆） $(1\leq i \leq [n/2])$

例：

3-1

如图3-1，若大根堆中$i=1，则L(1)=87 \geq L(2)=45且L(1)=87 \geq L(2+1)=78 $，小根堆同理。

堆数据结构可以视为一棵完全二叉树用顺序存储后的结果，如图3-2所示

3-2

大根堆以完全二叉树视角来看，即$根\geq 左、右$。小根堆则相反，$根\leq 左、右$

堆排序的思路：

首先将存放在L[1…n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆低元素送入堆顶，此时根节点已不满足大顶堆的性质，堆被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再继续输出堆顶元素。如此反复。

而堆排序的关键就是构造初始堆。

堆构造

以大根堆为例，若有图3-3这一初始序列$L(53,17,78,9,45,65,87,32)$，并将序列以二叉树形式展示。

3-3

思路：把所有非终端结点都检查一遍，看是否满足大根堆的要求（根大于左右子树的值），不满足则进行调整，而在顺序存储的完全二叉树中，非终端结点编号$i\leq [n/2]$，图上则i=[8/2]=4。即对53，17，78，09进行检查，从右往左进行检查，从而从i=4，即09开始判断。

3-4

获取09的左孩子通过完全二叉树的性质也得左孩子=2i=2*4=8，即以8为下标的位置为09的左孩子，即32。要保证大根堆的特性，所以要将根结点和左孩子进行交换。

3-5

然后再检查i=3（结点78），根据完全二叉树的性质，左孩子=2i=2*3=6（结点65），右孩子=2i+1=6+1=7（结点87）。后再将根节点分别与左右孩子进行比较。将最大的（右孩子结点87）值与根节点交换。

3-6

同样的，最后就可以将i=1和i=2进行以大根堆性质的交换，可得最后结果。

3-7

而此时导致以53为根的子树不满足大根堆的特性，以此要再次对53为根的子树进行调整。

3-8

最后调整完成即可使整个树符合大根堆特性。

建立大根堆代码实现

//建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i = len/2; i>0; i--)		//从i=[n/2]~1 反复调整堆
        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){		//每次都将i赋值为左孩子
        if(i<len && A[i] < A[i+1]){		//左孩子比右孩子小，就用右孩子和根进行比较
            i++;
        }
        if(A[0] >= A[i]){
            break;		//根比左右孩子都大，就无需交换
        }
        else{
            A[k] = A[i];	//将左右孩子大的值调整到双亲结点上
            k = i;			//修改k的值，以便继续向下筛选
        }
    }	//for循环结束
    
    A[k] = A[0];			//被筛选结点的值放入最终位置
}

堆排序算法实现

void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);		//初始建堆
    for(int i=len; i>1; i--){	//n-1趟交换堆顶元素和堆底元素位置以及建堆过程
        int temp = A[1];		//堆顶元素和堆底元素交换
        A[1] = A[i];
        A[i]= temp;
        HeadAdjust(A,1,i-1);	//交换后再对剩下的i-1个元素整理成堆
    }
}

算法效率分析：

空间效率：仅使用了常数个辅助单元，所以空间复杂度尾O(1)。

时间效率：

设树高为h，某结点再第i层，则将这个结点向下调整最多只需要“下坠”h-i层，关键字对比次数不超过2(h-i)次，而n个结点的完全二叉树树高$h=[log_2n]+1$。

第i层最多有$2^{i-1}$个结点，而只有第1~(h-1)层的结点才有可能需要“下坠”调整（最后一层无需调整），将整棵树调整为大根堆，关键字对比次数不超过
$$
\sum^{1}{i=h-1}2^{i-1}2(h-i)=\sum^{1}{i=h-1}2^{i}(h-i)=\sum^{h-1}_{j=1}2^{h-j}j
$$
将高度$h=[log_2n]+1$带入第三式子中，得
$$
\sum2^{[log_2n]+1-j}j=\sum2^{[log_2n]+1}2^{-j}j\leq \sum2^{log_2n}2^{1-j}j=\sum 2n2^{-j}j\leq 4n
$$
所以**建堆时间复杂度为O(n)**，而每次调整的时间复杂度为O(h)，n-1趟的总时间复杂度为$O(nlog_2n)$，故平均的情况下，堆排序的时间复杂度为$O(nlog_2n)$。

稳定性：进行筛选时，有可能会调整值相同的元素，所以堆排序是不稳定的排序方法。

在堆中插入新元素

以小根堆为例，若想在堆中插入元素，会先将新元素放到表尾，与父节点对比，若新元素比父节点更小，则两者互换。再一路向上与根结点比较，直至到无法继续上升位置。

例：

3-9

在表尾插入13，需要与父节点进行比较，即和i=[9/2]=4（32元素），显然13比32小，就将13与父节点进行交换。

3-10

后13在和父节点i=[4/2]=2（17元素）对比，显然13更小，就再与父节点进行交换。

3-11

此时在与父节点i=[2/1]=1（9元素）对比，父节点9更小，就无需再进行交换。此时即满足小根堆特性，插入成功。

在堆中删除元素

以小根堆为例，若删除非表尾元素则需以表尾元素来替代删除元素的位置，后再通过不断的“下坠”来恢复小根堆的特性。

例：

3-12

在图3-12中，若想删除2位置的元素13。删除后会用表尾46来替代2位置的元素。

3-13

后再通过46和左右孩子(2i=4和2i+1=5)进行比较，恢复回小根堆的特性，依次比较可得最后结果：

3-14

归并排序和基数排序

归并排序

归并（Merge）：把两个或多个以及有序的序列合并成一个。

以二路归并（二路归并即将两个表合成一个表）为例：

4-1

将图4-1的左右两个表合并到一个新表中，可以通过设置i,j,k三个指针来实现，首先，先让i与j所指的值进行比较，即目前12>7，则将7放到k所指位置，然后使j++，i和j再进行比较。

4-2

如此反复，当j超出下标所指范围时，就只会将i所指后面的元素放入到新表中，最后即可得到最后合并的结果：

4-3

代码实现

int *B=(int *)malloc(n * sizeof(int));	//定义一个长度为n的辅助数组B
void Merge(int A[],int low,int mid ,int high){
    //表A的两段A[low...mid]和A[mid+1...high]各自有序，将它们合并成一个有序表
    int i,j,k;
    for(k=low; k<=high; k++)
        B[k] = A[k];			//将A中所有元素复制到B中
    //将 i设为第一个表中的头指针 j为第二表中的头指针  k为新表的头指针
    for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++){
        if(B[i] <= B[j])		//比较B的左右两端中的元素
            A[k]=B[i++];		//将大的赋值到k所指位置并使指针向右移
        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)		//归并
    }
}

2路归并排序算法性能分析：

空间效率：Merge()操作中，辅助单元为n个单元，所以空间复杂度为O(n)。

时间效率：每趟归并的时间复杂度为O(n)，共需进行$[log_2n]$趟归并，所以算法时间复杂度为$O(nlog_2n)$。

稳定性：由于Merge()操作不会改变相同元素的相对次序，所以归并排序是稳定的算法。

基数排序

基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法。

假设长度为n的线性表中每个结点$a_j$的关键字由d元组（$k_j^{d-1},k_j^{d-2},\dots,k_j^1,k_j^{0}$）组成，满足$0\leq k_j^i\leq r-1 \quad (0\leq j<n,0\leq i\leq d-1)$。其中$k_j^{d-1}$为最主位关键字，$k_j^0$为最次位关键字，r为基数。

以递减序列为例：

4-4

此时该表的”个十百“均有十种不同的取值（即取0,1,2,3,4,5,6,7,8,9），则基数为10。最次位关键字为个位，最主位关键字为百位。

若要对图4-4表进行基数排序，首先会新建队列，在第一趟排序中会将所有数按照”个位“进行”分配”。

4-5

如图4-5所示，从左往右按“个位”将每个关键字放到对应的队列中，后再根据队列最大的值进行收集，每个元素会从队头出队。

4-6

收集完成后会得到一个“个位”递减的序列。然后再从左往右根据”十位“进行第二趟排序。

4-7

再进行队头关键词出队收集。

4-8

就可以获得”十位“递减的序列，后再根据”百位“，进行第三趟排序。

4-9

再对该队列进行收集。

4-10

最后就可以得到一个”百位“递减的序列，同时若”百位“相等，则根据”十位“递减，同样的，”十位“相等，根据”个位“递减。就获得了一个递减的表。

基数排序算法性能分析

空间效率：一趟排序需要的辅助存储空间为r（r个队列：r个队头指针和r个队尾指针），空间复杂度为O(r)。

时间效率：基数排序需要进行d趟分配和收集，一趟分配需要O(n)，一趟收集需要O(r)（r为基数），所以基数排序的时间复杂度为O(d(n+r))。

稳定性：对于基数排序算法而言，很重要一点就是按位排序时必须是稳定的。因此基数排序一定是稳定的。

外部排序

文件通常是按块存储在磁盘上的，磁盘的读/写以”块“为单位，数据读入内存后才能被修改，修改完成后还需写回磁盘，因此在外部排序过程中的时间代价主要考虑访问磁盘的次数，即I/O数。

外部排序通常采用归并排序法，与内部排序归并相似，先将每个文件块读入缓存，再将读入的记录进行排序，将排序完的有序子文件重新写回外存，最后再对这些文件块逐趟归并，使有序子文件逐渐由小到大，直至得到整个有序文件为止。

例：

5-1

若想将图5-1中文件块有序，需先读入部分文件块使先做到部分有序。

5-2

此时读入了两块文件块，对其进行排序。

5-3

再依次放到输出缓冲区，写回磁盘中。

5-4

此时这两块文件块就是有序，即可将这两块文件块称为一个有序的”归并段“，然后依次再对剩下的文件块进行读入排序再写回。

5-5

经过16次读和16次的写，就可以获得8个有序”归并段“，此时就可以根据”归并段“进行归并排序。

5-6

此时将”归并段1“和”归并段2“中的两块子文件放入缓冲区进行排序，当凑满3个关键字就写回磁盘中。

5-7

此时就凑满3个最小关键字就写回到磁盘中，此时为了方便接下来继续使用二路归并，物理上会新建一个新文件块来存储要写回的关键字，将原先空间归还给系统。

5-8

然后继续进行归并，而当输入缓冲区有一块为空时，就会立刻从磁盘中再读新的文件快来填补。

5-9

这样就能保证归并永远是从归并段中最小的记录开始。

5-10

最后就能归并一个更长的“归并段”。

5-11

依次再将剩下的归并，可得：

5-12

然后依据这个思路，扩充为8、16个文件块为以归并段进行归并，就能获得最终有序文件。

一般情况下，外部排序中实现两两归并时，会进行大量数据读出、写入磁盘，而这会耗费大量的时间。一般外部排序的总时间 = 内部排序所需的时间 + 外存信息读写的时间 + 内部归并所需的时间。

由上二路归并所示，生成一个归并段就会进行了读、写外部信息，而读写的次数=32 + 32*3 =128（初始生成归并段进行读、写各16次，读、写各16次，共三趟归并）。

若想进行优化，可采用4归并排序，仅需2趟归并，此时外部读、写次数减至32+ 32 *2 = 96次。

结论：

对用r个初始归并段，做k路归并，则归并书可用k叉树表示，若树高为h，则$归并趟数=h-1=[\log_kr]$，若k越大，r越小，归并趟数越少，读写磁盘次数越少。

败者树

败者树可视为一棵完全二叉树。k个叶结点分别是当前参加比较的元素，非叶子结点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较（即让更小的进行下一步比较，根节点为要比较的结点中最小的值），一直到根结点。

例：

5-13

败者树中会将每个归并段中第一个最小的关键字进行比较，更小的将继续上升继续下一轮比较。

5-14

从左往右看27和12进行比较，12失败，记录失败者的归并段1，12进行下一场比拼。1和17比较，1失败，记录失败者的归并段4，1进入下一场比拼。2和9比较，2失败，记录失败者的归并段6，2进行下一场比拼。11和4比较，4失败，记录失败者的归并段7，4进入下一场比拼，每次都会进行最小关键字的比较，比较到最后可得最小关键字为1，来自归并段3（树中放的是关键字来自哪个归并段）。

5-15