【数据结构入门】排序算法之交换排序与归并排序

2024-09-08 12:12

本文主要是介绍【数据结构入门】排序算法之交换排序与归并排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

        在前一篇博客,我们学习了排序算法中的插入排序和选择排序,接下来我们将继续探索交换排序与归并排序,这两个排序都是重头戏,让我们接着往下看。

 一、交换排序

1.1 冒泡排序

冒泡排序是一种简单的排序算法。

1.1.1 基本思想

它的基本思想是通过相邻元素的比较和交换,让较大的元素逐渐向右移动,从而将最大的元素移动到最右边。

动画演示:

1.1.2 具体步骤

  1. 从列表的第一个元素开始,重复进行以下步骤,直到最后一个元素:
    • 遍历列表中的每一个相邻的元素。
    • 如果相邻元素的顺序错误(较大的元素在前),则交换它们的位置。
  2. 重复上述步骤,直到列表中的所有元素都按照从小到大的顺序排列。

1.1.3 算法特性

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2) ,其中n是列表的长度。因为算法需要对列表中的每个元素进行多次比较和交换操作。
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

1.1.4 算法实现

void BubbleSort(int* a, int n)
{int isorder = 1;for (int i = 0; i < n; i++){for (int j = 1; j < n-i; j++){if (a[j-1] > a[j]){Swap(&a[j - 1], &a[j]);isorder = 0;}}if (isorder == 1){break;}}
}

1.2 快速排序

快速排序是一种常用的排序算法。

1.2.1 基本思想

任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

注意:

由于选取基准值是任意的,所以会有多种实现方式,每种方式最后的结果也不尽相同。

一般实现的大思路主要有三种:

1.hoare版本(左右指针法)

 注意事项:     

左边做key,右边先走;右边做key,左边先走。这样能够保证两个指针相遇时,以左边为key,相遇位置比key小正好可以交换;以右边为key时,相遇的位置比key大,正好可以交换。

原理如下:

以左边为例:

1.R找小,L找大没有找到,L遇到R

2.R找小,没有找到,直接遇到L,要么就是一个比key小的位置或者直接到keyi

类似的,右边做key,左边先走,相遇的位置就比key要大。

2.挖坑版本


 

3.前后指针版本

实现思路:

1.cur找到比key小的值,++prev curprev位置的值交换,++cur;

2.cur找到比key大的值,++cur;

方法:

1.a[cur] < key , 交换left 和 cur 数据, left++, cur++;

2.a[cur] == key, cur++;

3.a[cur] > key, 交换cur 和 right数据, right++;

4.cur > right 结束

核心思想:

1.与key相等的值,往后推

2.比key小的值,往前甩

3.比key大的值,往后甩

4.与key相等的就在中间

1.2.2 具体步骤

  1. 选择列表中的一个元素作为基准值(pivot),一般选择列表的第一个元素。
  2. 遍历列表,将比基准值小的元素放到基准值的左边,将比基准值大的元素放到基准值的右边。
  3. 将基准值放到它最终的位置上,即左边的元素都比它小,右边的元素都比它大。
  4. 对基准值左边和右边的子列表,分别进行递归快速排序。

1.2.3 算法特性

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

  2. 时间复杂度:O(N*logN)(经过优化后),在最坏情况下,快速排序的时间复杂度为O(n^2),但是通过一些优化技巧,可以将其降低到O(nlogn)。快速排序是一种原地排序算法,即不需要额外的空间来存储排序结果。

  3. 空间复杂度:O(logN)

  4. 稳定性:不稳定

1.2.4 算法实现

在算法整体实现之前我们需要考虑一下快速排序算法的特殊性:

这个算法利用了分治的思想,理想的状态下,从中间分开,时间复杂度大大降低,如果每次选key都正好选到中间值,那么完全可以达到\log (n)

但是要是key选的不好,假如说选到最小值或最大值,那么这个排序的效率就会大打折扣,不如直接使用插入排序。

所以,不能简单的直接取左边的数或者右边的数,这样很容易造成key的选择不好,降低效率。

好用的方法有两个:

        1. 随机选key

                这种方式使用随机在数中选key的方式,来选择key,降低了选到最大或者最小值的概率。

srand((unsigned int)time(NULL));void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}int randi = left + (rand() % (right - left));
swap(&a[left], &a[randi]);

        2.三数取中法

        这种方法使用的较为普遍,通过选择三个数中中间的一个数来定key,在数据没有大量重复的情况下,对提高算法效率有很大帮助。

这里其实留下了一个坑,当数据大量重复时,快速排序的效率会降到Nlog(N),如何解决这个问题,可以等等下一篇博客,会介绍三路划分优化快速排序算法。

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中,有序情况下最快
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else //a[mid] <= a[left]{if (a[right] < a[mid]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);

 1)hoare版本(左右指针法)

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中,有序情况下最快
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else //a[mid] <= a[left]{if (a[right] < a[mid]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}
//hoare版本
int PartSort1(int* a, int left, int right)
{//优化:三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;//这地方left 不能先+1,否则最后一步交换会出问题while (left < right){//右边先找小//注意内部没有判断left< rightwhile (left < right && a[right] >= a[keyi]){right--;}//左边找大while (left < right && a[left] <= a[keyi]){left++;}Swap(&a[left], &a[right]);}//相遇位置一定比key小Swap(&a[keyi], &a[left]);keyi = left;return keyi;
}

