admin 信阳6种常见的排序算法的C语言实现
在c言语学习阶段，我们如好转经过c言语来完成几种罕见的排序算法？下面是小编在网络上为我们整理的6种罕见的排序算法的C言语完成：
6种罕见的排序算法的C言语完成
1）“冒泡法1”
其原理为从a[0]末尾，依次将其和前面的元素比拟，若a[0]>a[i]，则交流它们，不时比拟到a[n]。
同理对a[1],a[2],…a[n-1]处置，即完成排序。
[cpp] view plaincopy
void bubble（int *a,int n）
{
int i,j,temp;
for（i=0;i<n-1;i++）
{
for（j=i+1;j<n;j++） /*留意循环的上下限*/
{
if（a[i]>a[j]）
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
}
2）“冒泡法2”
冒泡法还有第二种方式，或许叫沉底法也行：
每相邻的两个数停止比拟，假设发现b[j]>b[j+1]
[cpp] view plaincopy
void bubble（int *b,int n）
{
int i,j,temp;
for（i=0;i<n-1;i++）
{
for（j=0;j<n-i-1;j++）
{
if（b[j]>b[j+1]）
{
temp = b[j];
b[j] = b[j+1];
b[j+1]=temp;
}
}
}
}
冒泡法原理复杂，但其缺陷是交流次数多，效率低。
下面引见一种源自冒泡法但更有效率的方法“选择法”。
3）“选择法”
选择法循环进程与冒泡法1分歧，它还定义了记号k=i,然后依次把a[k]同前面元素比拟，若a[k]>a[j],则使k=j.
最后看看k=i能否还成立，不成立则交流a[k],a[i],这样就比冒泡法省下许多无用的交流，提高了效率。
[cpp] view plaincopy
void choise（int *a,int n）
{
int i,j,min,temp;
for（i=0;i<n-1;i++）
{
min=i; /*给记号赋值*/
for（j=i+1;j<n;j++）
{
if（a[min]>a[j]）
min=j; /*是k总是指向最小元素*/
}
if（i!=min） /*当k!=i是才交流，否则a[i]即为最小*/
{
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
}
4）“拔出法”
拔出法是一种比拟直观的排序方法。
它首先把数组头两个元素排好序，再依次把前面的元素拔出适当的位置。
把数组元素插完也就完成了排序。
[cpp] view plaincopy
void （int *a,int n）
{
int i,j,temp;
for（i=1;i<n;i++）
{
temp=a[i]; /*temp为要拔出的元素*/
j=i-1;
while（ j>=0&&temp<a[j] ）
{ /*从a[i-1]末尾找比a[i]小的数，同时把数组元素向后移*/
a[j+1]=a[j];
j–;
}
a[j+1]=temp; /*拔出*/
}
}
但说到高效率，非“快速法”莫属，如今就让我们来了解它。
5）“快速法”
快速法定义了三个参数，（数组首地址*a,要排序数组起始元素下标i,要排序数组完毕元素下标j）。
它首先选一个数组元素（普通为a[ （i+j）/2 ],即中间元素）作为参照，把比它小的元素放到它的左边，比它大的放在左边。
然后运用递归，在将它左，右两个子数组排序，最后完成整个数组的排序。
下面剖析其代码：
[cpp] view plaincopy
void quick（int *a,int i,int j）
{
int m,n,temp;
int k;
m=i;
n=j;
k=a[（i+j）/2]; /*选取的参照*/
do
{
while（ a[m]<k && m<j ）
m++; /* 从左到右找比k大的元素*/
while（ a[n] >k && n>i ）
n–; /* 从右到左找比k小的元素*/
if（m<=n）
{ /*若找到且满足条件，则交流*/
temp=a[m];
a[m]=a[n];
a[n]=temp;
m++;
n–;
}
}
while（m<=n）；
if（m<j）
quick（a,m,j）； /*运用递归*/
if（n>i）
quick（a,i,n）；
}
6）“shell法”
shell法是一个叫 shell 的美国人与1969年发明的。
它首先把相距k（k>=1）的那几个元素排好序，再增加k值（普通取其一半），再排序，直到k=1时完成排序。
下面让我们来剖析其代码：
[cpp] view plaincopy
void shell（int *a,int n）
{
int i,j,k,x;
k=n/2; /*间距值*/
while（k>=1）
{
for（i=k;i<n;i++）
{
x=a[i];
j=i-k;
while（j>=0&&x<a[j]）
{
a[j+k]=a[j];
j-=k;
}
a[j+k]=x;
}
k/=2; /*增加间距值*/
}
}
下面我们曾经对几种排序法作了引见，如今让我们写个主函数检验一下。
#include
/*别偷懒，下面的“…”代表函数体，自己加上去哦！*/
void bubble（int *a,int n）
{
…
}
void choise（int *a,int n）
{
…
}
void quick（int *a,int i,int j）
{
…
}
void （int *a,int n）
{
…
}
void shell（int *a,int n）
{
…
}
/*为了打印方便，我们写一个print吧。*/
void print（int *a,int n）
{
int i;
for（i=0;i<n;i++）
printf（“%5d”,a[i]）；
printf（“ ”）；
}
main（）
{ /*为了公允，我们给每个函数定义一个相反数组*/
int a1[]={13,0,5,8,1,7,21,50,9,2};
int a2[]={13,0,5,8,1,7,21,50,9,2};
int a3[]={13,0,5,8,1,7,21,50,9,2};
int a4[]={13,0,5,8,1,7,21,50,9,2};
int a5[]={13,0,5,8,1,7,21,50,9,2};
printf（“the original list:”）；
print（a1,10）；
printf（“according to bubble:”）；
bubble（a1,10）；
print（a1,10）；
printf（“according to choise:”）；
choise（a2,10）；
print（a2,10）；
printf（“according to quick:”）；
quick（a3,0,9）；
print（a3,10）；
printf（“according to :”）；
（a4,10）；
print（a4,10）；
printf（“according to shell:”）；
shell（a5,10）；
print（a5,10）；
}
