九大排序算法

1.快速排序算法

#include

#include

int n = 8;     //定义全局变量，在子函数中使用

void QSort(int *,int,int);

int Partition(int *,int,int);

void Print(int *);

int main()

{

   int a[9] = {0,4,5,6,1,2,3,9,1};

   QSort(a,1,n);   //快速排序调用

   Print(a);   //输出排序后的结果

   return 0;

}

void Print(int a[])

{

   int i;

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

       printf("%d\t",a[i]);

}

int Partition(int a[],int low,int high)

{

   int i,j,tmp;

   a[0] = a[low];  //保留第一个数组元素存放基准数

    i= low;

    j= high;

   while(i < j)

    {

       while((i < j) && (a[j] >= a[0]))    //从右边开始查找，直到找到第一个小于基准数的值为止

           j--;

       while((i < j) && (a[i] <= a[0]))    //在从左边开始查找，直到找到第一个大于基准数的值为止

           i++;

       if(i < j)   //交换俩个数在数组中的位置

       {

           tmp = a[i];

           a[i] = a[j];

           a[j] = tmp;

       }

    }

   a[low] = a[i];  //也可以写为a[low] =

a[i]，将基准数归位

   a[i] = a[0];    //将基准数归位   

   return i;

}

void QSort(int a[],int low,int high)

{

   int i;

   if(low < high){

       i = Partition(a,low,high);

       QSort(a,low,i-1);   //继续处理左侧数组元素，递归过程

       QSort(a,i+1,high);  //继续处理右侧数组元素，递归过程

    }

}

2.直接插入排序

/*1.将数组划分为有序和无序俩组，其中a[1]~a[i-1]为有序组，a[i]~a[n]为无序组

2.其中，a[i]为基准数，即无序组中的第一个元素

3.引入a[0]，保存基准数a[i]的值，并且作为while循环的判断条件

4.在插入第i个记录a[i]时，前面的a[1]~a[i-1]已经排好序，然后将a[i]与a[i-1]~a[1]

由后向前依次进行比较，找到a[i]的插入位置j,与此同时由后向前依次将a[i-1]~a[j]

顺序后移一个位置

5.将a[i]放入到让出来的位置a[j]处

6.重复2~5步，知道排序完成*/

#include

#include

void D_Insert(int *,int);

void Print(int *,int);

int main()

{

   int n = 6;

   int a[] = {0,44,33,55,22,77,11};

   D_Insert(a,n);

   Print(a,n);

   return 0;

}

void D_Insert(int *a,int n)

{

   int i,j;

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

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

           a[0] = a[i];

           j = i-1;

           while(a[j] > a[0])

           {

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

                j--;

           }

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

       }

    }

}

void Print(int a[],int n)

{

   int i;

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

       printf("%d\t",a[i]);

}

3.冒泡排序

#include

#include

void BSort(int *,int);

void Print(int *,int);

int main()

{

   int n = 7;

   int a[] = {10,44,33,55,22,77,11};

   BSort(a,n);

   Print(a,n);

   return 0;

}

void BSort(int *a,int n)

{

   int i,j,swap,tmp;

   /*比较n-1趟*/

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

       swap = 0;

       for(j = 0;j < n-1;j++){/*比较n-1次*/

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

               tmp = a[j];

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

               a[j+1] = tmp;

               swap = 1;    //交换发生

           }

       }

       if(swap == 0)   //本趟比较中，没有交换发生，则说明已经排序好，终止循环

           break;

    }

}

void Print(int a[],int n)

{

   int i;

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

       printf("%d\t",a[i]);

}

4.选择排序

#include

#include

void BSort(int *,int);

void Print(int *,int);

int main()

{

   int n = 7;

   int a[] = {10,44,33,55,22,77,11};

   BSort(a,n);

   Print(a,n);

   return 0;

}

void BSort(int *a,int n)

{

   int i,j,k,tmp;

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

       k = i;

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

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

                k = j;

       }

       if(k != i){

           tmp = a[i];

           a[i] = a[k];

           a[k] = tmp;

       }

    }

}

void Print(int a[],int n)

{

   int i;

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

       printf("%d\t",a[i]);

}

5.希尔排序

#include

#include

#define MAXSIZE 15

void Print(int a[])

{

   int i;

   for(i = 1;i <= MAXSIZE-1;i++)

        printf("%d\t",a[i]);

}

void ShellInsert(int a[],int n,int d)

{

   int i,j;

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

    {

       if(a[i] < a[i-d])

       {

           a[0] = a[i];

           for(j=i-d; j>0&&a[0]

                a[j+d] = a[j];

           a[j+d] = a[0];

       }

    }

}

void ShellSort(int a[],int n)

{

   int d[MAXSIZE],t,i;

   printf("请输入增量因子的个数:\n");

   scanf("%d",&t);

   printf("由大到小输入增量因子:\n");

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

       scanf("%d",&d[i]);

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

    {

       ShellInsert(a,n,d[i]);

       printf("\n第%d趟(d=%d):\n",i,d[i]);

       Print(a);

    }

}

int main()

{

   int a[MAXSIZE]={0,39,80,76,48,13,29,50,78,30,11,100,7,48,86};

   ShellSort(a,MAXSIZE-1);

   return 0;

}

6.归并排序

#include

#include

#define MAXSIZE 9

void Print(int a[],int n)

{

   int i;

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

       printf("%d\t",a[i]);

   printf("\n");

}

void Merge(int a2[],int a1[],int l,int

m,int h)

{

   int i,j,k;

    i= k = l;

    j= m+1;

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

       if(a2[i] <= a2[j])

           a1[k++] = a2[i++];

       else

           a1[k++] = a2[j++];

   while(i<=m)

       a1[k++] = a2[i++];

   while(j<=h)

       a1[k++] = a2[j++];

   Print(a1,k);

}

void MergeSort(int a[],int a1[],int l,int

h)

{

   int m;

   int a2[MAXSIZE];

   if(l == h)

       a1[l] = a[l];

   else

    {

       m = (l+h)/2;

       MergeSort(a,a2,l,m);

       MergeSort(a,a2,m+1,h);

       Merge(a2,a1,l,m,h);

    }

}

int main()

{

   int a[MAXSIZE]={0,48,33,61,96,72,11,25,48};

   int a1[MAXSIZE];

   MergeSort(a,a1,1,MAXSIZE-1);

   return 0;

}

7.堆排序

#include

#include

#define MAXSIZE 7

void Print(int a[],int n)

{

   int i;

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

       printf("%d\t",a[i]);

   printf("\n");

}

void HeapAdjust(int a[],int l,int h)

{

   int i,j;

    i= l;

   a[0] = a[l];

   for(j=2*i;j<=h;j=2*j)

    {

       if(j

           j = j+1;

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

           break;

       a[i]=a[j];

       i=j;

    }

   a[i]=a[0];

}

void HeapSort(int a[],int n)

{

   int i;

   for(i=n/2;i>=1;i--)

       HeapAdjust(a,i,n);

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

    {

       a[0] = a[1];

       a[1] = a[i];

       a[i] = a[0];

       HeapAdjust(a,1,i-1);

    }

}

int main()

{

   int a[MAXSIZE]={0,47,33,25,82,72,11};

   HeapSort(a,MAXSIZE-1);

   Print(a,MAXSIZE-1);

   return 0;

}