排序的整理

原创
2013/04/11 17:33
阅读数 85

自己之前搞的一些排序算法,希望对大家有帮助。差不多就这么多种吧。

void  bubblesort(int *a,int n)         //冒泡排序

{int i,j,t;

for(i=0;i<n-1;i++)

for(j=0;j<n-i-1;j++)

{  if(a[j]>a[j+1]) {

t=a[j];

a[j]=a[j+1];

a[j+1]=t;  }   }

}

void selectsort(int *a,int n)              //选择排序

int i,j,max,t;

for(i=0;i<n;i++)

{

max=i;

for(j=i+1;j<n;j++)

{

if(a[max]>a[j])

{

max=j;  }

} if(max!=i)  {

t=a[i];

a[i]=a[max];

a[max]=t; }

}

}

void InsertSort(int *a,int n)   //插入排序

{

int i,j,temp;

for(i=1;i<n;i++) {

temp=a[i];

for(j=i-1;j>=0 && a[j]>temp; j--) {

a[j+1]=a[j];

a[j]=temp;    

}

}

}

void Quicksort(int *a,int left,int right)     //快排

{

int i,j,t;

i=left;

j=right+1;

 

if(i<j) {

do {

do {

i++;

}while(i<=right && a[i]<a[left]);

 

do{

j--;

}while(j>=left && a[j]>a[left]);

if(i<j) {

t=a[i];

a[i]=a[j];

a[j]=t;

}

}while(i<j);

t=a[j];

a[j]=a[left];

a[left]=t;

Quicksort(a,left,j-1);

Quicksort(a,j+1, right);

}

}

void   creatheap(int *a,int root,int index)   //堆排

{

int i,t,flag=0;

i=2*root;

t=a[root];

while(i<=index && flag==0) {

if(i<index) {

if(a[i]<a[i+1]) {

i++;

}

}

if(a[i]< t)      //  a[i/2] ****************∂»¥Û”⁄2 ±t********************

{

flag=1;

}

else{

a[i/2]=a[i];

//   a[i]=t;      /////////////////////////////////////

i=2*i;

}

}

a[i/2]=t;

}

void sort(int *a,int index) {

int i,j,t;

for(i=index/2;i>=1;i--) {

creatheap(a,i,index);

}

for(i=index;i>=1;i--) {

t=a[1];

a[1]=a[i];

a[i]=t;

creatheap(a,1,i-1);

}

}

void shellsort(int *a,int n)          //希尔

{

int i,j,flag,gap=n,t;

while(gap>1) {

gap=gap/2;

 do{

flag=0;

for(i=0;i<n-gap;i++) {

j=i+gap; 

if(a[i]>a[j]) {

t=a[i];

a[i]=a[j];

a[j]=t;

flag=1;

}

}

}while(flag!=0); 

}

}

void Counting_Sort(int a[],int b[],int n,int max)  //基数排序

{

int i,*count;

count=(int *)malloc((max+1)*sizeof(int));

memset(count,0,(max+1)*sizeof(int));

for(i=0;i<n;i++)

count[a[i]]++;

for(i=1;i<=max;i++)

count[i]+=count[i-1];

for(i=n-1;i>=0;i--)

{

b[count[a[i]]-1]=a[i];

count[a[i]]--;

}

free(count);

}

void  MergeSort(int *a,int first,int mid,int last,int *temp)  //归并排序

{

int i=first;

int j=mid+1;

int m=mid;

int n=last;

int k=0;

 

while(i<=m &&j<=n)

{

if(a[i]<a[j])

{

temp[k++]=a[i++];

}

if(a[i]>a[j])

{

temp[k++]=a[j++];

}

}

 

while(i<=m )

{

temp[k++]=a[i++];

}

 

while (j<=n )

{

temp[k++]=a[j++];

}

 

 

for (i=0;i<k;i++)

{

 

a[first+i]=temp[i];             //

}

 

 

 

}

 

void mergesort(int *a,int first,int last,int *temp)

{

int mid=(first+last)/2;

 

if (first>=last)

{

return;

}

mergesort(a,first,mid,temp);

mergesort(a,mid+1,last,temp);

MergeSort(a,first,mid,last,temp);

 

}

 

void  Sort(int *a,int index)

{

int *temp=(int *)malloc(sizeof(a[0])*index);

 

if (temp==NULL)

{

return;

}

mergesort(a,0,index-1,temp);

}

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部