数据结构之内外排序
一、内排序
排序类别 | 排序方法 | 最好时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 辅助空间 | 稳定性 | 备注 |
|---|---|---|---|---|---|---|---|
插入类 | 插入 | O(n) | O(n2) | O(n2) | O(1) | 稳定 | 大部分已排序时较好 |
希尔排序 | - | O(ns)，1<s<2 | - | O(1) | 不稳定 | s是所选分组 | |
交换类 | 冒泡排序 | O(n) | O(n2) | O(n2) | O(1) | 稳定 | n小时较好 |
快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn) | 不稳定 | n大时较好 | |
选择类 | 选择 | O(n2) | O(n2) | O(n2) | O(1) | 不稳定 | n小时较好 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | n大时较好 | |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | n大时较好 | |
基数排序 | O(d(n+rd)) | O(d(n+rd)) | O(d(n+rd)) | O(rd) | 稳定 | 见下文 |
1．插入排序（InsertSort）
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。这样，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
void insertSort(int a[],int n) //插入排序
{
int i,j;
int t;
for(i=1;i<n;i++)
{
t=a[i]; //保存当前无序表中的第一个数据
j=i-1;
while(j>=0 && a[j]>t)
{
a[j+1]=a[j];
j--;
}
a[j+1]=t; //将数据插入有序表中
}
} 2．希尔排序（ShellSor）
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
Shell排序的分组合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
void shellSort(int a[],int n) //希尔排序
{
int i,j,gap;
int t;
for(gap=n/2;gap>0;gap/=2)
for(i=gap;i<n;i++)
{
t=a[i];
j=i-gap;
while(j>=0 &&a[j]>t)
{
a[j+gap]=a[j];
j-=gap;
}
a[j+gap]=t;
}
} 3．冒泡排序（BubbleSort）
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，就不会再把它们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
冒泡排序是最慢的排序算法，在实际运用中它是效率最低的算法。
void bubbleSort(int a[],int n) //冒泡排序
{
int i,j;
int t;
for(i=0;i<n;i++)
for(j=0;j<n-i-1;j++)
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
} 4．快速排序（QuickSort）
快速排序有两个方向，左边的i下标一直往右走，当a[i]<= a[center_inde]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j]> a[center_index]。如果i和j都走不动了，i<= j, 和a[j],重复上面的过程，直到i>j。交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为{5，3，3，4，3，8，9，10，11}，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。
快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。 ⑴如果不多于1个数据，直接返回。 ⑵一般选择序列最左边的值作为支点数据。 ⑶将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。 ⑷对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
void quickSort(int a[],int s,int e) //对a[s]至a[e]的元素进行快速排序
{
int i=s,j=e;
int t;
if(s<e)
{
t=a[s];
while(i!=j)
{
while(j>i && a[j]>t) j--; //从右向左扫描，找第一个小于t的a[j]
if(i<j) //表示找到这样的a[j]
{
a[i]=a[j];
i++;
}
while(i<j && a[i]<=t) i++; //从左向右扫描，找第一个大于t的a[i]
if(i<j) //表示找到这样的a[i]
{
a[j]=a[i];
j--;
}
}
a[i]=t; //将a[s]放到a[s]至a[e]的恰当位置i处，使得其左边的元素都不大于它，其右边的元素都不小于它。
quickSort(a,s,i-1); //对左区间递归排序
quickSort(a,i+1,e); //对右区间递归排序
}
} 5．选择排序（SelectSort）
选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。例如，序列{5，8，5，2，9}，第一趟选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
void selectSort1(int a[],int n) //选择排序
{
int i,j;
int t;
for(i=0;i<n-1;i++) //数据起始位置，从0到倒数第二个数据
for(j=i+1;j<n;j++) ////在剩下的数据中循环
{
if(a[i]>a[j]) // //如果有比它小的，交换两者
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
void selectSort2(int a[],int n) //选择排序的改进，减少了交换的次数
{
int i,j,small;
int t;
for(i=0;i<n-1;i++) //数据起始位置，从0到倒数第二个数据
{
small=i; //记录最小数据的下标
for(j=i+1;j<n;j++) //在剩下的数据中寻找最小数据
{
if(a[j]<a[small]) //如果有比它更小的，记录下标
small=j;
}
t=a[small]; //将最小数据和未排序的第一个数据交换
a[small]=a[i];
a[i]=t;
}
} 6．堆排序（HeapSort）
堆的结构是结点i的孩子为2i和2i+1节点，大顶堆要求父结点大于等于其2个子结点，小顶堆要求父结点小于等于其2个子结点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子结点共3个值选择最大（大顶堆）或者最小（小顶堆），这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1,n/2-2, ...1这些个父结点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父结点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法。
堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，由于快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
void max_heapify(int a[], int start, int end) //调整为大顶堆
{
//父结点和子结点下标
int dad = start, son = start * 2 + 1;
while(son <= end) //子结点下标在数组范围内才能比较
{
//先比较左右孩子的大小，选择大孩子的下标
if(son+1 <= end && a[son+1] > a[son]) son++;
if(a[son] > a[dad])
{
int t = a[son];
a[son] = a[dad];
a[dad] = t;
dad = son;
son = dad * 2 + 1;
}
else
break;
}
}
void heapSort(int a[], int n) //堆排序
{
int i;
//初始化数组为大顶堆，i=n/2-1表示最后一个父结点的下标
for(i=n/2-1; i>=0; i--) max_heapify(a, i, n-1);
for(i=n-1; i>0; i--) //根作为最大值调整到当前序列的最后
{
int t = a[0];
a[0] = a[i];
a[i] = t;
max_heapify(a, 0, i-1);
}
} 7．归并排序（MergeSort）
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换）,然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
归并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
void mergearray(int a[], int first, int mid, int last, int temp[]) //将有二个有序数列a[first...mid]和a[mid+1...last]合并。
{
int i=first, j=mid+1;
int m=mid, n=last;
int k=0;
while (i<=m && j<=n)
{
if (a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while (i<=m)
temp[k++]=a[i++];
while (j<=n)
temp[k++]=a[j++];
for (i=0;i<k;i++)
a[first+i]=temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
if (first<last)
{
int mid=(first+last)/2;
mergesort(a, first, mid, temp); //左边有序
mergesort(a, mid+1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
void MergeSort(int a[], int n)
{
int *p=(int *)malloc(n*sizeof(int));
mergesort(a, 0, n - 1, p);
free(p);
} 8．基数排序（RadixSort）
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。
时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。
int maxbit(int a[],int n) //求数组元素的最大位数
{
int d=1,i=0; //保存最大的位数
int p=10;
for(i=0;i<n;i++)
{
while(a[i]>=p)
{
p*=10;
d++;
}
}
return d;
}
void radixsort(int a[],int n) //基数排序
{
int d = maxbit(a,n);
long *tmp=(long *)malloc(n*sizeof(long));
long count[10]; //计数器,统计每位基数的个数
long i,j,k;
int radix=1;
for(i=1;i<=d;i++) //进行d次排序
{
for(j=0;j<10;j++) //每次分配前清空计数器
count[j]=0;
for(j=0;j<n;j++) //统计基数出现的次数
{
k=(a[j]/radix)%10;
count[k]++;
}
for(j=1;j<10;j++) //将tmp中的位置依次分配给每个计数器
count[j]=count[j-1]+count[j];
for(j=n-1;j>=0;j--) //根据计数器，将记录依次收集到tmp中
{
k=(a[j]/radix)%10;
count[k]--;
tmp[count[k]]=a[j];
}
for(j=0;j<n;j++) //将临时数组的内容复制到数组a中
a[j] = tmp[j];
radix = radix*10;
}
free(tmp);
} 二、外排序
当待排序的文件比内存的可使用容量还大时，文件无法一次性放到内存中进行排序，需要借助于外部存储器（例如硬盘、U盘、光盘），这时就需要用外部排序算法来解决。
外部排序算法由两个阶段构成： 按照内存大小，将大文件分成若干长度为 l 的子文件（l 应小于内存的可使用容量），然后将各个子文件依次读入内存，使用适当的内部排序算法对其进行排序（排好序的子文件统称为“归并段”或者“顺段”），将排好序的归并段重新写入外存，为下一个子文件排序腾出内存空间； 对得到的顺段进行合并，直至得到整个有序的文件为止。
例如，有一个含有 10000 个记录的文件，但是内存的可使用容量仅为 1000 个记录，毫无疑问需要使用外部排序算法，具体分为两步： 1. 将整个文件其等分为 10 个临时文件（每个文件中含有 1000 个记录），然后将这 10 个文件依次进入内存，采取适当的内存排序算法对其中的记录进行排序，将得到的有序文件（初始归并段）移至外存。 2. 对得到的 10 个初始归并段进行如图所示的两路归并，直至得到一个完整的有序文件。
有 10 个初始归并段到一个有序文件，共进行了 4 次归并，每次都由 m 个归并段得到 ⌈m/2⌉ 个归并段，这种归并方式被称为 2-路平衡归并。
对于外部排序算法来说，影响整体排序效率的因素主要取决于读写外存的次数，即访问外存的次数越多，算法花费的时间就越多，效率就越低。
对于同一个文件来说，对其进行外部排序时访问外存的次数同归并的次数成正比，即归并操作的次数越多，访问外存的次数就越多。使用2-路平衡归并的方式，举一反三，还可以使用 3-路归并、4-路归并甚至是 10-路归并的方式，下图为 5-路归并的方式： 对于 k-路平衡归并中 k 值得选择，增加 k 可以减少归并的次数，从而减少外存读写的次数，最终达到提高算法效率的目的。除此之外，一般情况下对于具有 m 个初始归并段进行 k-路平衡归并时，归并的次数为：s=」logkm」（其中 s 表示归并次数）。
从公式上可以判断出，想要达到减少归并次数从而提高算法效率的目的，可以从两个角度实现： 1. 增加 k-路平衡归并中的 k 值； 2. 尽量减少初始归并段的数量 m，即增加每个归并段的容量。