排序算法详解（一）

虽然现今越来越多的新技术涌现出来，但是基础还是最重要的，这里就和大家一起重温一下排序算法。

排序是什么？其是计算机程序设计当中的一个重要的操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。由于排序的记录数量不同，是的-排序过程当中所涉及的存储器不同，可将排序分为两大咧：内部排序和外部排序。内部排序指的是待排记录存放在计算机随机存储器中进行的排序过程；外部排序指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，再排序的过程中尚须对外存进行访问的排序过程。这里我们先主要先来看一下内部排序。

内部排序的结构请看这里，我们先来看一下插入排序。插入排序有直接插入排序、折半插入排序、2-路插入排序等等，但是其都是在直接插入排序的基础上改进而来。所以我们先来详细的看一下直接插入排序。

直接插入排序实际上就是将第i个数插入到已经有序的前i-1个元素当中，那么这i个元素也就成为有序的序列，如此往复循环，直至将整个序列变为有序的。，下面我们来看个例子：

                          L[0]     L[1]     L[2]     L[3]     L[4]     L[5]     L[6]     L[7]     L[8]      

初始关键字                (49)       38       65       97       76       13       27       49

i=2                    (38)    (38        49)     65       97       76       13       27       49

I=3                    (65)    (38        49      65)      97       76       13       27       49

I=4                    (97)    (38        49      65       97)      76       13       27       49

I=5                    (76)    (38        49      65       76      97)       13       27       49

I=6                    (13)    (13        38      49       65       76      97)       27       49
I=7                    (27)    (13        27      38       49       65        76      97)      49
I=8                    (49)    (13        27      38       49       49        65       76      97)      
上面就是一个直接插入排序的过程，每次比较完成后指针自加一次，然后指针指向的元素与前一个元素进行比较，如果比前一个元素小，那么存入L[0]中，然后前一个元素存入到指针指向的位置，然后L[0]和前面已经排好的序列从后向前进行比较，比较过的元素都向后移动，直到L[0]大于比较的数，将L[0]中的数插入到其后面的单元中。算法代码如下：

[cpp] 
#include<stdio.h> 
 
#define N 100 
int L[N]; 
 
void insertsort(int n) 
{ 
    int i,j; 
    for(i=2;i<=n;i++) 
    { 
        if(L[i]<L[i-1]) 
        { 
            L[0] = L[i]; 
            L[i] = L[i-1]; 
        } 
        for(j=i-2;L[j]>L[0];j--) 
            L[j+1] = L[j]; 
        L[j+1] = L[0]; 
    } 
    for(i=1;1<=n;i++) 
        printf("L[%d]=%d",i,L[i]); 
} 
 
int main() 
{ 
    int i,n; 
    scanf("%d",&n); 
    for(i=1;i<=n;i++) 
        scanf("%d",&L[i]); 
    insertsort(n); 
    return 0; 
} 
上面就是直接插入排序的一个例子，它的时间复杂度为O(n2)。直接插入排序是稳定的。
下面我们来看一下插入排序的另外一种：希尔排序。它又称作“缩小增量排序”，它较之直接插入排序，时间复杂度上有了较大的提高。其主要的算法思想是：先将整个序列分割成若干子序列进行直接插入排序，待整个序列中的记录基本有序后，再对全体记录进行一次直接插入排序，这样他的时间复杂度就有了较大的提高。下面我们将一个序列进行一次希尔排序，如下：

初始关键字                49       38       65       97       76       13       27       49       55       04
第一趟排序                49                                                      13

                                                38                                                      27

                                                           65                                                      49

                                                                       97                                                       55

                                                                                    76                                                      04

一趟排序结果           13         27      49        55        04       49       38       65       97       76           第一趟排序增量为5

第二趟排序               13                                55                                38                              76

                                                 27                               04                               65

                                                            49                                49                               97

二趟排序结果           13         04       49       38        27       49        55       65       97       76           第二趟排序增量为3       

第三趟排序               04         13       27       38        49       49        55       65       76       97           

下面我们来看运用希尔排序的一个小例子，更加有助于大家对于希尔排序的理解：

[cpp]
#include<stdio.h> 
 
#define N 100 
int L[N]; 
 
void ShellInsert(int n,int dk) 
{ 
    int i,j; 
    for(i=dk+1;i<=n;i++) 
    { 
        if(L[i]<L[i-dk]) 
            L[0] = L[i]; 
        for(j=i-dk;j>0&&L[0]<L[j];j=j-dk) 
            L[j+dk] = L[j]; 
        L[j] = L[0]; 
    } 
} 
 
void Shellsort(int n,int dlta[],int t) 
{ 
    int k,i; 
    for(k=0;k<t;k++) 
        ShellInsert(n,dlta[k]); 
    for(i=1;i<=n;i++) 
        printf("L[%d]=%d/n",i,L[i]); 
} 
 
int main() 
{ 
    int i,n,t,dlta[5]={5,3,1}; 
    scanf("%d",&n); 
    scanf("%d",&t); 
    for(i=1;i<=n;i++) 
        scanf("%d",&L[i]); 
    Shellsort(n,dlta,t); 
    return 0;    
} 
希尔排序的时间复杂度为O(n*ln n)。
由上面的算法可以看出，直接插入排序是稳定的排序算法，而希尔排序是不稳定的排序算法。

上面就是插入排序的一个大概的讲解，下面我们还将进行余下排序算法的讲解。