排序算法复习
程序员文章站
2022-04-15 20:42:08
...
基本三种排序算法是：交换排序（包括冒泡排序和快速排序）、插入排序（包括直接插入排序、对分插入排序和希尔排序）、选择排序（包括直接选择排序和堆排序），再加上归并排序和基数排序（又称桶排序），一共是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;
}运行结果：
排序算法复习到此结束，这也是发表的第一篇博客，希望作为一个开始，见证自己的进步。