首页 > 代码库 > 各种排序

各种排序

#include<stdio.h>
void swap(int a[],int i,int j)
{
int t=a[i];
a[i]=a[j];
a[j]=t;
}

 

 

 

 

 

 

 


/*冒泡排序**/

/*

冒泡排序是最简单最基本的排序方法之一。

冒泡排序的思想很简单,就是以此比较相邻的元素大小,将小的前移,大的后移,

就像水中的气泡一样,最小的元素经过几次移动,会最终浮到水面上。

举例分析说明一下,如下数据:

2 7 4 6 9 1 首先比较最后两个数字,发现1比9小,于是前移

2 7 4 6 1 9 然后比较6和1

2 7 4 1 6 9 继续前移,然后是4和1

2 7 1 4 6 9 7和1比较

2 1 7 4 6 9 2和1

1 2 7 4 6 9 至此,第一趟冒泡过程完成,最小的元素1被移到第一个,不再参与后面的排序过程。

下一趟冒泡过程同理,比较6和9,以此类推,最终得到结果。

*/
void maopao(int a[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
swap(a,i,j);
}
}
}
}

 

 

 

 

 

 

 

/*插入排序*/

/*

插入排序基本思想:

最基本的操作是将第i个记录插入到前面i-1个以排好序列的记录中。

具体过程是:将第i个记录的关键字K依次与其前面的i-1个已经拍好序列的记录进行比较。

将所有大于K的记录依次向后移动一个位置,直到遇到一个关键字小于或等于K的记录,

此时它后面的位置必定为空,则将K插入。

*/
void charu(int a[],int n)
{
int i,j;
for(i=1;i<n;i++)
{
for(j=i-1;j>=0;j--)
{
if(a[j]<a[j+1])
break;
swap(a,j,j+1);
}
}
}

 

 

 

 

 

/*选择排序*/

/*选择排序的思想非常直接,

不是要排序么?那好,我就从所有序列中先找到最小的,然后放到第一个位置。

之后再看剩余元素中最小的,放到第二个位置……

以此类推,就可以完成整个的排序工作了。

可以很清楚的发现,选择排序是固定位置,找元素。

相比于插入排序的固定元素找位置,是两种思维方式。

不过条条大路通罗马,两者的目的是一样的。

*/

void xuanze(int a[],int n)
{
int i,j;
for(i=0;i<n;i++)
{
int min=1000000;
for(j=i;j<n;j++)
{
if(a[j]<min)
{
min=a[j];
swap(a,i,j);
}
}
}
}

 

 

 

 

/*快排,即桶排序*/

/*快速排序采用的思想是分治思想。

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置。递归快速排序,将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置,排序完成。所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。

举例说明一下吧,这个可能不是太好理解。假设要排序的序列为

2 2 4 9 3 6 7 1 5 首先用2当作基准,使用i j两个指针分别从两边进行扫描,把比2小的元素和比2大的元素分开。首先比较2和5,5比2大,j左移

2 2 4 9 3 6 7 1 5 比较2和1,1小于2,所以把1放在2的位置

2 1 4 9 3 6 7 1 5 比较2和4,4大于2,因此将4移动到后面

2 1 4 9 3 6 7 4 5 比较2和7,2和6,2和3,2和9,全部大于2,满足条件,因此不变

经过第一轮的快速排序,元素变为下面的样子

[1] 2 [4 9 3 6 7 5]

之后,在把2左边的元素进行快排,由于只有一个元素,因此快排结束。右边进行快排,递归进行,最终生成最后的结果。

/*
int quicksort(int v[], int left, int right){
if(left < right){
int key = v[left];
int low = left;
int high = right;
while(low < high){
while(low < high && v[high] > key){
high--;
}
v[low] = v[high];
while(low < high && v[++low] < key){
//low++;
}
v[high] = v[low];
}
v[low] = key;
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}

 

 

 

 

 

 

 

 

/*希尔排序*/

/*

希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。

该方法又称缩小增量排序,

 基本思想:
     先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。

所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序;

然后,取第二个增量d2<d1重复上述的分组和排序,

直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
     该方法实质上是一种分组插入方法。

*/
void xier(int a[],int n)
{
int gap=n/2;
while(gap>=1)
{
for(int i=gap;i<n;i++)
{
int j,temp=a[i];
for(j=i-gap;j>=0&&temp<a[j];j=j-gap)
{
a[j+gap]=a[j];
}
a[j+gap]=temp;
}
gap=gap/2;
}
}
int main()
{
int a[10]={6,1,2,5,7,4,8,9,3,5};
int b[10]={6,1,2,5,7,4,8,9,3,5};
int c[10]={6,1,2,5,7,4,8,9,3,5};
int d[10]={6,1,2,5,7,4,8,9,3,5};
int e[10]={6,1,2,5,7,4,8,9,3,5};
printf("冒泡排序前:");
for(int i=0;i<10;i++)
{
printf(" %d",a[i]);
}
printf("\n");
maopao(a,10);
printf("冒泡排序后:");
for(int i=0;i<10;i++)
{
printf(" %d",a[i]);
}
printf("\n");
printf("插入排序前:");
for(int i=0;i<10;i++)
{
printf(" %d",b[i]);
}
printf("\n");
charu(b,10);
printf("插入排序后:");
for(int i=0;i<10;i++)
{
printf(" %d",b[i]);
}
printf("\n");
printf("选择排序前:");
for(int i=0;i<10;i++)
{
printf(" %d",c[i]);
}
printf("\n");
xuanze(c,10);
printf("选择排序后:");
for(int i=0;i<10;i++)
{
printf(" %d",c[i]);
}
printf("\n");
printf("快速排序前:");
for(int i=0;i<10;i++)
{
printf(" %d",d[i]);
}
printf("\n");
quicksort(d,0,9);
printf("快速排序后:");
for(int i=0;i<10;i++)
{
printf(" %d",d[i]);
}
printf("\n");
printf("希尔排序前:");
for(int i=0;i<10;i++)
{
printf(" %d",e[i]);
}
printf("\n");
xier(e,10);
printf("希尔排序后:");
for(int i=0;i<10;i++)
{
printf(" %d",e[i]);
}
printf("\n");
return 0;
}

各种排序