常用排序方法（一）

   一、插入排序

    插入排序又分为直接插入排序、折半插入排序、表插入排序和希尔排序。不过我们最常用的就是现在即将介绍的直接插入排序。

   直接插入排序：是一种比较简单的排序方法，它的基本思想是依次将每个记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增加1的有序表。

    直接插入排序的算法描述如下：       

[csharp] 

voidStraightInsertSort(List R, int n)  

       //对顺序表R进行直接插入排序  

       {  

           int i, j;  

           for (i = 2; i <= n; i++)  //n为表长，从第二个记录起进行插入  

           {  

               R[0] =R[i];   //第i个记录复制为岗哨  

               j = j - 1;  

               while(R[0].key<R[j].key)  //与岗哨比较，直至键值不大于岗哨键值  

               {  

                   R[j + 1] =R[j];   //将第j个记录赋值给第j+1个记录  

                   j--;  

               }  

               R[j + 1] =R[0];    //将第i个记录插入到排序中  

           }  

       }  

     应用直接插入排序方法：

 

         

     这个算法简单，易于理解，容易实现，时间复杂度为O（n2），若带排序记录的数量很大时，一般不建议选用直接插入排序。从空间上看，它只需要一个记录的辅助空间，即空间复杂度为O（1）。直接插入排序方法是稳定的。

 

   二、交换排序

    交换排序的基本思想：比较两个记录键值的大小，如果这两个记录键值的大小出现逆序，则交换这两个记录，这样将键值较小的记录向序列前部移动，键值较大的记录向序列后部移动。

    交换排序又可分为冒泡排序和快速排序，由于本人对快速排序还不甚理解，先主要讲述冒泡排序。

   冒泡排序法：其过程是首先将第一个记录的键值和第二个记录的键值进行比较，若为逆序（即R[1].key>R[2].key），则将这两个记录交换，然后继续比较第二个和第三个记录。依次类推，直到完成第n-1个记录和第n个记录的键值比较交换位置。上述过程为第一趟起泡，其结果使键值最大的记录移到了第n个位置上。然后再进行第二趟起泡排序，即对前n-1个记录进行同样的操作，其结果是次大键值的记录安置在第n-1个位置上。重复以上过程，当在一趟起泡过程中没有进行记录交换操作时，整个排序过程终止。

    看着过程貌似很复杂，其实冒泡排序是非常简单的，下面以一个例子来解释：

 

               初始键值序列 45  38  66 90  88  10  25  45

 

               第一趟排序后 38  45  66 88  10  25 45 90

 

               第二趟排序后 38  45  66 10  25  45 88  90

 

               第三趟排序后 38  45  10 25  45 66  88  90

 

               第四趟排序后 38  10  25 45  45  66 88  90

 

               第五趟排序后 10  25  38  45 45  66 88  90

 

               第六趟排序后 10  25  38 45 45  66 88  90

 

               第七趟排序后 10  25  38 45 45  66 88  90（完成）

 

     从上例中可以看出，键值较小的记录好比气泡一样向上漂浮，键值较大的记录则向下沉，因为每趟都有一个最大键值的记录沉到水底，所以整个排序过程至多需要进行n-1趟起泡。

     冒泡排序的算法描述如下：

      

[csharp] 

Void BubbleSort(List R,int n)  

{  

int i,j,temp,endsort;  

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

{  

endsort=0;  

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

{  

if (R[j].key>R[j+1].key)  //若逆序则交换记录  

{  

temp=R[j];  

R[j]=R[j+1];  

R[j+1]=temp;  

endsort=1;  

}  

}  

if (endsort==0) break;  

}  

}  

 

    在算法实现时，定义一个整型变量endsort，在每一次排序之前，先将他设置为0，若在一趟起泡中交换了记录，则将他置位1。当一次循环结束时，我们再检查endsort，ruoendsort的值为0便终止算法。

    该算法的时间复杂度为O（n2），是一种稳定的排序方法。

 

    这里先介绍插入排序和交换排序，下一篇博客会详细介绍选择排序和归并排序，敬请期待！ 

补充：软件开发 , C# ,