本文主要是介绍算法—排序，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

排序

• 1 插入排序
• • 1.1 思路
  • 1.2 代码
• 2 冒泡排序
• • 2.1 思路
  • 2.2 伪代码
• 3 Shells 排序
• • 3.1 思路
  • 3.2 代码
• 4 归并排序
• • 4.1 思路
  • 4.2 代码
• 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 快速排序

思路

代码

这篇关于算法—排序的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！