1、冒泡：就是每次相邻的比较，较大的移到后面，一次后就移动最大的到最后面了。
#include <stdio.h>
void maopao(int *a,int len)
{
for(int y=len-1;y>0;y--)
for(int x=0;x<y;x++)
{
if(a[x]>a[x+1])
{
int b=a[x];
a[x]=a[x+1];
a[x+1]=b;
}
}
}
void main()
{
int a[]={48,62,35,77,55,14,35,98,22,40};
int len=sizeof(a)/sizeof(a[0]);
maopao(a,len);
for(int x1=0;x1<len;x1++)
{
printf("%d ",a[x1]);
}
}
2、 快速排序，用递归来理解就是先取待排序列中的一位数（通常选取第一位），将比它小的移到左边，较大的移到右边。然后左边和右边小的序列进行上面同样的方法，最终都排完。
下面是冒泡和快速排序的实现（冒泡和上面是重复的）：
#include <stdio.h>
//冒泡排序算法
void maopao(int *a,int len)
{
for(int y=len-1;y>0;y--)
for(int x=0;x<y;x++)
{
if(a[x]>a[x+1])
{
int b=a[x];
a[x]=a[x+1];
a[x+1]=b;
}
}
}
//调换数组里的2个元素内容
void change(int *c, int a,int b )
{
int q=c[a];
c[a]=c[b];
c[b]=q;
}
void kuaipai(int *a,int left,int right)
{
int lo=left;
int hg=right;
int point=hg;//从左还是右边开始找值与a[0]比。
while(lo!=hg)
{
if(point==hg)
{
if(a[hg]<a[lo])
{
change(a,lo,hg);
lo++;
point=lo;
}
else
{
hg--;
point=hg;
}
}
else if(point==lo)
{
if(a[hg]<a[lo])
{
change(a,lo,hg);
hg--;
point=hg;
}
else
{
lo++;
point=lo;
}
}
}
if((lo-1)>left)
kuaipai(a,left,lo-1);
if(lo+1<hg)
kuaipai(a,lo+1,hg);
}
void main()
{
/* 快排 */
int a[]={48,62,35,77,55,14,35,98};
int len=8;
kuaipai(a,0,len);
for(int x1=0;x1<len;x1++)
{
printf("%d ",a[x1]);
}
/* 冒泡 */
int a2[]={48,62,35,77,55,14,35,98,22,40};
//获取数组的长度
int len2=sizeof(a2)/sizeof(a2[0]);
maopao(a2,len2);
for(int x2=0;x2<len2;x2++)
{
printf("%d ",a[x2]);
}
}
3、归并排序：（java写的）,时间复杂度是O(nlogn)，额外空间复杂度为O(n)
public class Test {
public static void main(String[] args) {
int[] d={2,7,1,4,1231,343,8};
int[] d2=new int[d.length];
int[] dsorted=mergesort(d);
System.out.println(Arrays.toString(dsorted));
mergesort2(d,0,d.length-1,d2);
System.out.println(Arrays.toString(d));
}
//第一种归并易懂，但是浪费空间，每次需要创建较多的额外的空间c和a、b,额外空间复杂度为O（nlogn）
public static int[] merge(int[]a,int[]b)
{
int i=0;int j=0;int[] c=new int[a.length+b.length];int point=0;
while(i<a.length&&j<b.length)
{
if(a[i]<b[j])
{
c[point]=a[i];
point++;
i++;
}
else
{
c[point]=b[j];
point++;
j++;
}
}
while(i<a.length)
{
c[point]=a[i];
i++;
point++;
}
while(j<b.length)
{
c[point]=b[j];
j++;
point++;
}
return c;
}
public static int[] mergesort(int[]c)
{
int len=c.length;
if(len>=2){
int mid=(len-1)/2;
int[]a=Arrays.copyOfRange(c, 0, mid+1);
int[]b=Arrays.copyOfRange(c,mid+1, len);
int[]a2=mergesort(a);
int[]b2=mergesort(b);
return merge(a2,b2);
}
else
return c;
}
//下面是第二中方法，节约了空间，每次合并的内容都保存在c中，这样只需要额外的空间c2即O(n)
public static void merge2(int[] c,int low,int mid,int high,int[] c2)
{
int i=low;int j=mid+1;int point=low;
while(i<=mid&&j<=high)
{
if(c[i]<c[j])
{
c2[point]=c[i];
point++;
i++;
}
else
{
c2[point]=c[j];
point++;
j++;
}
}
while(i<=mid)
{
c2[point]=c[i];
i++;
point++;
}
while(j<=high)
{
c2[point]=c[j];
j++;
point++;
}
for(int x=low;x<=high;x++)
c[x]=c2[x];
}
public static void mergesort2(int[]c,int low,int high,int[] c2)
{
if(low!=high)
{
int mid=(low+high)/2;
mergesort2(c,low,mid,c2);
mergesort2(c,mid+1,high,c2);
merge2(c,low,mid,high,c2);
}
}
}