排序算法复习

标签: 快速排  希尔排  堆排  归并排  基数排

基本三种排序算法是:交换排序(包括冒泡排序和快速排序)、插入排序(包括直接插入排序、对分插入排序和希尔排序)、选择排序(包括直接选择排序和堆排序),再加上归并排序和基数排序(又称桶排序),一共是9种排序算法。

这里重新复习九种排序算法,冒泡排序和直接选择排序比较基础,不予实现。

快速排序

与冒泡排序同属于交换排序 ,时间复杂度(O(nlog2n))低于冒泡排序,栈最大深度O(n),属于不稳定排序。
#include<iostream>
using namespace std;
template<class T>
int quick_sort(T a[],int m,int n){
	int i=m,j=n;
	T temp=a[m];
	while(i!=j){
		while(a[j]>=temp&&j>i)j--;
		a[i]=a[j];
		while(a[i]<=temp&&j>i)i++;
		a[j]=a[i];
	}
	a[j]=temp;
	return j;
}
template<class T>
void quick_sort_loop(T a[],int m,int n){
	int i;
	if(n>m){
		i=quick_sort(a,m,n);
		if(i>m)quick_sort_loop(a,m,i-1);
		if(i<n)quick_sort_loop(a,i+1,n);
	}
}
int main(){
	int a[]={46,55,13,42,94,5,17,70,1,45},j;
	char b[]="jlhaisdaap";
	double c[]={12.12312,0.12,2.366,5.166,8.5659415,23.65656,56.13131,2.131313,0.13131,56.13};
	_int64 d[]={456465464566878,4564132132146,45678978413132,12354645313,456689798798764,56568784655,3546546468876,1213545646564564,789784654645646,2345645645465};
	quick_sort_loop(a,0,9);
	quick_sort_loop(b,0,9);
	quick_sort_loop(c,0,9);
	quick_sort_loop(d,0,9);
	cout<<"序号:"<<'\t'<<"数组a:"<<'\t'<<"数组b:"<<'\t'<<"数组c:"<<'\t'<<"数组d:"<<endl;
	for(j=0;j<10;j++){
		cout<<j+1<<'\t'<<a[j]<<'\t'<<b[j]<<'\t'<<c[j]<<'\t';
		printf("%I64d\n",d[j]);
	}
	return 0;
}

运行结果:

插入排序

直接插入排序、对半插入排序与希尔排序,运行结果与上同。这里希尔排序选择的增量是长度的1/2,并依次减半,直至为1.希尔时间复杂度介于O(n)和O(n^2)之间,属于不稳定排序。

template<class T>
void insert_sort(T a[],int n){
	int i,j;
	T temp;
	for(i=1;i<n;i++){
		temp=a[i];
		for(j=i-1;temp<a[j]&&j>=0;j--){
			a[j+1]=a[j];
		}
		a[j+1]=temp;
	}
}
template<class T>
void half_insert_sort(T a[],int n){
 int low,high,mid,i,j;
 T temp;
 for(i=1;i<n;i++){
  low=0;
  high=i-1;
  temp=a[i];
  if(temp>a[i-1])continue;
  while(low<high){
   mid=(low+high)/2;
   if(temp<a[mid]){
    high=mid;
   }else{
    low=mid+1;
   }
  }
  for(j=i-1;j>=low;j--){
   a[j+1]=a[j];
  }
  a[low]=temp;
 }
}
template<class T>
void shell_sort(T a[],int n){
	int h=n/2,i,j;
	T temp;
	for(;h>=1;h/=2){
		for(i=h;i<n;i++){
			temp=a[i];
			for(j=i-h;temp<a[j]&&j>=0;j-=h){
				a[j+h]=a[j];
			}
			a[j+h]=temp;
		}
	}
}

堆排序

时间复杂度优于选择排序,最坏情况O(nlogn),且堆排序只需运用一个辅助空间,也属于不稳定排序。这里值得一提的是,直接选择排序也属于不稳定算法。
template<class T>
void construct_heap(T a[],int n,int k){
 int i=k,j;
 T temp;
 temp=a[i];
 j=i*2+1;
 while(j<n){
  if(j<n-1&&a[j]<a[j+1])j++;
  if(temp<a[j]){
   a[i]=a[j];
   i=j;
   j=2*i+1;
  }else{
   break;
  }
 }
 a[i]=temp;
}
template<class T>
void heap_sort(T a[],int n){
 int k=n/2-1,i;
 T temp;
 for(i=k;i>=0;i--)
  construct_heap(a,n,i);
 for(i=n-1;i>0;i--){
  temp=a[i];
  a[i]=a[0];
  a[0]=temp;
  construct_heap(a,i,0);
 }
}


归并排序

归并排序,基于分治思想,分的时间复杂度O(log2n),治的时间复杂度O(n),总的时间复杂度O(nlog2n),稳定排序。

