7大常用排序算法

1. 冒泡排序

 

#include <stdio.h>

typedef int bool;

void bubbleSort(int array[],int n)
{
    int i,j,temp;
    bool exchange; //判断是否交换

    for(i=0;i<n;i++)
    {
        exchange=0;
        for(j=n-2;j>=i;j--)
        {
            if(array[j+1]<array[j])
            {
                temp=array[j];
                array[j]=array[j+1];
                array[j+1]=temp;
                exchange=1;
            }
        }
        if(!exchange)
            return;
    }
}

int main()
{
    int shu[]={23,4,56,12,13,11,19,7,5,6,3,7,32,27};
    int n=sizeof(shu)/sizeof(int);
    int i;
    bubbleSort(shu,n);
    for(i=0;i<n;i++)
    {
        printf("%d<",shu[i]);
    }
    return 0;
}


2. 快速排序

#include <stdio.h>
#define MAX 255
int Partition(int i,int j,int R[])
{
    int pivot=R[i];
    while(i<j){
        while(i<j&&R[j]>=pivot)
            j--;
        if(i<j)
            R[i++]=R[j];
        while(i<j&&R[i]<=pivot)
            i++;
        if(i<j)
            R[j--]=R[i];
       }
      R[i]=pivot;
      return i;
}

void Quick_Sort(int low,int high,int R[])
{
     int pivotpos;
     if(low<high){
        pivotpos=Partition(low,high,R);
        Quick_Sort(low,pivotpos-1,R);
        Quick_Sort(pivotpos+1,high,R);
      }
}

int main()
{
    int R[]={23,4,56,12,13,11,19,7,5,6,3,7,32,27};
    int n=sizeof(R)/sizeof(int);
    int i;
    Quick_Sort(0,n-1,R);
    for(i=0;i<n;i++)
    {
        printf("%d<",R[i]);
    }
    return 0;
}


3.插入排序

#include <stdio.h>

void insertSort(int array[],unsigned int n)
{
    int i,j,temp;
    for(i=1;i<n;i++)
    {
        temp=array[i];
        for(j=i;j>=1&&temp<array[j-1];j--)
        {
            array[j]=array[j-1];
        }
        array[j]=temp;
    }
}
       
int main()
{
    int shu[]={23,4,56,12,13,11,19,7,5,6,3,7,32,27};
    int n=sizeof(shu)/sizeof(int);
    int i;
    insertSort(shu,n);
    for(i=0;i<n;i++)
    {
        printf("%d<",shu[i]);
    }
    return 0;
}


4. 希尔排序

#include <stdio.h>

void shellSort(int array[],int n)
{
    int i,j,temp,k;
    int inc=n/2;
    while(inc>=1)
    {
        for(i=inc;i<n;i++)
        {
            temp=array[i];
            for(j=i;j>=inc&&temp<array[j-inc];j=j-inc)
            {
                array[j]=array[j-inc];
            }
            array[j]=temp;
        }
        inc=inc/2;
    }
}
       
int main()
{
    int shu[]={23,4,56,12,13,11,19,7,5,6,3,7,32,27};
    int n=sizeof(shu)/sizeof(int);
    int i;
    shellSort(shu,n);
    for(i=0;i<n;i++)
    {
        printf("%d<",shu[i]);
    }
    return 0;
}


5.选择排序

#include <stdio.h>

void selectSort(int array[],int n)
{
    int i,j,temp,min;
    for(i=0;i<n;i++)
    {
        min=i;
        for(j=i+1;j<n;j++)
        {
            if(array[j]<array[min])
                min=j;
        }
        temp=array[i];
        array[i]=array[min];
        array[min]=temp;
    }
}

int main()
{
    int shu[]={23,4,56,12,13,11,19,7,5,6,3,7,32,27};
    int n=sizeof(shu)/sizeof(int);
    int i;
    selectSort(shu,n);
    for(i=0;i<n;i++)
    {
        printf("%d<",shu[i]);
    }
    return 0;
}


 

