论文部分内容阅读
【摘要】排序的功能是将一组“无序”的记录序列按照一定的方法调整成为“有序”的序列，这是计算机内进行的一种常见操作，也是一种重要的操作。若是按照在排序中涉及的存储器的不同，来对排序进行划分，可以分内部排序和外部排序。本文是就常见的几种内部排序的方法进行分析与比较。
【关键词】时间复杂度；关键字
排序（sorting）又称分类，是计算机程序设计中的一个重要操作，即把一批任意序列的数据元素（或记录），重新排列成一个按关键字有序的序列。通过排序可以提高数据表的直观性，并为以后查询提供方便，提高查找效率。
排序（sorting）又称分类，是计算机程序设计中的一个极其重要的操作，应用极其广泛，如电话簿、病历、档案等等。排序就是把任意序列的数据元素，重新排列成一个按某种关键字形成有序的序列。排序之后可以提高数据表的直观性，方便查询，并提高查找效率。
一、插入排序
1、直接插入排序
直接插入排序（straight insertion sort）是一种最简单的排序方式。这种排序的操作就是将一个记录或数据元素插入到一个长度为n的有序表中，使表仍保持有序，会得到一个新的长度为n+1的有序表。
算法思路：设有一组关键字{k1，k2，…，kn}；在这里k1是一个有序的序列；让k2插入这个只有1个记录的的序列中，使之成为一个有2个记录的有序序列；以此类推，最后让kn插入到表长为n-1的有序序列中，得到一个表长为n的有序序列。
2、折半插入排序
当用直接插入排序进行到某一趟比较时，对于r[i].key来讲，前边i-1个记录已经按关键字排序。此时可不用直接插入排序的方法，而改用折半插入排序。
算法思路：与直接插入排序相近，只是在进行比较时，r[i].key首先与已排好序的中间记录进行比较，然后根据比较结果来确定r[i].Key继续与中间记录的前面记录比较，还是与中间记录的后面记录比较，找出应插入的位置，然后插入。
3、希尔排序
希尔排序（Shell sort）也称缩小增量排序。它的做法是要先将整个的记录序列划分成为若干个子序列，再分别进行直接插入的排序方式，等到整个序列中的记录基本上成为有序表的时候，对全体记录最后进行一次直接插入排序。这样做就减少了记录的移动次数和频率，也提高了排序效率。
算法思路：首先取一个正整数设为d1（d1=1），所有记录最终成为一个组。
二、交换排序
1、冒泡排序
冒泡排序（bubble sort）是一种人们熟悉的、最直观的交换排序方法。在排序过程中，从上到下对每两个相邻记录比较关键字大小，使较小关键字的记录往上升，象水中的汽泡向上冒出一样，而关键字较大的记录好比石头沉到序列的底部，故称此方法为冒泡排序法。
算法思路：假设有n个记录需要进行排序，要先将第一个记录和第二个记录的关键字进行比较，若r[2].key 2、快速排序
快速排序（Quick Sort）是由霍尔（Hoare）提出，它是一种对冒泡排序的改进。该方法的实质是将一组关键字[k1，k2，…，kn]分区时行交换排序。将等待排序的记录划分成独立的两个部分，一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续分区进行交换排序，形成有序序列。
算法思路：
（1）任选一个关键字（一般取第一记录k1）为控制关键字，将整个记录[k1，k2，…，kn]分成左、右两区，左区的关键字小于等于k1，右区关键字大于等于k1，最后k1居两个子区中间的适当位置。
（2）右区首、尾记录保存入栈，对左区进行第（1）步操作，重新得到左区和右区，控制关键字居中。
（3）重复第（1）、（2）步，一直到左区处理完毕，形成有序序列，退栈，再对另一个子区进行相同的操作，直到栈空，就形成完整的有序序列。
三、选择排序
1、简单选择排序
简单选择排序（Simple Selection Sort）也称直接选择排序。此方法在高级语言编程中较常用。它首先选出关键字最小的记录送到最前位置，再选关键字次小的记录送到第二个位置，…，直至选择完了n个记录为止。
算法思路：对于一组关键字（k1，k2，…，kn），将其由小到大进行排序，首先从序列中选择最小值，假如它是kk，则将kk与k1对换；然后从 k2，…，kn中选择最小值kk，再将kk与k2对换。如此进行选择和调换，对第i趟选择排序，进行n-i次关键字比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换。令i从1至n-1，进行n-1趟选择排序，一个由小到大的有序序列就形成。
2、堆排序
堆排序（Heap Sort）是利用堆的性质进行的一种选择排序。堆是n个元素的有限序列{k1，k2，…，kn}，当且仅当满足如下关系时，称之为堆。
ki≤k2i和ki≤k2i+1（i=1，2，…，n/2）或ki≤k2i和ki≤k2i+1（i=1，2，…，n/2）
前者称为小根堆，后者称为大根堆。
算法思路：
1）将初始待排序关键字序列（k1，k2，…，kn）构建成大顶堆，此堆为初始的无序区；
2）将堆顶元素k[1]与最后一个元素k[n]交换，此时得到新的无序区（ k1，k2，…，kn1）和新的有序区kn，且满足k[1，2...n-1]<=k[n]；
3）由于交换后新的堆顶k[1]可能违反堆的性质，因此需要对当前无序区（k1，k2，…，kn1）调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区（k1，k2，…，kn1）和新的有序区（kn1，kn）。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
四、各种排序方法的性能比较
这里介绍的几种排序方法，并没有哪一种排序方法是最好的，各有优缺点，应根据不同要求和情况进行选择，找到较合适的方法，当然也可以结合使用多种方法。
1、当待排序的记录数n不大时（约n<=50），可以使用直接插入排序、简单插入排序、冒泡排序。时间复杂度为0（n2），但方法简单，好理解，易实现。当原文件记录按关键字“基本有序”时，直接插入排序和冒泡排序两种方法速度比较快。
2、当n值很大，关键字元素比较随机，对稳定性没要求宜用快速排序。关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。它们排序速度非常快。但快速排序对原序列基本有序的情况，速度减慢接近0（n2），而堆排序不会出现最坏情况。
【关键词】时间复杂度；关键字
排序（sorting）又称分类，是计算机程序设计中的一个重要操作，即把一批任意序列的数据元素（或记录），重新排列成一个按关键字有序的序列。通过排序可以提高数据表的直观性，并为以后查询提供方便，提高查找效率。
排序（sorting）又称分类，是计算机程序设计中的一个极其重要的操作，应用极其广泛，如电话簿、病历、档案等等。排序就是把任意序列的数据元素，重新排列成一个按某种关键字形成有序的序列。排序之后可以提高数据表的直观性，方便查询，并提高查找效率。
一、插入排序
1、直接插入排序
直接插入排序（straight insertion sort）是一种最简单的排序方式。这种排序的操作就是将一个记录或数据元素插入到一个长度为n的有序表中，使表仍保持有序，会得到一个新的长度为n+1的有序表。
算法思路：设有一组关键字{k1，k2，…，kn}；在这里k1是一个有序的序列；让k2插入这个只有1个记录的的序列中，使之成为一个有2个记录的有序序列；以此类推，最后让kn插入到表长为n-1的有序序列中，得到一个表长为n的有序序列。
2、折半插入排序
当用直接插入排序进行到某一趟比较时，对于r[i].key来讲，前边i-1个记录已经按关键字排序。此时可不用直接插入排序的方法，而改用折半插入排序。
算法思路：与直接插入排序相近，只是在进行比较时，r[i].key首先与已排好序的中间记录进行比较，然后根据比较结果来确定r[i].Key继续与中间记录的前面记录比较，还是与中间记录的后面记录比较，找出应插入的位置，然后插入。
3、希尔排序
希尔排序（Shell sort）也称缩小增量排序。它的做法是要先将整个的记录序列划分成为若干个子序列，再分别进行直接插入的排序方式，等到整个序列中的记录基本上成为有序表的时候，对全体记录最后进行一次直接插入排序。这样做就减少了记录的移动次数和频率，也提高了排序效率。
算法思路：首先取一个正整数设为d1（d1
二、交换排序
1、冒泡排序
冒泡排序（bubble sort）是一种人们熟悉的、最直观的交换排序方法。在排序过程中，从上到下对每两个相邻记录比较关键字大小，使较小关键字的记录往上升，象水中的汽泡向上冒出一样，而关键字较大的记录好比石头沉到序列的底部，故称此方法为冒泡排序法。
算法思路：假设有n个记录需要进行排序，要先将第一个记录和第二个记录的关键字进行比较，若r[2].key
快速排序（Quick Sort）是由霍尔（Hoare）提出，它是一种对冒泡排序的改进。该方法的实质是将一组关键字[k1，k2，…，kn]分区时行交换排序。将等待排序的记录划分成独立的两个部分，一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录继续分区进行交换排序，形成有序序列。
算法思路：
（1）任选一个关键字（一般取第一记录k1）为控制关键字，将整个记录[k1，k2，…，kn]分成左、右两区，左区的关键字小于等于k1，右区关键字大于等于k1，最后k1居两个子区中间的适当位置。
（2）右区首、尾记录保存入栈，对左区进行第（1）步操作，重新得到左区和右区，控制关键字居中。
（3）重复第（1）、（2）步，一直到左区处理完毕，形成有序序列，退栈，再对另一个子区进行相同的操作，直到栈空，就形成完整的有序序列。
三、选择排序
1、简单选择排序
简单选择排序（Simple Selection Sort）也称直接选择排序。此方法在高级语言编程中较常用。它首先选出关键字最小的记录送到最前位置，再选关键字次小的记录送到第二个位置，…，直至选择完了n个记录为止。
算法思路：对于一组关键字（k1，k2，…，kn），将其由小到大进行排序，首先从序列中选择最小值，假如它是kk，则将kk与k1对换；然后从 k2，…，kn中选择最小值kk，再将kk与k2对换。如此进行选择和调换，对第i趟选择排序，进行n-i次关键字比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1≤i≤n）个记录交换。令i从1至n-1，进行n-1趟选择排序，一个由小到大的有序序列就形成。
2、堆排序
堆排序（Heap Sort）是利用堆的性质进行的一种选择排序。堆是n个元素的有限序列{k1，k2，…，kn}，当且仅当满足如下关系时，称之为堆。
ki≤k2i和ki≤k2i+1（i=1，2，…，n/2）或ki≤k2i和ki≤k2i+1（i=1，2，…，n/2）
前者称为小根堆，后者称为大根堆。
算法思路：
1）将初始待排序关键字序列（k1，k2，…，kn）构建成大顶堆，此堆为初始的无序区；
2）将堆顶元素k[1]与最后一个元素k[n]交换，此时得到新的无序区（ k1，k2，…，kn1）和新的有序区kn，且满足k[1，2...n-1]<=k[n]；
3）由于交换后新的堆顶k[1]可能违反堆的性质，因此需要对当前无序区（k1，k2，…，kn1）调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区（k1，k2，…，kn1）和新的有序区（kn1，kn）。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
四、各种排序方法的性能比较
这里介绍的几种排序方法，并没有哪一种排序方法是最好的，各有优缺点，应根据不同要求和情况进行选择，找到较合适的方法，当然也可以结合使用多种方法。
1、当待排序的记录数n不大时（约n<=50），可以使用直接插入排序、简单插入排序、冒泡排序。时间复杂度为0（n2），但方法简单，好理解，易实现。当原文件记录按关键字“基本有序”时，直接插入排序和冒泡排序两种方法速度比较快。
2、当n值很大，关键字元素比较随机，对稳定性没要求宜用快速排序。关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。它们排序速度非常快。但快速排序对原序列基本有序的情况，速度减慢接近0（n2），而堆排序不会出现最坏情况。