IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 8.【史上最全内部排序算法】(直接插入、折半插入、希尔) +(冒泡、快速)+(简单选择、堆{含元素的增删})+(归并)+ (基数)排序 + 对比总结 -> 正文阅读

[数据结构与算法]8.【史上最全内部排序算法】(直接插入、折半插入、希尔) +(冒泡、快速)+(简单选择、堆{含元素的增删})+(归并)+ (基数)排序 + 对比总结

排序

排序:重新排列表中的元素,使表中元素满足按关键字有序的过程。

排序算法的评价指标:时间复杂度、空间复杂度、稳定性。

算法的稳定性:关键字相同的元素在使用某一排序算法之后相对位置不变,则称这个排序算法是稳定的,否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
在这里插入图片描述

排序算法的分类
内部排序 : 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 :排序期间元素无法全部同时存在内存中,必须在排序的过程中根据要求,不断地在内、外存之间移动——关注如何使时间、空间复杂度更低,如何使读/写磁盘次数更少。

各自排序算法演示过程参考:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html



1. 插?排序

(稳定)1.1 直接插入排序【适用于顺序存储和链式存储的线性表】

基本操作就是:将有序数据后的第一个元素 插入到 已经排好序的有序数据中 从而得到一个新的、个数加一的有序数据

算法解释:(从小到大)
在这里插入图片描述

算法三个步骤:

先保留要插入的数字
往后移
插入元素

// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1; i<n; i++)
    {
    	//如果是A[i-1] <= A[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];    //所有大于temp的元素都向后挪
                
            A[j+1]=temp;//插入元素
        }
    }
}

用算法再带入这个例子,进行加深理解
在这里插入图片描述

带哨兵:
在这里插入图片描述

补充:对链表L进行插入排序

void InsertSort(LinkList &L){
    LNode *p=L->next, *pre;
    LNode *r=p->next;
    p->next=NULL;
    p=r;
    while(p!=NULL){
        r=p->next;
        pre=L;
        while(pre->next!=NULL && pre->next->data<p->data)
            pre=pre->next;
        p->next=pre->next;
        pre->next=p;
        p=r;
    }
}

时间、空间复杂度

在这里插入图片描述

最好情况: 共n-1趟处理,每?趟只需要对?关键字1次,不?移动元素
最好时间复杂度—— O(n)

最坏情况: 【感觉第1趟:对?关键字2次,移动元素1次? 】
第1趟:对?关键字2次,移动元素3次
第2趟:对?关键字3次,移动元素4次

第 i 趟:对?关键字 i+1次,移动元素 i+2 次
最坏时间复杂度——O(n2)

在这里插入图片描述



(稳定)1.2 折半插入排序【先?折半查找找到应该插?的位置,再移动元素】

过程:

在这里插入图片描述

//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{ 
    int i,j,low,high,mid;
    for(i=2; i<=n; i++)
    {
        A[0]=A[i]; //存到A[0]
        //-----------------折半查找【代码一样】---------------------------
        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];//插入
    }
}

时间、空间复杂度

空间复杂度:O(1)

【右移】的次数变少了,但是关键字对?的次数依然是O(n2) 数量级,整体来看时间复杂度依然是O(n2)


(不稳定)1.3 希尔排序【多次直接插入排序】

是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。

算法思想

  • 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;
  • 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

图解:

在这里插入图片描述

代码实现:

//从小到大
void shellSort(int* arr, int n)
{
        int gap, i, j, temp;
        //小组的个数,小组的个数从n/2个,变成n/4,再变变变,越来越少,直到变成一个
        for (gap = n / 2; gap >= 1; gap = gap / 2) 
        {
            //**********************************直接插入排序(只是步长改变)**************************************************
            for (i = gap; i < n; i++)  //因为这个小组的元素使隔了gap个,所以排的时候也要隔gap个
            {
                if (arr[i] < arr[i - gap])
                {
                    temp = arr[i];
                    
                    //后移
                    for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap) 
                        arr[j + gap] = arr[j];
                    
                    arr[j + gap] = temp;//插入进去
                }
            }
            //************************************************************************************
        }
}