6. 归并排序

#include <stdio.h>

void merge(int low,int mid,int high,int array[],int temp[])
{
    int i=low,j=mid+1,p=0;
    while(i<=mid&&j<=high)
        temp[p++]=(array[i]<array[j])?array[i++]:array[j++];
    while(i<=mid)
        temp[p++]=array[i++];
    while(j<=high)
        temp[p++]=array[j++];
    for(p=0,i=low;i<=high;i++,p++)
    {
        printf("%d<",temp[p]);
        array[i]=temp[p];
    }
    printf("\n");
}
       
mergeSort(int low,int high,int array[],int temp[])
{
    int mid;
    if(low<high)
    {
        mid=(low+high)/2;
        mergeSort(low,mid,array,temp);
        mergeSort(mid+1,high,array,temp);
        merge(low,mid,high,array,temp);
    }
}

int main()
{
    int shu[]={23,4,56,12,13,11,19,7,5,6,3,7,32,27};
    int n=sizeof(shu)/sizeof(int);
    int tem[]={0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    int i;
    mergeSort(0,n-1,shu,tem);
    for(i=0;i<n;i++)
    {
        printf("%d<",shu[i]);
    }
    return 0;
}

7.基数排序

#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define MAX 5
typedef struct node
{
    int k;
    struct node *next;
} *lnode;

lnode my_input(int *d)
{
    lnode head,temp,terminal;
    char s[MAX+1];
    printf("Input the records ('0' to end input):\n");
    scanf("%s",s);
    head=NULL;
    *d=0;
    terminal=NULL;
    while(s[0]!='0')
    {
        temp=(lnode)malloc(sizeof(struct node));
        if (strlen(s)>*d)
            *d=strlen(s);
        temp->k=atoi(s);
        if (head==NULL)
        {
            head=temp;
            terminal=temp;
        }
        else
        {
            terminal->next=temp;
            terminal=temp;
        }
        scanf("%s",s);
     }
        terminal->next=NULL;
    return head;
}

void my_output(lnode h)
{
    lnode t=h;
    printf("\n");
    while (h!=NULL)
    {
        printf("%d ",h->k);
        h=h->next;
    }
    h=t;
    /* getch(); */
}
lnode Radix_Sort(lnode head,int d)
{
    lnode p,q,h,t;
    int i,j,x,radix=1;
    h=(lnode)malloc(10*sizeof(struct node));
    t=(lnode)malloc(10*sizeof(struct node));
    for (i=d;i>=1;i--)
    {
        for (j=0;j<=9;j++)
        {
            h[j].next=NULL;
            t[j].next=NULL;
        }
        p=head;
        while (p!=NULL)
        {
            x=((p->k)/radix)%10;
            if (h[x].next==NULL)
            {
                h[x].next=p;
                t[x].next=p;
            }
        else
        {
            q=t[x].next;
            q->next=p;
            t[x].next=p;
        }
        p=p->next;
   }

    j=0;
    while (h[j].next==NULL)
    j++;
    head=h[j].next;
    q=t[j].next;
    for (x=j+1;x<=9;x++)
    if (h[x].next!=NULL)
    {
        q->next=h[x].next;
        q=t[x].next;
    }
    q->next=NULL;
    radix*=10;
    printf("\n---------------------\n");
    }
    return head;
}
void my_free(lnode h)
{
    lnode temp=h;
    while (temp)
    {
        h=temp->next;
        free(temp);
        temp=h;
    }
}
void main()
{
    lnode h;
    int d;
    h=my_input(&d);
    puts("The sequence you input is:");
    my_output(h);
    h=Radix_Sort(h,d);
    puts("\nThe sequence after radix_sort is:");
    my_output(h);
    my_free(h);
    puts("\n Press any key to quit...");
    getch();
}