template<class T>
void mergeArray(T a[],T temp[],int first,int mid,int last){
	int left1=first,right1=mid,left2=mid+1,right2=last,i,j=0;
	while(left1<=right1&&left2<=right2){
		if(a[left2]<a[left1]){
			temp[j++]=a[left2++];
		}else{
			temp[j++]=a[left1++];
		}
	}
	while(left1<=right1)temp[j++]=a[left1++];
	while(left2<=right2)temp[j++]=a[left2++];
	for(i=0;i<j;i++){
		a[first+i]=temp[i];
	}
}
template<class T>
void msort(T a[],T temp[],int m,int n){
	int mid=(m+n)/2;
	if(n>m){
		msort(a,temp,m,mid);
		msort(a,temp,mid+1,n);
		mergeArray(a,temp,m,mid,n);
	}
}
template<class T>
void merge_sort(T a[],int n){
	T *p=new T[n];
	msort(a,p,0,n-1);
	delete[] p;
}

基数排序

基数排序基于多关键字,这里只给出int型数据。

void int_radix_sort(int a[],int n){
	int i,j,k,l,flag;
	int *temp[10],count[10]={0};
	for(i=0;i<10;i++){
		temp[i]=new int[n];
		memset(temp[i],0,sizeof(int)*n);
	}
	for(i=0;;i++){
		memset(count,0,sizeof(int)*10);
		for(j=0;j<n;j++){
                        //falg用来判断数字是否达到最高位,达到时跳出for循环
			flag=0;
			int number=a[j]/pow(10,i);
			number=number%10;
			if(number)flag=1;
			temp[number][count[number]]=a[j];
			count[number]++;
		}
		if(!flag)break;
		k=0;
		for(j=0;j<10;j++){
			for(l=0;l<count[j];l++){
				a[k++]=temp[j][l];
			}
		}
	}
}

下面给出了一个队string和int型数组的排序完整程序:

#include<iostream>
#include<cmath>
#include<string>
using namespace std;
void int_radix_sort(int a[],int n){
	int i,j,k,l,flag;
	int *temp[10],count[10]={0};
	for(i=0;i<10;i++){
		temp[i]=new int[n];
		memset(temp[i],0,sizeof(int)*n);
	}
	for(i=0;;i++){
		memset(count,0,sizeof(int)*10);
		for(j=0;j<n;j++){
			flag=0;
			int number=a[j]/pow(10,i);
			number=number%10;
			if(number)flag=1;
			temp[number][count[number]]=a[j];
			count[number]++;
		}
		if(!flag)break;
		k=0;
		for(j=0;j<10;j++){
			for(l=0;l<count[j];l++){
				a[k++]=temp[j][l];
			}
		}
	}
}
int string_lenth(string a[],int n){
	int len=0,i;
	for(i=0;i<n;i++){
		len=a[i].size()>len?a[i].size():len;
	}
	return len;
}
void string_radix_sort(string a[],int n){
	int i,j,k,l,len;
	len=string_lenth(a,n);
	string *temp[27];
	int count[27]={0};
	for(i=0;i<27;i++){
		temp[i]=new string[n];
		memset(temp[i],'\0',sizeof(string)*n);
	}
	for(i=len-1;i>=0;i--){
		memset(count,0,sizeof(int)*27);
		for(j=0;j<n;j++){
			char c=a[j][i];
			if(c=='\0'){
				c='a'-1;
			}
			temp[c-'a'+1][count[c-'a'+1]]=a[j];
			count[c-'a'+1]++;
		}
		k=0;
		for(j=0;j<27;j++){
			for(l=0;l<count[j];l++){
				a[k++]=temp[j][l];
			}
		}
	}
}
int main(){
	int a[]={46,55,13,42,94,5,17,70,1,45},j;
	string s[]={"sdqwdasd","asdqwsadasd","opdfkopsdfal","bsdlfiasl","asdksa","lpoppsdfj","oprjtyryr","mlfopdfog","opdsofs","asdsaldk"};
	string_radix_sort(s,10);
	int_radix_sort(a,10);
	cout<<"序号:"<<'\t'<<"数组a:"<<'\t'<<"数组s:"<<endl;
	for(j=0;j<10;j++){
		cout<<j+1<<'\t'<<a[j]<<'\t'<<s[j]<<endl;
	}
	return 0;
}

运行结果:



排序算法复习到此结束,这也是发表的第一篇博客,希望作为一个开始,见证自己的进步。

版权声明:本文为sinat_41738615原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/sinat_41738615/article/details/80672415

智能推荐

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

猜你喜欢

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...

力扣困难难度 第4题 寻找两个正序数组的中位数

先看一眼题 我的思路: 设置下标i,j分别用于遍历两个数组,初始值均为0,直到找到两个数组中从小到大的第第length/2个数为止结束循环,length为两个数组长度之和。 ·每次比较nums[i]nums[j],如果前者小则i++,否则j++ ·循环结束时,如果count已经达到length/2,则说明已经找到了中位数,[注意:此时有可能正好其中一个数组遍历完了!所以...

[国家集训队]小Z的袜子(莫队)

[国家集训队]小Z的袜子 题目描述 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这NN只袜子从1到NN编号,然后从编号LL到RR(LL 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同...