时间、空间复杂度

空间复杂度:O(1)

时间复杂度:和步长的大小有关,?前?法?数学?段证明确切的时间复杂度 ,最坏时间复杂度为 O(n2),当n在某个范围内时,可达O(n1.3)

稳定性:不稳定!

在这里插入图片描述

适?性:仅适?于顺序表,不适?于链表



2. 交换排序

2.1 (稳定)冒泡排序

英文:bubble sort ????(bubble 动和名词 起泡,冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置

每一轮比较会让一个最大数字沉底或者一个最小数字上浮

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。

实现代码:

//从小到大:
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
	int temp;
	for (int i = 0; i < len - 1; ++i)//循环比较次数
	{
		//for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
		for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化 
		{
			if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
			{
				//交换两个元素位置
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

优化代码【当初始序列有序时,外层for会执行“【1】”,从而外层for只执行了一次】:

//从小到大:
void bubble_sort(int arr[], int len)
{
	int temp;
	bool flag;
	for (int i = 0; i < len - 1; ++i)
	{
	    //表示本趟冒泡是否发生交换的标志
		flag=false;
		
		for (int j = 0; j < len - 1 - i; ++j)
		{
			if (arr[j] > arr[j + 1])//稳定的原因
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
				//有发生交换
				flag=true;
			}
		}//for
		
		//本趟遍历后没有发生交换,说明表已经有序
		if(flag==false)return;1}//for
}

时间、空间复杂度

在这里插入图片描述
适用性:冒泡排序可以用于顺序表、链表
在这里插入图片描述



2.2 (不稳定)快速排序【所有内部排序算法中,平均性能最优的排序算法】

算法思想:
在待排序表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)上,这个过程称为?次“划分”。

然后分别递归地对两个?表重复上述过程,直?每部分内只有?个元素或空为?,即所有元素放在了其最终位置上。

划分的过程:

初始状态:取首元素为pivot,定义low,high指针
在这里插入图片描述
首元素为49
high指针指向的数据小于49,就放在low指向的位置
low指针指向的数据大于49,就放在high指向的位置

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

// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
	//取首元素为pivot
    int pivot = A[low];
    
    while(low<high)
    {
    	//先是high开始向左移动
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];
        
        //随后low向右移动
        while(low<high && A[low]<=pivot) 
            ++low;
        A[high] = A[low];
    }
    
    //low=high的位置,即pivot放在的位置
    A[low] = pivot;
    
    return low;
} 

// 对A[]数组的low到high进行快速排序
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);
    }
}

时间、空间复杂度

在这里插入图片描述

把n个元素组织成?叉树,?叉树的层数就是递归调?的层数

n个结点的?叉树: 最??度 = ?log2n? + 1,最??度 = n

时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n),是所有内部排序算法中平均性能最优的排序算法

空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)

最坏的情况

在这里插入图片描述

?较好的情况

在这里插入图片描述

不稳定的原因:

在这里插入图片描述



3.选择排序

选择排序:每?趟在待排序元素中,选取关键字最?(或最?)的元素加?有序?序列

3.1 (不稳定)简单选择排序

算法思路:每一趟在待排序元素中,选取关键字最小的元素待排序元素中的第一个元素交换位置

在这里插入图片描述

// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
	//一共进行n-1趟,i指向待排序序列中第一个元素
    for(int i=0; i<n-1; i++)
    {          	
        int min = i;
        for(int j=i+1; j<n; j++){		//在A[i...n-1]中选择最小的元素
            if(A[j]<A[min])
                min = j;
        }
        if(min!=i)                     
            swap(A[i], A[min]);
    }
}

补充:对链表进行简单选择排序

void selectSort(LinkList &L){
    LNode *h=L,*p,*q,*r,*s;
    L=NULL;
    while(h!=NULL){
        p=s=h; q=r=NULL;
        while(p!=NULL){
            if(p->data>s->data){
                s=p; r=q;
            }
            q=p; p=p->next;
        }
        if(s==h)
            h=h->next;
        else
            r->next=s->next;
        s->next=L; L=s;
    }
}

