排序算法详解（一）

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

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

内部排序的结构请看这里，我们先来看一下插入排序。插入排序有直接插入排序、折半插入排序、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]中的数插入到其后面的单元中。算法代码如下：

#include<stdio.h>#define N 100int 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;}

由上面的算法可以看出，直接插入排序是稳定的排序算法，而希尔排序是不稳定的排序算法。

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