本文主要是介绍算法—排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
排序
1 插入排序
2 冒泡排序
3 Shells 排序
4 归并排序
5 快速排序
1 插入排序
1.1 思路
数组A(0,..,n-1)
1.从0 - n-1 循环分别到达自己对应的位置。
2.外循环i=0 到 n-1
3.内循环 j=i 到 0
平均时间复杂度:O(N^2)
最坏时间复杂度:O(N^2)
最优时间复杂度:O(N)
1.2 代码
pseudocode
//从小到大排序
void insertion(vector<int>& arr)
{
for each j to arr.size()
int tmp=arr[j]
for each i=j to 0 and arr[i]<arr[i-1]
swap(arr[i],arr[j]) //若arr[i]小于arr[i-1] 交换
arr[i]=tmp
}
2 冒泡排序
2.1 思路
//基于交换的排序思路
1.外循环 i=0 到 n-1
2.内循环 j=0 到 n-i-1
3.将比较大的元素沉底
平均时间复杂度:O(N^2)
最坏时间复杂度:O(N^2)
最优时间复杂度:O(N)
2.2 伪代码
pseudocode
void bubble(vector<int> & arr)
{
for i=0 to arr.size()
for j=0 to arr.size()-1-i
if(arr[j]>arr[j+1])
swap(arr[j],arr[j+1])
}
3 Shells 排序
3.1 思路
//跳跃式分组策略
平均时间复杂度:O(N^1.3)
最坏时间复杂度:O(N^2)
最优时间复杂度:O(N)
3.2 代码
pseudocode
void shell(vector<int> & arr)
{
//比较增量gap,并逐步减小增量
for gap = arr.size()/2 to 0 by gap/=2
for i =gap to arr.size() by i+=1
j =i
while(j-gap>0 且 arr[j]<arr[j-gap]) //往前循环
swap(arr[j],arr[j-gap])
j-=gap;
}
4 归并排序
4.1 思路
1.分而治之的思想
2.arr[0,n-1] 分为两部分 如此 递归划分 直至只有单个元素
3.将划分的两部分 合并
平均时间复杂度:O(NlogN)
最坏时间复杂度:O(NlogN)
最优时间复杂度:O(NlogN)
4.2 代码
pseudocode
//合并函数
void merge(vector<int>&arr,vector<int>& tmp,int left ,int mid,int right)
{
int i = left,j=mid;
int k = left;//temp数组初始位置
//对两个部分进行排序
while(i<=mid && j <=right)
{
if(arr[i]<arr[j])
tmp[k++]=arr[i++]
else if(arr[i]>=arr[j])
tmp[k++]=arr[j++]
}
while(i<=mid )
{
tmp[k++]=arr[i++]
}
while(j<=right )
{
tmp[k++]=arr[j++]
}
int numSize = right-left+1;
//更新arr
for(int z = 0;z<numSize;z++,right--)
{
arr[right]=tmp[right];
}
}
//归并排序
void mergeSort(vector<int>&arr,vector<int>& tmp,int left ,int right)
{
//如果只有两个元素不划分,直接返回
if(left<right)
{
int mid = left+(right-left)/2;
//继续划分左右两个部分
mergeSort(arr,tmp,left,mid);
mergeSort(arr,tmp,mid+1,right);
//合并
merge(arr,tmp,mid,left,right);
}
}
5 快速排序
思路
代码
这篇关于算法—排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!