[数据结构与算法] 数据结构—

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构——3. 排序 -> 正文阅读

[数据结构与算法]数据结构——3. 排序

PS:《大话数据结构》第九章笔记

一、冒泡排序

1. 冒泡排序基本思想：

两两比较相邻记录的关键字，反序则交换，直到没有反序的记录

2. 基本冒泡排序算法：

例如由小到大排列： 从后往前循环，若前者大于后者，则交换
在这里插入图片描述

3. 冒泡排序优化：

可能会出现序列已经有序，不需要再多进行判断的情况，此时可以增加一个flag来帮助减少多余步骤

int i,j;
bool flag=true;
for (i=1;i=s.length()-1;i++) {
	flag=false;
	for (j=s.length()-1;j>=i;j--){
		if(s[j]>s[j+1]){
			swap(s[j],s[j+1]);
			flag=true;
		}
	}
}

4. 复杂度

最坏的情况即倒序，需要比较 $1 + 2 + 3 + . . . + n ? 1 = n (n ? 1) / 2$ 次，因此时间复杂度为 $O(n^{2})$

二、简单选择排序

1. 简单选择排序

通过n-i次关键字比较，从n-i+1个记录中选择出最小，并与第i个记录交换。
例如：

int i,j,min;
for (i=1;i<s.length();i++) {
    min =i;   //当前下标定义为最小下标
    for (j=i+1;j<s.length();j++) {
        if（s[min]>s[j）{
                min = j;   //更新最小值
        }
    if (i!=min){  //说明找到最小值
            swap(s[i],s[min]);
        }            
    }
}

复杂度分析：

没有最好最坏情况，第i趟排序需要n-i次，因此总共需要 $n ? 1 + n ? 2 + . . . + 2 + 1 = n (n ? 1) / 2$ 次。时间复杂度为 $O(n^{2})$ 。

简单排序性能略优于冒泡排序

三. 直接插入排序

含义：将一个记录插入到已经排好序的列表当中，从而得到一个新的，记录数加1的表
例如：

int i,j,len=s.length();
for (i=2;i<=len;i++) {
    if (s[i]<s[i-1]) {
        s[0]=s[i];  // 设置哨兵
        for (j=i-1;s[j]>s[0];j--) {
            s[j+1]=s[j];  //整体后移
        }
        s[j+1]=s[0];   //插入到正确位置
    }
}

图示：
在这里插入图片描述

复杂度分析：
最坏的情况即排序表逆序，因此总共需要 $2 + 3 + 。。。 + n = (n + 2) (n ? 1) / 2$ 次。时间复杂度为 $O(n^{2})$ 。

直接插入排序性能略优于冒泡排序和简单排序。

四. 希尔排序

含义：将相隔某增量的记录形成一个子序列，从而实现跳跃式的移动，增加排序的效率。
相当于直接插入排序的升级，属于插入排序类。
例如：

int i,j;
int inc=l.length();   //代表增量序列
do {
    inc = inc/3+1;    //增量的算法不固定
    for (i=inc+1;i<=l.length();i++) {
        if (l[i]<l[i-inc]){
            //将l[i]插入有序增量子表
            l[0]=l[i];      //暂存在l[0]
            for (j=i-inc;j>0&&l[0]<l[j];j-=inc){
                l[j+inc]=l[j];  //记录后移，找插入位置   
            }
            l[j+inc]=l[0];   //插入
        }
    }
}
    while(inc>1);

注意事项：最后一个增量必须为1
复杂度分析：
时间复杂度为 $O(n^{3/2})$ 。

希尔算法不是一种稳定的排序算法，但突破了慢速排序。

五、堆排序

1.堆

堆是具有下列形式的完全二叉树：
每个结点的值都大于或等于其左右孩子节点的值——大顶堆
每个结点的值都小于或等于其左右孩子节点的值——小顶堆

——根节点一定是堆中所有节点的最大/小值

2. 堆排序

将待排的序列构造成一个大顶堆，此时的最大值为顶堆根节点。将其移走（与末尾交换，把末尾变成最大值），在将剩余的n-1个序列重新构造成大顶堆，不断反复。
属于简单选择排序的升级，同属于选择排序类。

void HeapSort (SqList *L)
{
    int i;
    for (i=L->length/2;i>0;i--) {
        HeapSort(L,i,L->length);   // 构造大顶堆
    }
    for (i=L->length;i>1;i--) {
        swap(L,1,i);  //堆顶和最后一个交换
        HeapSort(L,1,i-1);   //剩余重新构造大顶堆
    }
}

void HeapSort(SqList *L,int s,int m){
    int temp,j;
    temp = L->r[s];
    for (j=2*s;j<=m;j*=2){       //沿着关键字较大的孩子节点向下筛选
        if (j<m && L->r[j] < L->r[j+1]) {
            j++;             //j：关键字较大的记录下标
        }
        if (temp>=L->r[j]) {
            break;       //插入在位置s上
        }
        L->r[s] = L->r[j];
        s=j;
    }
    L->r[s]=tem;    //插入
}

在这里插入图片描述

3.时间复杂度分析

构建堆：从最下最右的非终端结点开始，与其孩子进行比较，有需要则互换。时间复杂度为 $O (n)$
排序：第i次取堆顶重建堆需要 $O (l o g i)$ ，并需要取n-1次堆顶记录

总计时间复杂度为： $O (n l o g n)$ (无论最好、最坏还是平均)

六、归并排序

1. 含义

假设初始序列有n个记录，则看成是n个子序列，长度为1；然后两两合并，得到[n/2]个长度为2或者1的有序子序列；再两两合并，重复到一个长度为n的有序序列为止。这种方法称为2路归并排序。

2. 基本算法：

void MargeSort(SqList *L) {
    MSort(L->r,L->r,L->length);
}

//将SR归并为TR1
void MSort(int SR[],int TR1[],int s, int t) {
    int m;
    int TR2[MAXSIZE+1];
    if (s==t) {
        TR1[s]=SR[s];
    }
    else {
        m=(s+t)/2;   //进行平分,将SR[s，t]分成SR[s，m]和SR[m+1，t]
        MSort(SR,TR2,s,m);   //递归将SR[s，m]归并成有序的TR2[s，m]
        MSort(ST,TR2,m+1,t);
        Merge(TR2,TR1,s,m,t);
        // 将TR2[s，m]，TR2[m+1，t]归并到TR1[s，t]
    }
}


//归并函数：将TR2[s，m]，TR2[m+1，t]归并到TR1[s，t]
void Merge(int SR[],int TR[],int i, int m,int n) {
    int j,k,l;
    // 将SR从小到大归并到TR
    for (k=i,j=m+1;i<=m&&j<=n;k++) {
        if (SR[i]<SR[j]) {
            TR[k]=SR[i++];
        }
        else{TR[k]=SR[j++];}
    }
    if  (i<=m) {
        for (l=0;l<=m-i;l++) {
            TR[k+l]=SR[i+l];
        }
    }
    
    if (j<=n) {
        for (l=0;l<n-j;l++) {
            TR[k+l]=SR[j+l];
        }
    }
}

在这里插入图片描述

3.复杂度分析

一趟归并需要两两合并并存放结果，需要将所有记录扫一遍，需要 $O (n)$ ;
由完全二叉树深度可知，整个归并排序需要 $O(log_2n)$ ;

–>时间复杂度为： $O (n l o g n)$ ;
由于在归并中需要与原始记录序列同样的数量的存储空间存放归并结果以及递归时深度为log2n的栈空间，

–>空间复杂度： $O (n + l o g n)$ ;

归并排序是一种较占用内存，但效率高且稳定的算法

4. 非递归实现归并排序

从最小的数列开始归并，直至完成

void MergeSort2(SqList *L)
{
    int* TR=(int*)malloc(L->length*sizeof (int)); // 申请额外空间存放结果
    int k=1;
    while(k<L->length) {
        MergePass(L->r,TR,k,L->length);
        k=2*k;    //子序列加倍
        MergePass(TR,L->r,k,L->length);
        k=2*k;    //子序列加倍
    }
}

void MergePass(int SR[],int TR[],int s,int n){
    int i=1;
    int j;
    while(i<=n-2*s+1) {
        Merge(SR,TR,i,i+s-1,i+2*s-1);  //两两归并
        i= i+2*s;
    }
    if (i<n-s+1) {Merge(SR,TR,i,i+s-1,n);}  //归并最后两个子序列
    else {                   //如果只剩下单个的子序列
        for (j=i;j<=n;j++) {
            TR[j]=SR[j];
        }
    }
}

七、快速排序

1. 含义

基本思想：
通过一趟排序，将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对两部分记录继续进行排序，从而达到整体有序的目的。
输于冒泡排序的升级，都属于交换排序类。

2. 基本算法

选择一个枢轴
使用partition函数，将枢轴放在合适的位置，使得其左边都是比枢轴小的数，右边都比枢轴大
对左右部分进行同样的partition操作

void QuickSort(SqList *L) {
    Qsort(L,1,L->length);
}

//对r[low,...,high]做快速排序
void QSort(SqList *L,int low, int high) {
    int pivot;
    if(low<high) {     //low,high不断更换位置
        pivot=Partition(L,low,high);
        // 将r[low,...,high]一分为二算出枢轴值pivot
        QSort(L,low,pivot-1);   //对低子表递归排序
        QSort(L,pivot+1;high);  //对高子表递归排序
    }
}

int Partition(SqList *L,int low,int high) {
    int pivotkey;
    pivotkey = L->r[low];    //用子表的第一个做枢轴
    while(low<high) {     //两端交替向中间扫描
        while(low<high&&L->r[high]>=pivotkey) {
            high--;
        }
        swap(L,low,high);  //比枢轴小的交换到低端
        while(low<high && L->r[low]<=pivotkey)
            low++;
        swap(L,low,high); //比枢轴大的交换到高端
    }
    return low;         //返回枢轴所在位置                                                                        
}

3. 复杂度分析

最优情况：
partition划分平均，时间复杂度和空间复杂度都为 $O (n l o g n)$ .
最坏情况：
正序或逆序，每次只变化一个位置，一个子序列为空。时间复杂度为 $O(n^{2})$ ，空间复杂度 $O (n)$ 。

4. 快排优化

4.1 优先选取枢轴

排序快慢取决于第一个关键字在整个序列中的大小位置，如果过大或者过小，就会影响性能。
–> 改进办法：
三数取中法：
随机取三个数先排序，再将中间的数作为枢轴
例如在partition代码的第3，4行中间加入：

int pivotkey;
//添加：
int m=low+(high-low)/2;
if (L->r[low] > L->r[high]) 
	swap(L,low,high);
if (L->r[m] > L->r[high])
	swap(L,high,m);
if (L->r[m] > L->r[low])
	swap(L,m,low);

类似还有九数取中法：分三次取三个数，各自取出中数，再从这三个数中取中数。

4.2 优化不必要的交换

将pivotkey备份到L.r[0]中，并把代码中的交换改为替换，可以减少多次交换的操作。

int Partition1(SqList *L,int low,int high) {
    int pivotkey;
    //省略三数取中代码
    pivotkey = L->r[low];    //用子表的第一个做枢轴
    L->r[0]=pivotkey；   //进行备份
    while(low<high) {     //两端交替向中间扫描
        while(low<high&&L->r[high]>=pivotkey) {
            high--;
        }
        L->r[low]=L->r[high];   //使用替换而不是交换
        while(low<high && L->r[low]<=pivotkey)
            low++;
        L->r[high]=L->r[low]; //使用替换而不是交换
    }
    L->r[low]=L->r[0];  //将枢轴替换回去
    return low;         //返回枢轴所在位置                                                                        
}

4.3 优化小数组时的排序

在数组比较小时，可以选择使用直接插入。
可以改进为：当high-low大于某个常数时，使用快速排序，而小于等于某常数时，使用直接插入排序。

4.4 优化递归操作

尽量减少递归，实施尾递归，来优化性能。
改进代码：

void QSort(SqList *L,int low,int high) {
    int pivot;
    if ((high-low)>length){  //长度阈值
        while(low<high) {
            pivot = Partition1(L,low,high);
            QSort1(L,low,pivot-1);
            low = pivot+1;
        }
    }
    else
        InsertSort(L);
}