常用排序算法
创始人
2024-05-31 14:07:19
0

一、冒泡排序

原理: 第一遍从0-n-1遍历,比较相邻元素,最后一个位置确定;第二遍从0-n-2遍历,比较相邻元素,倒数第二个位置被确定;一直遍历直到每个位置都被确定。

数据是反序时,耗费时间最长O(n²);
数据是正序时,耗费时间最短O(n)

是一种稳定的排序算法。
在这里插入图片描述

/* 力扣代码 */
class Solution{
public:vector sortArray(vector& nums) {int len = (int)nums.size();for(int i=0;i<=len-1;i++){for(int j=0;jif(nums[j] > nums[j+1]){swap(nums[j],nums[j+1]);}}}return nums;}
};

二、选择排序

原理: 遍历所有的数据,先在数据中找出最大或最小的元素,放到序列的起始,再从余下的数据中继续寻找最大或最小的元素,依次放到序列中,直到所有有序。

平均时间复杂度为O(n²)

是一种不稳定的排序算法。
在这里插入图片描述

/* 力扣代码 */
class Solution{
public:vector sortArray(vector& nums){int len = nums.size();for(int i=1;iint k = i-1;for(int j=i;jif(nums[j] < nums[k]){k = j;}}if(k != i-1){swap(nums[k],nums[i-1]);}}return nums;}
};

三、快速排序

原理: 从数组中选择一个元素作为中轴元素,一般可选第一个,把数组中小于中轴的元素放在其左边,大于中轴的元素放在其右边,之后再递归快速排序中轴左右两边的序列直到完成。

最理想的情况是,整个算法的时间复杂度为O(n logn)
最坏的情况是,整个排序算法的时间复杂度为O(n²)

是一种不稳定的排序算法。
在这里插入图片描述

/* 力扣代码 */
class Solution{
public: int quickSort(vector& arr,int left,int right){if(left >= right){return 0;}int middle = arr[left];int begin=left,end=right;int start = left;while(begin < end){while(begin < end && arr[end] >= middle){end--;}while(begin < end && arr[begin] <= middle){begin++;}if(begin != end){swap(arr[begin],arr[end]);}}swap(arr[start],arr[begin]);quickSort(arr,left,begin-1);quickSort(arr,begin+1,right);return 0;}vector sortArray(vector& nums) {srand((unsigned)time(NULL));quickSort(nums,0,(int)nums.size() - 1);return nums;}
};

四、堆排序

原理: 将数组当成二叉树构建,且必须满足每一个节点的值都必须大于或等于左右子节点的值。之后将根节点与最后的一个节点交换位置,再对除了最后一个节点外重新排序;一直重复这个步骤,直到排完。

平均时间复杂度为O(n logn),是一种不稳定的排序算法。
在这里插入图片描述

/* 力扣代码 */
class Solution{        
public:void max_heap(vector& arr,int start,int end){int dad = start;int son = dad*2 + 1;while(son <= end){if(son+1 <= end && arr[son] < arr[son+1]){son++;} if(arr[dad] > arr[son]){return;}if(son <= end && arr[son] > arr[dad]){swap(arr[son],arr[dad]);dad = son;son = dad*2+1;}}}void heap_sort(vector&arr,int len){for(int i=len/2-1;i>=0;i--){max_heap(arr,i,len-1);}for(int i=len-1;i>0;i--){swap(arr[0],arr[i]);max_heap(arr,0,i-1);}}vector sortArray(vector& arr){int len = (int)arr.size();heap_sort(arr,len);return arr;}
};

五、插入排序

原理: 假定前i个数据是有序的(起始一般是第一个),接着往后遍历数据,每一个数据都要找到前有序序列中的一个合适位置插入。

数据是反序时,耗费时间最长O(n²);数据是正序时,耗费时间最短O(n)

是一种稳定的排序算法
在这里插入图片描述

/* 力扣代码 */
class Solution{
public:vector sortArray(vector& arr){int len = arr.size();int i=0;for(int p=1;pi = p - 1;int temp = arr[p];while(i>=0 && arr[i] > temp){arr[i+1] = arr[i];i--;               }    arr[i+1] = temp;    }return arr;    }                
};

六、希尔排序

原理: 一般可使用3个增量进行排序,分别是5、3、1,也就是在一组数据里面以5为间隔大小,分别划分出不同的序列分别进行插入排序,再以3为间隔大小,分别划分出不同的序列进行插入排序,最后1就是一次全序列进行插入排序

复杂度下界为O(n log²n),在中等规模的数据中表现良好。

平均时间复杂度为O(n^3/2),是一种不稳定的排序算法
在这里插入图片描述

/* 力扣代码 */
class Solution{
public:      void sortShell(vector&arr,int len){int i,j,key;for(int inc=len/2;inc>0;inc/=2){for(i=inc;ikey = arr[i];for(j=i;j>=inc && key < arr[j-inc];j-=inc){arr[j] = arr[j-inc];}arr[j] = key;}}}vectorsortArray(vector&arr){int len = arr.size();sortShell(arr,len);return arr;}
};

七、归并排序

