问题描述：

输入：n个数<a₁,a₂,...,a_n>。

输出：输入序列的一个排序（即重新排序）<a'₁,a'₂,...,a'_n>，使得a'₁≤a'₂≤...≤a'_n。

约定：数组A，下标从1开始

首先列出用到的数据来源程序（随机产生1000个数）文件名：SortData.h

#include
       
        #include
        
         #define RAND_NUM 10000int  *randData;void getRandData(){    int i=0;    randData=(int*)malloc(RAND_NUM*sizeof(int));    for ( i = 0; i < RAND_NUM; i++)        randData[i]=1+(int)(RAND_NUM*1.0*rand()/(RAND_MAX+1.0)); }void printRandData(){    int i=0;    for ( i = 0; i < RAND_NUM; i++)    {        if(i%15==0)            printf("\n");        printf("%5d",randData[i]);    }    printf("\n");}
        
       

测试程序如下：其中红色XXX.h为不同的排序程序，替换后即可直接测试 #include
       
        #include
        
         #include
         
          #include"SortData.h"#include"XXX.h"int main(){    clock_t start,finish;    double duration;        int wait;    printf("Before Sort:");    getRandData();    printRandData();    start=clock();    XXX(randData,RAND_NUM);    finish=clock();    printf("After Sort:");    printRandData();    duration = (double)(finish - start) / CLOCKS_PER_SEC;    printf( "Sort Used time:%f seconds\n", duration );    scanf("%d",&wait);}
         
        
       

 

1.冒泡排序

算法思想：　将被排序的记录数组A[1..n]垂直排列，每个记录A[i]看作是重量为A[i]的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

算法伪代码如下：

1 BUBBLE_SORT(A)2 i <- length(A)3 for i downto 14    j=15   while j
       
        A[j] 8         j++
       

 举例说明：数组A{5,1,3,9,2}，冒泡排序执行过程如下：

如上图所示，A4,A5，数组A已经排好了，所以不需要移动数组元素。

 冒泡排序源代码如下，BubbleSort.h