2)挖坑版本

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//三数取中,有序情况下最快
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else //a[mid] <= a[left]{if (a[right] < a[mid]){return mid;}else if (a[right] > a[left]){return left;}else{return right;}}
}
//挖坑版
int PartSort2(int* a, int left, int right)
{//优化:三数取中int midi = GetMidNumi(a, left, right);Swap(&a[left], &a[midi]);int key = a[left];int pit = left;//这地方left 不能先+1,否则最后一步交换会出问题while (left < right){//右边先找小//注意内部没有判断left< rightwhile (left < right && a[right] >= key){right--;}a[pit] = a[right];pit = right;//左边找大while (left < right && a[left] <= key){left++;}a[pit] = a[left];pit = left;}//相遇位置一定比key小a[pit] = key;return pit;
}

3)前后指针版本

//前后指针法
int PartSort3(int* a, int left, int right)
{int midi = GetMidNumi(a, left, right);if (midi != left){Swap(&a[left], &a[midi]);}int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}//这里prev直接换就好了,不用交换Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}

4)快速排序调用程序 

void QuickSort(int* a, int left, int right)
{//递归结束条件if (left >= right){return;}//小区间优化 -- 小区间使用插入排序//这个数字不能太大,否则没有意义if ((right - left + 1) > 10){int keyi = PartSort3(a, left, right);//只需改变1,2,3就可以改用三个快速排序版本//[begin, keyi-1] keyi [keyi+1, end]QuickSort(a, left, keyi - 1);QuickSort(a, keyi+1, right);}else{InsertSort(a + left, right - left +1);}
}

 优化:

在区间长度小于10时,改用插入排序,然后再递归,增加了算法效率。但是一定要注意区间长度一定要设置的恰到好处,否则区间过长就起不到相应的作用了。

1.2.5 非递归实现(重点)

非递归的实现一般有两种方式:   

  1. 1.直接改,适用于简单的递归,比如斐波那契数;
  2. 2.使用栈辅助改为非递归,适用于复杂的结构,利用栈先进先出的特点,对数据进行排序。
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);//入栈,先入后出,所以先入右边的值STPush(&st, right);STPush(&st, left);//栈非空时,进行操作while (!STEmpty(&st)){//出栈int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);if (end > keyi + 1){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}

二、归并排序

归并排序是一种分治算法,它将列表递归地拆分成两个子列表,然后将这两个子列表合并成一个有序的列表。

2.1 基本思想

它的基本思想是将待排序列表分解成若干个子列表,然后将这些子列表逐个合并,最终得到一个有序的列表。

动画演示:

2.2 具体步骤

  1. 将列表不断地二分,直到每个子列表只包含一个元素。
  2. 将两个有序的子列表合并成一个有序的列表。合并时,比较两个子列表的第一个元素,将较小的元素放到结果列表中,并将指针向后移动一位,依此类推,直到其中一个子列表为空。然后将另一个非空子列表的剩余部分直接放到结果列表中。
  3. 重复步骤2,直到所有的子列表都合并为一个有序的列表。

2.3 算法特性

1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度:O(N*logN),其中n是列表的长度。
3. 空间复杂度:归并排序是一种稳定的排序算法,它需要额外的空间来存储临时的结果,所以空间复杂度为O(n)。
4. 稳定性:稳定

2.4 算法实现

//归并排序,O(NlogN)
void _MergeSort(int* a, int begin, int end, int* tmp)
{//递归结束条件if (begin >= end){return;}int mid = (begin + end) / 2;//mid控制递归_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid + 1, end, tmp);//[begin, mid] [mid+1, end]归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;//i为每个栈帧中的独立变量,控制每一次的归并int i = begin;while (begin1 <= end1 && begin2 <= end2){//begin1<=begin2,可以做到稳定if (a[begin1] <= a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}//没排到的直接接到后面while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}//覆盖到原数组memcpy(a+begin, tmp+begin, sizeof(int)*(end-begin+1));
}void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

 归并在实现时使用了递归所以一定要注意栈帧的开辟,防止爆栈。

事实上,归并的递归写法并不难,但是在大量数据归并时对栈帧的开销很大,很容易造成栈溢出,所以作为一名合格的程序员,一定要学会将递归改为非递归。

修正思路:

归并排序改非递归:数据多不好调试,可以打印出来看边界

复杂问题分解为简单问题:分类处理

        1.end1越界?不归并了

        2.end1没有越界,begin2越界了?跟1一样处理

        3.end1、begin没有越界,end2越界了? 继续归并,修正

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");return;}int gap = 1;//gap是归并过程中,每组数据的个数while (gap < n){for (int i = 0; i < n; i += 2*gap){			//归并一次,拷贝一次(推荐)if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}//归并int j = i;while (begin1 <= end1 && begin2 <= end2){//begin1<=begin2时可以做到稳定if (a[begin1] <= a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}//没排到的直接接到后面while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//数据覆盖到原数组memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;//gap控制遍历}free(tmp);tmp = NULL;
}

三、算法复杂度及稳定性分析

 

 总结

  • 冒泡排序是简单的排序算法,通过交换相邻元素使得较大(小)的元素逐渐向右(左)移动,时间复杂度为O(n^2)。
  • 快速排序是高效的排序算法,采用分治思想,通过选择基准元素将数组分割成左右子数组,进一步递归排序,平均时间复杂度为O(nlogn)。
  • 归并排序也是高效的排序算法,采用分治思想,将数组分割成左右子数组,递归排序后再合并,时间复杂度为O(nlogn)。

快速排序和归并排序相比,快速排序更常用,但快速排序在最坏情况下可能达到O(n^2)的时间复杂度。在实际应用中,需要根据具体情况选择合适的排序算法。

这篇关于【数据结构入门】排序算法之交换排序与归并排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1148082

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时