排序算法
快速排序
C语言快速排序qsort(数组，长度，元素大小，cmp函数(*,*))//注意函数cmp的参数为指针
#include <stdio.h>
#include <stdlib.h>
#include <stdlib.h> //qsort函数
int cmp (int a,int b)
{
return a -b;
} //0 3 2 1 4 5 6 9 8 7
int main()
{
inta[10],i,x;
for(i=0;i<10; i++)
{
scanf("%d",&a[i]);
}
qsort(a,10,sizeof(a[0]),cmp);
for(i=0;i<10; i++)
{
printf("%d ",a[i]);
}
return 0;
}
自定义qsort void qsort2(int a[],int l,int r){
if(l<r){
inti=l,j=r;
intk=a[i];
while(i<j){
while(i<j&&a[j]>=k){
j--;
}
a[i]=a[j];
while(i<j&&a[i]<=k){
i++;
}
a[j]=a[i];
}
a[i]=k;
qsort2(a,l,i-1);
qsort2(a,i+1,r);
}
}
冒泡排序
void bubble(int a[],int n)
{
int i,j;
for(i=0;i<n-1; i++)
{
for(j=n-1; j>i; j--)
{
if(a[j]<a[j-1])
{
int t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
}
}
}
归并排序
void merge(int a[],int l,int m,int r){
inttemp[r-l+1];
inti=l,j=m+1,k=0;
while(i<=m&&j<=r){
if(a[i]<a[j])temp[k++]=a[i++];
elsetemp[k++]=a[j++];
}
while(i<=m){
temp[k++]=a[i++];
}
while(j<=r){
temp[k++]=a[j++];
}
for(i=0;i<k;i++){
a[l+i]=temp[i];
}
}
void mergeSort(int a[],int l,int r){
if(l<r){
intm=(l+r)/2;
mergeSort(a,l,m);
mergeSort(a,m+1,r);
merge(a,l,m,r);
}
}
选择排序
void selectSort(int a[],int n){
int i,j;
for(i=0;i<n;i++){
intk=i;
for(j=i+1;j<n;j++){
if(a[j]>a[k]){
k=j;
}
if(k!=i){
int t=a[i];
a[i]=a[k];
a[k]=t;
}
}
}
}
堆排序
#include <stdio.h>
#include <stdlib.h> typedef struct heap_t{
int *arr; //point for an array to store heap value.
intheapMaxIndex; //heap element max indexnumber
intarrLength; //array length of arr }Heap; void printArr(int *p, int size)
{
int i;
for(i=0;i<size;i++)
{
printf("%d",p[i]);
}
} void maxHeapify(Heap *hp, unsigned int nodei)
{
unsignedint l = (nodei+1) << 1 - 1; //leftchild = 2i-1, -1 ?:arr[0..n-1]
unsignedint r = (nodei+1) << 1 ; //right child = 2i
unsignedint largest = 0;
intheapMaxI = hp->heapMaxIndex; if(l<= heapMaxI && hp->arr[l] > hp->arr[nodei])
largest= l ;
else
largest= nodei ; if(r<= heapMaxI && hp->arr[r] > hp->arr[largest])
largest= r ; if(largest!=nodei)
{
//exchange
inttmp ;
tmp= hp->arr[largest];
hp->arr[largest]= hp->arr[nodei];
hp->arr[nodei]= tmp; maxHeapify(hp,largest);
}else{
return;
} } Heap *createHeap(int *arrp, int arrLength,Heap *heap)
{
int i;
heap->arr =arrp;
heap->heapMaxIndex = arrLength-1;
heap->arrLength = arrLength; //for an heapa[0..n-1]; a[(n/2)..n-1] all are leaves
for(i =arrLength>>1-1; i >=0; i--)
maxHeapify(heap,i);
return heap;
} void heapSort(Heap *hp)
{
int tmp;
int last;
while(hp->heapMaxIndex>0)
{
last= hp->heapMaxIndex ;
//exchange
tmp= hp->arr[last];
hp->arr[last]= hp->arr[0];
hp->arr[0]= tmp;
hp->heapMaxIndex-= 1;
maxHeapify(hp,0); //make heap from root node 0 to heapMaxIndex
} } int main()
{
inta[]={15,25,32,23,1,-4,35,2,-85,42,0,12,26,56,45,12,145,17,25,21};
printArr(a,20);
printf("\n"); Heaphpa,*phpa;
phpa= createHeap(a,20,&hpa);
heapSort(phpa); printArr(a,20);
putchar('\n');
return 0;
}