排序算法总结

数据结构中的排序算法：包括冒泡排序、冒泡排序优化算法、选择排序、插入排序、希尔排序和快速排序。分别使用程序实现各个算法。

一、冒泡排序
#include
#include
using namespace std;

#define N 10

//交换函数声明
template
void swap(T x[],int m,int n);
//冒泡排序函数
template
void BubbleSort(T x[],int n);
//显示函数
template
void show(T x[],int n);

int main()
{
srand(time(NULL));
int arrayNum[N]={0};
for(int i=0;iarrayNum[i]=rand()%10;
cout<<"冒泡排序前排序:";
show(arrayNum,N);
BubbleSort(arrayNum,N);
cout<<"排序后数组元素:";
show(arrayNum,N);
return 0;
}

//函数定义
template
void show(T x[],int n)
{
for(int i=0;icout<cout<}
template
void swap(T x[],int m,int n)
{
int temp=x[m];
x[m]=x[n];
x[n]=temp;
}
template
void BubbleSort(T x[],int n)
{
for(int i=n-1;i>=1;i--)
{
for(int j=0;j{
//按从大到小顺序排列
if(x[j]<=x[j+1])
swap(x,j,j+1);
}
}
}

二、冒泡排序优化算法
#include
#include
#include
using namespace std;

#define N 10

//函数声明
void sort(int a[],int n);
void show(int a[],int n);

int main()
{
srand(time(NULL));
int array[N]={0};
for(int i=0;iarray[i]=rand()%10;
//排序前链表:
show(array,N);
clock_t t1=clock();
sort(array,N);
clock_t t2=clock();
//排序后链表:
show(array,N);
//通过计算时间差得到排序时间
cout<<"排序时间:"<return 0;
}

//函数定义
void sort(int a[],int n)
{
bool swapped;
do
{
swapped=false;
for(int i=1;iif(a[i]{
swap(a[i],a[i-1]);
swapped=true;
}
}
--n;
}while(swapped);
}
void show(int a[],int n)
{
for(int i=0;icout<cout<}

三、选择排序
#include
#include
#include
using namespace std;

#define N 10

//显示函数
void show(int x[],int n)
{
for(int i=0;icout<cout<}
//选择排序
void quitsort(int x[],int n)
{
for(int i=0;i{
int temp=i;
for(int j=i+1;j{
if(x[j]>x[temp])
temp=j;
}
if(temp!=i)
swap(x[temp],x[i]);
}
}

int main()
{
srand(time(NULL));
int array[N]={0};
for(int i=0;iarray[i]=rand()%10;
cout<<"排序前:";
show(array,N);
clock_t t1=clock();
quitsort(array,N);
clock_t t2=clock();
cout<<"排序后:";
show(array,N);
cout<<"排序时间:"<

return 0;
}

四、插入排序
#include
#include
#include
using namespace std;

#define N 10

//显示函数
void show(int x[],int n)
{
for(int i=0;icout<cout<}
//插入排序
void InsertSort(int x[],int n)
{
int temp=0;
//从第2个元素开始进行
for(int i=1;i{
if(x[i]>=x[i-1])
continue;
temp=x[i];
for(int j=i;j>0 && temp{
//将元素向后移一位
x[j]=x[j-1];
}
x[j]=temp;
}
}

int main()
{
srand(time(NULL));
int array[N]={0};
for(int i=0;iarray[i]=rand()%20;
cout<<"排序前:";
show(array,N);
clock_t t1=clock();
InsertSort(array,N);
clock_t t2=clock();
cout<<"排序后:";
show(array,N);
cout<<"排序时间:"<return 0;
}

五、希尔排序
#include
#include
#include
using namespace std;

#define N 10

//显示函数
void show(int x[],int n)
{
for(int i=0;icout<cout<}
//希尔排序
void ShellInsert(int x[],int dk)
{
for(int i=dk;i{
if(x[i-dk]<=x[i])
continue;
int temp=x[i];
for(int j=i-dk;j>=0 && tempx[j+dk]=x[j];
x[j+dk]=temp;
}
}
void ShellSort(int x[],int dlta[],int n)
{
for(int k=0;kShellInsert(x,dlta[k]);
}

int main()
{
srand(time(NULL));
int array[N]={0};
int dlta[]={5,3,1};
for(int i=0;iarray[i]=rand()%20;
cout<<"排序前:";
show(array,N);
ShellSort(array,dlta,3);
cout<<"排序后:";
show(array,N);
return 0;
}

六、快速排序
#include
#include
#include
using namespace std;

#define N 10

//显示函数
void show(int x[],int n)
{
for(int i=0;icout<cout<}
//快速排序
void QuitSort(int x[],int n)
{
if(n<=1) return;
if(n==2)
{
if(x[1]swap(x[0],x[1]);
return;
}
//将中间元素跟第一个元素交换
swap(x[0],x[n/2]);
//取第一个元素作为分界值
int t=*x;
int *L=x+1; //从左往右走，遇到不小于分界值的停下
int *R=x+n-1; //从右往左走，遇到小于分界值的停下
while(L{
while(L++L; //向右走
while(x=t)
--R; //向左走
if(Lswap(*L,*R); //未相遇则交换
}
swap(*x,*R);
QuitSort(x,R-x); //将左边组进行递归排序
QuitSort(R+1,n-(R-x)-1); //对右边组进行递归排序
}

int main()
{
srand(time(NULL));
int array[N]={0};
for(int i=0;iarray[i]=rand()%20;
cout<<"排序前:";
show(array,N);
QuitSort(array,N);
cout<<"排序后:";
show(array,N);
return 0;
}