时间、空间复杂度

在这里插入图片描述

在这里插入图片描述

适用性:适用于顺序存储和链式存储的线性表。



3.2 (不稳定)堆排序

① 什么是堆、?根堆(?顶堆)、?根堆(?顶堆)?

堆是具有以下性质的完全二叉树
每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆
或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

在这里插入图片描述
在这里插入图片描述
即:
若满?: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)—— ?根堆(?顶堆)

② 建??根堆:BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)

思路:
所有?终端结点都检查?遍,看是否满??根堆的要求,如果不满?,则进?调整

在顺序存储的完全?叉树中,?终端结点编号 i≤?n/2?,也就是检查 i=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];
    for(int i=2*k; i<=len; i*=2){	//沿k较大的子结点向下调整
        if(i<len && A[i]<A[i+1])	
            i++;
        if(A[0] >= A[i])
            break;
        else{
            A[k] = A[i];			//将A[i]调整至双亲结点上
            k=i;					//修改k值,以便继续向下筛选
        }
    }
    A[k] = A[0]
}

③基于?根堆进?排序:HeapSort(int A[], int len)

选择排序:每?趟在待排序元素中,选取关键字最?(或最?)的元素加?有序?序列

堆排序:每?趟将堆顶元素加?有序?序列即与待排序序列中的最后?个元素交换

过程:在这里插入图片描述

// 交换a和b的值
void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
	//初始建立大根堆
    BuildMaxHeap(A, len);         	
   
    //n-1趟的交换和建堆过程
    for(int i=len; i>1; i--)
    {      	
        swap(A[i], A[1]);
        HeadAdjust(A,1,i-1);
    }
}

时间、空间复杂度

建堆时间 O(n),之后进行 n-1 次向下调整操作,每次调整时间复杂度为 O(log2n);
时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)

空间复杂度 = O(1)

结论:堆排序是不稳定的


④ 补充:在堆中插?新元素

对于?根堆,新元素放到表尾,并与?节点对?,若新元素??节点更?,则将?者互换
新元素就这样?路“上升”,直到?法继续上升为?

在这里插入图片描述

⑤ 补充:在堆中删除元素

被删除的元素?堆底元素替代,然后让该元素不断“下坠”,直到?法下坠为?

在这里插入图片描述



4. (稳定)归并排序

归并:把两个或多个已经有序的序列合并成?个

① 明白什么是“2路”归并?——就是“?合?”

在这里插入图片描述
多路归并:
在这里插入图片描述

② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】

在这里插入图片描述
B[ i ] = B[ j ]时,优先用B[ i ],故算法稳定

③递归进行分治思想【MergeSort(int A[], int low, int high)】

在这里插入图片描述

④ 总实现代码

// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));

// 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];
    for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
        if(B[i]<=B[j])
            A[k]=B[i++];
        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);     //归并
    }
}

时间、空间复杂度

在这里插入图片描述



5. 基数排序

直接看课本的过程图来理解P352

再看这个例子:
在这里插入图片描述

  1. 算法思想:把整个关键字拆分为d位,按照各个关键字位递增的次序(比如:个、十、百),做d趟“分配”和“收集”,若当前处理关键字位可能取得r个值,则需要建立r个队列。
  2. 分配:顺序扫描各个元素,根据当前处理的关键字位,将元素插入相应的队列。一趟分配耗时 O(n) 。
  3. 收集:把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。
  4. 基数排序擅长处理的问题
    ①数据元素的关键字可以方便地拆分为d组,且d较小。
    ②每组关键字的取值范围不大,即r较小。
    ③ 数据元素个数n较大。
  5. 算法效率分析
    • 时间复杂度:一共进行d趟分配收集,一趟分配需要 O(n) ,一趟收集需要O( r ) ,时间复杂度O[d(n+r)] ,且与序列的初始状态无关.
    • 空间复杂度: O( r ) ,其中r为辅助队列数量。
    • 稳定性:稳定。



内部排序算法总结

在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-09-04 01:36:44  更:2022-09-04 01:38:52 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 17:58:23-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计