几种常见的排序运用

排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，究竟各有什么特点呢？本文力图设计实现常用内部排序算法并进行比较。分别为起泡排序，直接插入排序，简单选择排序，快速排序，堆排序，针对关键字的比较次数和移动次数进行测试比较。

 

　　问题分析和总体设计

 

ADT OrderableList

{

          

数据对象：D={ai| ai∈IntegerSet,i=1,2,…,n,n≥0}

          

数据关系：R1={〈ai-1，ai〉|ai-1, ai∈D, i=1,2,…,n}

 

1、起泡排序

 

　  算法：核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后，交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好。

//冒泡排序函数

void bsort::bubblesort(double *y, int m)

{

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

   {

       flag=0;

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

       {

           if(y[j-1]>y[j])

           {

              temp=y[j-1];

              y[j-1]=y[j];

              y[j]=temp;

              flag=1;

           }

       if(flag==0) break;           

       }                

                      

   }

 

 

2、直接插入排序

 

算法：经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]，则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。

//插入排序函数

void isort::insertion_sort(double *x, int m)

{

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

   {

      temp=x[i];

      j=i;

      while((j>0)&&(x[j-1]>temp))

      {

          x[j]=x[j-1];

          j--;

      }

      x[j]=temp;

                      

   }   

 

3、简单选择排序

 

　　算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来找第二小的数据，再将其同第二个数据交换位置，以此类推。

//shell排序函数

void ssort::shell_sort(double *x, int m)

{

   h=3;

   while(h>0)

   {

     

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

       {

          temp=x[i];

          j=i;

          while((j>=h)&&(x[j-h]>temp))

         {

          cout<<"排序成功"<<endl;                          

          x[j]=x[j-h];

          j-=h;

         }

         x[j]=temp;

                      

      }

      if((h/2)!=0) {h/=2;}

      else if(h==1) {h=0;}

      else{h=1;}

   }   

 

 

4、快速排序

 

　　算法：首先检查数据列表中的数据数，如果小于两个，则直接退出程序。如果有超过两个以上的数据，就选择一个分割点将数据分成两个部分，小于分割点的数据放在一组，其余的放在另一组，然后分别对两组数据排序。通常分割点的数据是随机选取的。这样无论你的数据是否已被排列过，你所分割成的两个字列表的大小是差不多的。而只要两个子列表的大小差不多。

//快速排序函数

void quicksort1::quicksort(double *x, int left, int right)

{

   l_h=left;

   r_h=right;

   pivot=x[left];

   while(left<right)

   {

       while((x[right]>=pivot)&&(left<right))

       {

          right--;  

       }

       if(left!=right)

       {

          x[left]=x[right];

          left++;

       }

       while((x[right]<=pivot)&&(left<right))

       {

          left++;  

       }

       if(left!=right)

       {

          x[right]=x[left];

          right--;

       } 

      

   }

   x[left]=pivot;

   pivot_loc=left;

   left=l_h;

   right=r_h;

   if(left<pivot_loc){quicksort(x, left, (pivot_loc-1));} 

   if(right>pivot_loc){quicksort(x,(pivot_loc+1),right);}

}