#include
       
        /*冒泡排序：数组a,需要排序数组length为数组长度*/void BubbleSort(int *a,int length){    int flage=0;    int i=length-1;    int j;    int swap;    for (; i >-1; i--)    {        if(flage==1)            break;        j=0;        while(j
       

运行结果如下图：

 2.插入排序

算法思想：类似于打牌的过程，手中的牌代表已经排好序的数组，而桌子上的牌代表未排序的数组。

算法伪代码如下：

INSERT_SORT(A)j<-2while j<=length(A)  do key<-A[j]     i=j-1     while(i>0 and A[i]>key)         do A[i+1]<-A[i]          i<-i-1A[i+1]<-key

举例说明：数组A{5,1,3,9,2}，插入排序执行过程如下：

插入排序源代码如下：

#include
       
        /*插入排序：数组a：待排序数组length:数组长度*/void InsertSort(int a[],int length){    int key;    int j;    if(length<=0)        return ;    for (int i = 1; i < length; i++)    {        key=a[i];        j=i-1;        while(j>=0&&a[j]>key)        {            a[j+1]=a[j];            j--;        }        a[j+1]=key;    }    }
       

运行结果如下：

3.选择排序

算法思想：首先找出A中最小的元素，并将其余A[1]中的的元素交换。接着，找出A中的次小最小元素，并将其与A[2]中的元素互换。对A中头n-1个元素继续这一过程。

伪代码如下：

SELECT_SORT(A)for j<-2 to length[A]  min=A[j-1]  i=j   while i<=length[A]    if A[i]
       
        A[j-1]
       

举例说明：数组A{5,1,3,9,2}，选择排序执行过程如下：

上图省略了找最小值的过程。

选择排序源代码如下：

#include
       
        /*选择排序：数组a：待排序数组length:数组长度*/void SelectionSort(int a[],int length){    int i,j,min,swap,index;    for ( i = 1; i < length; i++)    {        min=a[i-1];        j=i;        index=i-1;        while (j
       

运行结果如下图所示：

4.合并排序

算法思想：分解：将n个元素分成各含n/2个元素的子序列。解决：用合并排序法对两个字序列递归地排序；合并：合并两个已排序的子序列以得到排序结果。

算法伪代码如下：

MERGE_SORT(A，p,r)  if p

举例说明：数组A{5,1,3,9,2}，合并排序执行过程如下：

上图中，向下的箭头表示分治的过程，向上的箭头表示合并的过程。

合并排序源代码如下所示：

#include
       
        #include
        
         void Merge(int a[],int p,int q, int r){    int ln=q-p+1;    int rn=r-q;    int k=p,i,j;    int *L=(int *)calloc(ln,sizeof(int));    int *R=(int *)calloc(rn,sizeof(int));    if(!L||!R)    {        printf("calloc Error!");        return ;    }    for (i = 0; i < ln; i++)        *(L+i)=a[p+i];    for (j = 0; j < rn; j++)        *(R+j)=a[q+1+j];    i=p;    j=q+1;    while(k<=r)    {        if(i==q+1)        {            while(j<=r&&k<=r)            {                a[k++]=*(R+j-q-1);                j++;            }        }        else if(j==r+1)        {            while(i<=q&&k<=r)            {                a[k++]=*(L+i-p);                i++;            }        }        else if(*(R+j-q-1)>*(L+i-p))        {            a[k++]=*(L+i-p);            i++;        }        else        {            a[k++]=*(R+j-q-1);            j++;        }                }}void MergeSort(int a[],int p,int r){    if(p>=r)        return;    int q=(p+r)/2;    MergeSort(a,p,q);    MergeSort(a,q+1,r);    Merge(a,p,q,r);}
        
       

运行结果如下图所示：

5.堆排序

我以前写过一篇关于堆排序的博客，这是地址

这是给出源代码和运行结果：

#include
       
        #include
        
         int heap_size=0;int array_length=0;/*返回结点i的左结点*/int LEFT(int i){    return 2*i;}/*返回结点i的右结点*/int RIGHT(int i){    return 2*i+1;}/*返回结点i的父节点*/int PARENT(int i){    return i/2;}/*保持最大堆性质LEFT(i)和RIGHT(i)为最大堆*/void MAX_HEAPIFY(int a[],int i){    int r=RIGHT(i);    int l=LEFT(i);    int largest=-1;    int temp;    if((l<=heap_size)&&(a[l]>a[i]))        largest=l;    else         largest=i;    if((r<=heap_size)&&(a[r]>a[largest]))        largest=r;    if(largest!=-1&&largest!=i)    {        temp=a[largest];        a[largest]=a[i];        a[i]=temp;        MAX_HEAPIFY(a,largest);    }}/*对数组a，建立最大堆*/void BUILD_MAX_HEAP(int a[]){    heap_size=array_length;    for (int i = heap_size/2; i >= 0; i--)        MAX_HEAPIFY(a,i);}/*堆排序*/void HEAPSORT(int a[],int length){    int temp;    array_length=length;    BUILD_MAX_HEAP(a);    for (int i = array_length; i >0; i--)    {        temp=a[0];        a[0]=a[heap_size];        a[heap_size]=temp;        heap_size--;        MAX_HEAPIFY(a,0);    }}
        
       

运行结果如下图所示：

6.快速排序

算法思想：

分解：数组A[p..r]被划分成两个（可能为空）子数组A[p..q-1]和A[q+1,r]，使得A[p..q-1]中的每个元素都小于A[q]，而且小于等于A[q+1,..r]中的元素。下标也在这个划分过程中计算。

解决：通过递归调用快速排序，对数组A[p..q-1]和A[q+1..r]排序。

合并：因为两个子数组是就地排序的，将它们的合并不需要操作，整个数组A[p..r]已经排序。

快速排序伪代码如下：

QUICK_SORT(A,p,r) if p
       
         A[j]exchange A[i+1] <-> A[r]return i+1
       

举例说明：数组A{5,1,3,9,2}，快速排序执行过程如下：

程序源代码如下：

#include
       
        /*对数组a[p...r]进行划分，返回划分的位置*/int PARTITION(int a[],int p,int r){    int key=a[r];    int i=p-1;    int temp;    for (int j = p; j < r; j++)        if(a[j]<=key)        {            temp=a[j];            a[j]=a[++i];            a[i]=temp;        }        temp=a[i+1];        a[i+1]=a[r];        a[r]=temp;        return i+1;}/*对数组a[p...r]进行快速排序*/void QUICKSORT(int a[],int p,int r){    if(p>=r)        return ;    int q=PARTITION(a,p,r);    QUICKSORT(a,p,q-1);    QUICKSORT(a,q+1,r);}
       

测试结果如下图所示：

7.希尔排序

算法思想：将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。

举例说明：数组A{1,55,3,9,2}，希尔排序执行过程如下：

第一次 gap = 5/2=2 即 1,3,2一组，5,9一组

第二次 gap= 2/2=1 即 对整个数组进行插入排序

第三重 gap=1/2=0，必须要进行排序

希尔排序源代码如下：

1 #include
       
         2 /* 3 希尔排序 4 数组a：待排序的数组 5 length:数组长度 6 */ 7 void ShellSort(int a[],int length) 8 { 9     int gap=length/2;//初始步长为数组长度的一般10     int j,i,key,swap,k;11     for (;gap>0;gap/=2)12     {13         for (i= 0; i < gap; i++)14         {15             for(j=i+gap;j
        
         =0&&a[k]>key)22                     {23                         a[k+gap]=a[k];24                         k-=gap;25                     }26                     a[k+gap]=key;27                 }28             }29         }30     }31 }
        
       

运行结果如下图所示：

 8.计数排序

算法思想：n个输入元素中的每个都是介于0到k之间的整数

伪代码如下：

1 COUNT-SORT(A) 2    for i<- 0 to k 3       C[i] <- 0 4    for j<-1 to length[A] 5      C[A[j]] <-C[A[j]]+1 6    for i<- 1 to k 7      C[i] <- C[i-1]+C[i] 8    for j<-length[A] downto 1 9        do B[C[A[j]]] <- A[j]10             C[A[j]] <- C[A[j]]-1 11

举例说明：数组A{5,1,3,9,2}，计数排序执行过程如下：

计数排序代码如下：

1 #include
       
         2 #include
        
          3 #include"SortData.h" 4 void CountSort(int a[],int length) 5 { 6     int *C=(int*)malloc(RAND_NUM*sizeof(int));; 7     int *b=(int*)malloc(length*sizeof(int));; 8     int i,j,k; 9     for ( i = 0; i < RAND_NUM+1; i++)10         C[i]=0;11     for (j = 0; j < length; j++)12         C[a[j]]++;13     for ( i = 1; i < RAND_NUM+1; i++)14         C[i]=C[i]+C[i-1];15     for (k= length-1; k>-1 ; k--)16     {17         b[C[a[k]]]=a[k];18         C[a[k]]--;19     }20     for ( k = 0; k < length; k++)21         a[k]=b[k];22 }
        
       

运行结果如下图所示：