原理: 原理如图所示,先将一个序列一直对半划分,直到不能再划分,当划分完毕就进行合并,合并的时候分别比较左右分区的第一个元素,把较小的那个放到临时数组,一直这样合并直到合并完毕。

最好情况下可将时间复杂度降至O(n)

平均时间复杂度为O(n logn)
在这里插入图片描述

/* 力扣代码 */
class Solution{
public:vectortmp;/* 划分数组 */void msort(vector&nums,int left,int right){if(left < right){int mid = (left+right)/2;//划分左边区域msort(nums,left,mid);//划分右边区域msort(nums,mid+1,right);//合并int i = left,j = mid+1;int cnt = 0;/* 合并数组/ */while(i<=mid && j<=right){if(nums[i] <= nums[j]){tmp[cnt++] = nums[i++];}else{tmp[cnt++] = nums[j++];}}/* 合并左分区剩余序列 */while(i <= mid){tmp[cnt++] = nums[i++];}/* 合并右分区剩余序列 */while(j <= right){tmp[cnt++] = nums[j++];}/* 将排好的数组再放到原数组 */for(int i=0;i<(right-left+1);i++){nums[i+left] = tmp[i];}}elsereturn;}vectorsortArray(vector&nums){int len = nums.size();tmp.resize((int)nums.size(), 0);msort(nums,0,len-1);return nums;}
};

相关内容

热门资讯

微软安卓系统叫什么,Windo... 你知道吗?在科技界,微软这个巨头最近可是搞了个大动作,竟然把目光投向了安卓系统!没错,就是那个我们日...
安卓系统没有最近任务,揭秘无最... 你是不是也遇到了这个问题?安卓系统里怎么就没有“最近任务”这个功能呢?别急,让我来给你详细说说这个事...
安卓系统怎么拒聊天,安卓系统聊... 你是不是也和我一样,有时候手机里聊天软件的消息太多,让人头都大了?别急,今天就来教你怎么在安卓系统里...
下载工资软件安卓系统,高效便捷... 你有没有想过,每个月的工资一到手,是不是就感觉整个人都轻松了呢?但是,你知道怎么轻松地管理你的工资吗...
下载灰灰影音安卓系统,畅享高清... 你有没有想过,一部手机,一部电脑,就能让你随时随地享受高清电影、热门剧集的乐趣?没错,这就是我们今天...
安卓系统是不是中国,中国智慧与... 你有没有想过,那个陪伴你每天刷手机、玩游戏、办公的安卓系统,它是不是中国的“孩子”呢?这个问题听起来...
电脑如果安装安卓系统,探索安卓... 你有没有想过,如果家里的电脑突然决定要换换口味,不再坚守Windows的阵营,而是拥抱安卓系统呢?想...
安卓手机升级苹果系统,体验全新... 你有没有想过,你的安卓手机突然间变成了苹果的忠实粉丝,想要体验一番iOS系统的魅力呢?这可不是天方夜...
安卓系统短信不通知,享受宁静 你是不是也遇到了这个问题?安卓系统短信不通知,是不是让你抓狂?别急,今天就来给你详细解析一下这个让人...
夏普电视非安卓系统,非安卓系统... 亲爱的读者们,你是否曾对夏普电视的非安卓系统感到好奇呢?今天,就让我带你一探究竟,揭开这个神秘面纱背...
安卓系统43适配软件,软件升级... 你有没有发现,你的安卓手机最近是不是有点儿“水土不服”?别急,别急,让我来给你揭秘为什么你的安卓系统...
安卓系统有车载系统吗吗,智能驾... 你有没有想过,当你坐在车里,享受着旅途的悠闲时光,手机上的安卓系统是不是也能派上用场呢?没错,我就要...
安卓8.1系统解锁方法,畅享自... 你有没有想过,你的安卓手机里隐藏着无数的小秘密?比如,解锁安卓8.1系统,就能让你的手机焕发出全新的...
安卓系统怎么打开邮件,安卓系统... 你有没有想过,每天那么多邮件,怎么才能快速打开它们呢?尤其是当你用的是安卓系统手机的时候。别急,今天...
封闭安卓系统安装软件,一步到位... 你有没有想过,为什么你的安卓手机里有些软件只能通过官方渠道安装呢?今天,就让我带你一探究竟,揭开封闭...
小米mipad升级安卓系统,解... 你有没有发现,最近小米Mipad的安卓系统升级可是个大热门呢!这不,我就迫不及待地来和你聊聊这个话题...
哪个安卓系统体验好,揭秘安卓系... 你有没有想过,手机里的安卓系统就像是个大厨,不同的版本就是不同的拿手好菜,有的让你回味无穷,有的却让...
安卓系统开发测试,全方位技术解... 你有没有想过,那个陪伴你每天刷手机、玩游戏、办公的安卓系统,是怎么从无到有,一步步成长起来的呢?今天...
安卓系统怎么查配置,轻松掌握设... 你有没有想过,你的安卓手机里藏着多少秘密?别小看这些配置信息,它们可是了解你手机性能的“小侦探”呢!...
pve下安装安卓系统,PVE环... 你有没有想过,在你的PVE服务器上安装一个安卓系统呢?听起来是不是有点酷炫?想象你的服务器不仅能够运...