【源码】C语言排序算法
- 时间:
- 浏览:2532
- 来源:吧啦熊
引言
C语言各种经典排序法。大学时期刚入坑的时候写的代码，近期整理电脑时发现的，就随手分享了出来，希望对新入坑的童鞋有点作用。
#include<stdio.h>
void BubbleSort(int *Array,int n);//冒泡排序法
void BubleSort_ch1(int *Array,int n);//改进后的冒泡排序法
void BubleSort_ch2(int *Array,int n);//改进的冒泡排序法
void QuickSort(int *Array,int n);//快捷排序法
void SelectSort(int *Array,int n);//直接选择排序法
void InsertSort(int *Array,int n);//直接插入法
void ShellSort(int *Array,int n);//希尔排序法
void HeapSort(int *Array,int n);//堆排序法
void MergeSort(int *Array,int n);//归并排序法
void Restore(int *Array,int i,int n)//重建堆
{
int j,k,r;
int done=0;
k=r=*(Array+i);
j=2*i;
while(j<=n&&done==0)
{
if(j<n)
{
if(*(Array+j)<*(Array+j+1))
j++;
}
if(k>=*(Array+j))
{
done=1;
}
else
{
*(Array+j/2)=*(Array+j);
j*=2;
}
}
*(Array+j/2)=r;
}
void HeapSort(int *Array,int n)
{
Array--;//该算法数组第一个位置无效。
int i,j,t;
for(i=n/2;i>0;i--)
Restore(Array,i,n);
for(i=n-1;i>0;i--)
{
t=*(Array+i+1);
*(Array+i+1)=*(Array+1);
*(Array+1)=t;
Restore(Array,1,i);
}
}
void InsertSort(int *Array,int n)//直接插入法
{
int i,j,temp;
for(i=1;i<n;i++)
{
if(*(Array+i)<*(Array+i-1))
{
temp=*(Array+i);
j=i-1;
do
{
*(Array+j+1)=*(Array+j);
j--;
}while(j>=0&&temp<*(Array+j));
*(Array+j+1)=temp;
}
}
}
void MergePass(int *a,int *b,int t,int n)
{
int i,j,index;
int beg1,end1;
int beg2,end2;
beg1=0;
index=0;
while(beg1+t<=n-1)
{
beg2=beg1+t;
end1=beg2-1;
if(beg2+t-1<=n-1)
end2=beg2+t-1;
else
end2=n-1;
i=beg1;
j=beg2;
while(i<=end1&&j<=end2)
{
if(*(a+i)<*(a+j))
{
*(b+index)=*(a+i);
i++;
index++;
}
else
{
*(b+index)=*(a+j);
j++;
index++;
}
}
while(i<=end1)
{
*(b+index)=*(a+i);
index++;
i++;
}
while(j<=end2)
{
*(b+index)=*(a+j);
index++;
j++;
}
beg1=end2+1;
}
for(i=beg1;i<n;i++,index++)
{
*(b+index)=*(a+i);
}
}
void MergeSort(int *Array,int n)
{
int *array=new int[n];
int i,j;
j=1;
while(j<n)
{
MergePass(Array,array,j,n);
for(i=0;i<n;i++)
*(Array+i)=*(array+i);
j*=2;
}
delete array;
}
//i 数组左边界
//j 数组右边界
int Partition(int *Array,int i,int j)
{
int t=*(Array+i);
while(i<j)
{
while(i<j&&*(Array+j)>=t)
j--;
if(i<j)
{
*(Array+i)=*(Array+j);
i++;
}
while(i<j&&*(Array+i)<=t)
i++;
if(i<j)
{
*(Array+j)=*(Array+i);
j--;
}
}
*(Array+i)=t;
return i;
}
void ToQuickSort(int *Array,int low,int high)
{
int mid;
if(low<high)
{
mid=Partition(Array,low,high);
ToQuickSort(Array,low,mid-1);
ToQuickSort(Array,mid+1,high);
}
}
void QuickSort(int *Array,int n)
{
ToQuickSort(Array,0,n-1);
}
void SelectSort(int *Array,int n)//直接选择排序法
{
int i,j,m,a;
for(i=0;i<n-1;i++)
{
m=i;
for(j=i+1;j<n;j++)//从无序序列中找出具有最小值的位置
{
if(*(Array+j)<*(Array+m))
m=j;
}
if(m!=i)
{
a=*(Array+m);
*(Array+m)=*(Array+i);
*(Array+i)=a;
}
}
}
void ShellInsert(int *Array,int step,int n)
{
int i,j,rec;
for(i=1+step;i<n;i++)
{
if(*(Array+i)<*(Array+i-step))
{
j=i-step;
rec=*(Array+i);
do
{
*(Array+j+step)=*(Array+j);
j-=step;
}while(j>=0&&rec<*(Array+j));
*(Array+j+step)=rec;
}
}
}
void ShellSort(int *Array,int n)
{
int addition=n;
do
{
addition=addition/3;
ShellInsert(Array,addition,n);
}while(addition>0);
}
void main()
{
int array[9]={5,9,2,16,10,4,12,15,8};
int i;
printf("排序前:");
for(i=0;i<9;i++)
printf("%d ",array[i]);
//BubbleSort(array,8); //冒泡排序法
//BubleSort_ch1(array,8); //改进冒泡排序
//BubleSort_ch2(array,8); //改进冒泡排序
//QuickSort(array,9);
// SelectSort(array,9);
//InsertSort(array,9);//直接插入发
//ShellSort(array,9);
//HeapSort(array,9);
MergeSort(array,9);
printf("\n排序后:");
for(i=0;i<9;i++)
printf("%d ",array[i]);
printf("\n");
}void InsertSort(int *Array,int n)//直接插入法
{
int i,j,temp;
for(i=1;i<n;i++)
{
if(*(Array+i)<*(Array+i-1))
{
temp=*(Array+i);
j=i-1;
do
{
*(Array+j+1)=*(Array+j);
j--;
}while(j>=0&&temp<*(Array+j));
*(Array+j+1)=temp;
}
}
}void MergePass(int *a,int *b,int t,int n)
{
int i,j,index;
int beg1,end1;
int beg2,end2;
beg1=0;
index=0;
while(beg1+t<=n-1)
{
beg2=beg1+t;
end1=beg2-1;
if(beg2+t-1<=n-1)
end2=beg2+t-1;
else
end2=n-1;
i=beg1;
j=beg2;
while(i<=end1&&j<=end2)
{
if(*(a+i)<*(a+j))
{
*(b+index)=*(a+i);
i++;
index++;
}
else
{
*(b+index)=*(a+j);
j++;
index++;
}
}
while(i<=end1)
{
*(b+index)=*(a+i);
index++;
i++;
}
while(j<=end2)
{
*(b+index)=*(a+j);
index++;
j++;
}
beg1=end2+1;
}
for(i=beg1;i<n;i++,index++)
{
*(b+index)=*(a+i);
}
}
void MergeSort(int *Array,int n)
{
int *array=new int[n];
int i,j;
j=1;
while(j<n)
{
MergePass(Array,array,j,n);
for(i=0;i<n;i++)
*(Array+i)=*(array+i);
j*=2;
}
delete array;
}void SelectSort(int *Array,int n)//直接选择排序法
{
int i,j,m,a;
for(i=0;i<n-1;i++)
{
m=i;
for(j=i+1;j<n;j++)//从无序序列中找出具有最小值的位置
{
if(*(Array+j)<*(Array+m))
m=j;
}
if(m!=i)
{
a=*(Array+m);
*(Array+m)=*(Array+i);
*(Array+i)=a;
}
}
}void ShellInsert(int *Array,int step,int n)
{
int i,j,rec;
for(i=1+step;i<n;i++)
{
if(*(Array+i)<*(Array+i-step))
{
j=i-step;
rec=*(Array+i);
do
{
*(Array+j+step)=*(Array+j);
j-=step;
}while(j>=0&&rec<*(Array+j));
*(Array+j+step)=rec;
}
}
}
void ShellSort(int *Array,int n)
{
int addition=n;
do
{
addition=addition/3;
ShellInsert(Array,addition,n);
}while(addition>0);
}
猜你喜欢