各种内排序算法源码汇总--c语言

63 阅读 0 评论 42 点赞

我是靠谱客的博主犹豫百褶裙，最近开发中收集的这篇文章主要介绍各种内排序算法源码汇总--c语言，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

#include<iostream>
#include<math.h>
#include<set>
#include<algorithm>
#include<iterator>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
using namespace std;
/*
单行输出数组
*/
void disp_array(int r[],int n)
{
int i;
for(i=0;i<n;i++)
{
cout<<r[i]<<" ";
}
cout<<endl;
}
/*
直接插入法排序
算法时间复杂度O(n^2)，空间复杂度O(1)
扫描每一个数都要将该数位置前的下标移位
*/
void SInsertSort(int R[],int n)
{
int i,j,tmp;
for(i=1;i<n;i++)
{
tmp=R[i];
j=i-1;
while(j>=0&&tmp<R[j])
{
R[j+1]=R[j];
j--;
}
R[j+1]=tmp;
}
}
/*
折半插入排序
折半插入排序所需附加储存空间和直接插入排序相同，从时间上
比较，折半插入排序仅减少比较次数，而纪录的移动次数不变，时间
复杂度为O(n^2)
*/
void BInsertSort(int R[],int n)
{
int i,j,low,high,m,tmp;
for(i=1;i<n;i++)
{
low=0;high=i-1;
while(low<=high)
{
m=(low+high)/2;
if(R[i]>R[m]) low=m+1;
else high=m-1;
}
tmp=R[i];
for(j=i-1;j>=high+1;j--) R[j+1]=R[j];
R[high+1]=tmp;
}
}
/*
希尔排序
希尔排序的平均时间复杂度为O(nlog2n)
空间复杂度为O(1),相同的数排序前后位置可能不同，因此希尔排序是不稳定的。
希尔排序的算法性能依赖于增量gap的选择，下述这种选择效率很低
*/
void ShellSort(int R[],int n)
{
int i,j,gap,tmp,k;
for(gap=n/2;gap>0;gap/=2)//步长
{
for(i=0;i<gap;i++)
//对于每一个子序列
{
for(j=i+gap;j<n;j+=gap) //进行直接插入排序
{
tmp=R[j];
k=j-gap;
while(k>=0&&tmp<R[k])
{
R[k+gap]=R[k];
k-=gap;
}
R[k+gap]=tmp;
}
}
}
}
/*
起泡排序
平均时间复杂度为O(n^2),空间复杂度O(1)
*/
void BubbleSort(int R[],int n)
{
int i,j,flag,temp;
for(i=n-1;i>=1;i--)
{
flag=0;
for(j=1;j<=i;j++)
{
if(R[j-1]>R[j])
{
temp=R[j];
R[j]=R[j-1];
R[j-1]=temp;
flag=1;
}
}
if(flag==0) return; //一趟排序过程中没有元素互换
}
}
/*
快速排序
最好时间复杂度O(nlog2n)最坏O(n^2)待排序列越无序算法效率越高，平均时间
复杂度O(nlog2n)就平均时间而言快速排序是所有排序中最好的，排序趟数和初始
序列有关。本算法的空间复杂度为O(log2n)
*/
void QuickSortD(int R[],int l,int r) //对从R[l]到R[r]的元素进行排序
{
int temp;
int i=l,j=r;
if(l<r)
{
temp=R[l];
while(i!=j)
{
while(j>i&&R[j]>temp) j--;
if(i<j)
{
R[i]=R[j];
i++;
}
while(i<j&&R[i]<temp) i++;
if(i<j)
{
R[j]=R[i];
j--;
}
}
R[i]=temp;
QuickSortD(R,l,i-1);
QuickSortD(R,i+1,r);
}
}
void QuickSort(int R[],int n)
//快速排序入口函数
{
QuickSortD(R,0,n-1);
}
/*
简单选择排序
时间复杂度O(n^2)
*/
void SelectSort(int R[],int n)
{
int i,j,k,temp;
for(i=0;i<n;i++)
{
k=i;
for(j=i+1;j<n;j++)
{
if(R[k]>R[j])
k=j;
}
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
}
/*
堆排序
堆排序时间复杂度为O(nlog2n),堆排序在最坏的情况下的时间复杂度
也是O(nlog2n)这是它相对于快速排序的最大优点，空间复杂度为O(1)在所有
时间为O(nlog2n)的排序中最小的，堆排序适合的场景是记录数很多的情况，典型
的例子是从10000个记录中选出前10个最小的，如果纪录数较少，则不提倡使用堆排序
*/
void HeapSwift(int R[],int low,int high)
//堆排序子函数，将下标low到下标high范围内对位置low上的节点进行调整
{
int i=low,j=2*i;
//R[j]是R[i]的左子节点
int temp=R[i];
//选中待调整节点
if(low==0) j=1; //如果待调节点是0号节点，则它的左子节点为1号节点
while(j<=high)
{
if(j<high&&R[j]<R[j+1]) j++;
//选取左右子节点中最大的,若只有一个则选那个
if(temp<R[j])
//如果最大的那个子节点比它大
{
R[i]=R[j];
//则将子节点向上移动到它的位置
i=j;
//移位所空出的那个地方继续向下调整
j=2*i;
}
else
break;
//待调节点最终位置为两子节点都比它小（大根堆）
}
R[i]=temp;
}
void HeapSort(int R[],int n) //堆排序主函数
{
int i,temp;
for(i=n/2-1;i>=0;i--)
//建立初始堆
{
HeapSwift(R,i,n-1);
}
for(i=n-1;i>=1;i--)
//进行n-1次循环完成排序
{
temp=R[0];
//选取当前最大的
R[0]=R[i];
//把当前最大的和当前处理量中最后一个
R[i]=temp;
HeapSwift(R,0,i-1); //继续选出0到i-1中的最大的
}
}
/*
二路归并排序
时间复杂度和初试序列无关，即平均情况下O(nlog2n),最好情况下为O(nlog2n),最坏情况下也一样
是一种非常稳定的排序算法。空间复杂度O(n)
*/
void Merge(int R[],int low,int mid,int high,int n)
//R[low...mid]和R[mid+1...high]各自有序，将他们合并成一个有序数组,n总大小
{
int i,j,k;
int *B=(int*)malloc((n)*sizeof(int));
//辅助数组，为提高效率最好用作全局量
for(k=low;k<=high;k++)
B[k]=R[k];
//复制到辅助数组
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++)
{
if(B[i]<=B[j])
R[k]=B[i++];
else R[k]=B[j++];
}
while(i<=mid) R[k++]=B[i++];
//若未检测完，复制
while(j<=high)
R[k++]=B[j++];
free(B);
}
void MergeSortD(int R[],int low,int high,int n)
//二路归并排序的递归函数
{
int mid;
if(low<high)
{
mid=(low+high)/2;
MergeSortD(R,low,mid,n);
MergeSortD(R,mid+1,high,n);
Merge(R,low,mid,high,n);
}
}
void MergeSort(int R[],int n) //二路归并排序主函数
{
MergeSortD(R,0,n-1,n);
}
/*
基数排序
基数排序适合排序元素在某个取值之内的大量数据
下面是优化后的基数排序，为了避免除法使用2的幂数作为基数,在大量随机数据测试中
下面算法的性能能够优于快速排序
基数排序的时间复杂度为O(值在基数下的位数*(n+基数值))
空间复杂度为O(n+基数值)
下面的代码是LSD自底向上的（从最低先排），它的控制机构非常简单，而且它的基本操作适合
机器语言执行，在有特殊功能的高效硬件中，LSD基数排序可能是最快的
注意此处数据是非负的
*/
const static int radix=1024;
//基数为1024
static int radix_p[]={0,10,20,30};
//基数第1,2,3,4位置所在的二进制位数,这里最大位数为4,最大范围0~1024^4
inline int radix_get_part(int n,int i)
//获取数n的第i个基数位置的数
{
return n>>radix_p[i]&(radix-1);
}
void RadixSort(int *R,int n)
//基数排序主函数
{
int *bucket=(int*)malloc(sizeof(int)*n);
int ct[radix],i,j,k;
for(i=0;i<2;i++)
//保证取值范围之内的整数用1024基数分解不会超过2次(小于1024^2),该值随数据决定
{
memset(ct,0,sizeof(int)*radix);
for(j=0;j<n;j++)
{
ct[radix_get_part(R[j],i)]++;
}
for(j=1;j<radix;j++)
{
ct[j]+=ct[j-1];
}
for(j=n-1;j>=0;j--) //要保证稳定性需要从后面开始向前
{
k=radix_get_part(R[j],i);
bucket[ct[k]-1]=R[j];
ct[k]--;
}
memcpy(R,bucket,sizeof(int)*n);
}
free(bucket);
}
#define MAXM 1000
int main()
{
int i;
int r1[MAXM],r2[MAXM];
for(i=0;i<MAXM;i++)
{
r1[i]=rand()%99999;
r2[i]=r1[i];
}
SInsertSort(r2,MAXM);
HeapSort(r1,MAXM);
for(i=0;i<MAXM;i++) //测试算法有无问题
{
if(r1[i]!=r2[i]) cout<<"error!"<<endl;
}
//disp_array(r1,MAXM);
}