数据结构之java排序javasort.pdf

《数据结构之java排序javasort.pdf》由会员分享，可在线阅读，更多相关《数据结构之java排序javasort.pdf（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数据结构排序思想和算法分析（数据结构排序思想和算法分析（javajava 版）版）一、排序的概念：一、排序的概念：1 1、设、设 n n 个记录的序列为个记录的序列为 R R1 1 , R , R2 2 , R , R3 3 , . . . , R , . . . , Rn n 其相应的关键字序列为其相应的关键字序列为 K K1 1 , K , K2 2 , K , K3 3 , . . . , K , . . . , Kn n 若规定若规定 1 , 2 , 3 , . . . , n 1 , 2 , 3 , . . . , n 的一个排列的一个排列 p p1 1 , p , p2 2 , p

2、 , p3 3 , . . . , p , . . . , pn n，使，使得相应的关键字满足如下非递减关系得相应的关键字满足如下非递减关系: :K Kp1p1 K Kp2p2 K Kp3p3 . . . K . . . Kpnpn则原序列变为一个按关键字有序的序列则原序列变为一个按关键字有序的序列: :R Rp1p1 , R , Rp2p2 , R , Rp3p3 , . . . , R , . . . , Rpnpn此操作过程称为排序。此操作过程称为排序。2 2、排序问题一般分为内排序内排序( ( internalinternal sortingsorting ) )和外排序外排序( (

3、externalexternal sortingsorting ) )两类：2.1. 内排序内排序：待排序的表中记录个数较少，整个排序过程中所有的记录都可以保留在内存中；按照排序过程中所依据的原则的不同可以分类为按照排序过程中所依据的原则的不同可以分类为: : 插入排序插入排序（直接插入排序、折半插入排序、希尔排序） 交换排序交换排序( (快速排序快速排序) ) （冒泡泡排序、快速排序） 选择排序选择排序（直接选择排序、堆排序） 归并排序归并排序 基数排序基数排序 二叉排序树排序二叉排序树排序2.2.外排序外排序：待排序的记录个数足够多，以至于他们必须存储在磁带、磁盘上组成外部文件，排序过程中

4、需要多次访问外存。3、排序的时间复杂性：排序过程主要是对记录的排序码进行比较和记录的移动过程。 因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量。 当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少， 则认为该方法的时间复杂性就越好，分析一种排序方法，不仅要分析它的时间复杂性，而且要分析它的空间复杂性、稳定性和简单性等。二、各种排序算法及代码详解：1 1、插入类排序、插入类排序-直接插入排序直接插入排序插入类排序算法思想：主要就是对于一个已经有序的序列中，插入一个新的记录，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序法。它包括：直接插入排序，折

5、半插入排序和希尔排序。1.1、 直接插入排序的基本思想是， 经过 i-1 遍处理后,L1.i-1己排好序。第 i 遍处理仅将 Li插入 L1.i-1的适当位置，使得 L1.i又是排好序的序列。 要达到这个目的， 直接插入排序用顺序比较的方法。 首先比较 Li和 Li-1，如果 Li-1 Li， 则 L1.i已排好序， 第 i 遍处理就结束了； 否则交换 Li与Li-1的位置， 继续比较Li-1和Li-2， 直到找到某一个位置j(1ji-1)，使得 Lj Lj+1时为止。算法描述1.2、一般来说，插入排序都采用 in-place 在数组上实现。具体算法描述如下：1. 从第一个元素开始，该元素可以

6、认为已经被排序，2. 取出下一个元素，在已经排序的元素序列中从后向前扫描，3. 如果该元素（已排序）大于新元素，将该元素移到下一位置，4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置，5. 将新元素插入到下一位置中，6. 重复步骤 2；如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一种，称为二分查找排序。1.3、算法代码实现：publicpublic classclass DirectInserSort publicpublic staticstatic voidvoid main(String args) intint

7、count1 = 0, count2 = 0;/ 复制次数，比较次数longlong begin = System.currentTimeMillis();System.out.println(插入前时间为： + begin);/ TODOTODO Auto-generated method stubintint data = 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 ;intint temp, j;forfor (intint i = 1; i = 0 & dataj temp) dataj + 1 = dataj; j-; count1+; dataj + 1 =

8、 temp; count2+; longlong end = System.currentTimeMillis(); System. out.println(插入后时间为： + end); System.out.println(插入法用时为： + (end - begin);/ 输出排序好的数据forfor (intint k = 0; k =end,则结束查找；否则，向下继续。3.若 data midx， 说明待查找的元素值只可能在比中项元素小的范围内，则把 mid-1 的值赋给 end，并重新计算 mid，转去执行步骤 2。2.3、算法代码实现：publicpublic classclas

9、s BinInsertSort /折半插入排序publicpublic staticstatic voidvoid main(String args) intint count1 = 0, count2 = 0;/ 复制次数，比较次数longlong begin = System.currentTimeMillis();System.out.println(插入前时间为： + begin);intint data = 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 ;/ 存放临时要插入的元素数据intint temp;intint low, mid, high;forfor

10、 (intint i = 1; i data.length; i+) temp = datai;/ 在待插入排序的序号之前进行折半插入 low = 0; high = i - 1;whilewhile (low = high) mid = (low + high) / 2;ifif (temp = low + 1; j-) dataj = dataj - 1; count1+; / low已经代表了要插入的位置了 datalow = temp; longlong end = System.currentTimeMillis(); System. out.println(插入后时间为： + en

11、d); System. out.println(插入法用时为： + (end - begin);forfor (intint k = 0; k aj，则交换它们的位置；Step3 当 dK = 1 的循环过程完成后，排序过程结束。3.3、算法代码实现：importimport java.util.Random;classclass ShellSortpublicpublic voidvoid sort(intint resource)intint h = 1;intint temp;whilewhile (h*3+1resource.length+1) h = h*3+1; whilewhil

12、e (h != 0)forfor(intint i=0; ih; i+)forfor (intint j=i; ji-h; k-=h)ifif (tempresourcek) resourcek+h = resourcek; elseelse breakbreak; resourcek+h = temp; h = (h-1)/3; publicpublic staticstatic voidvoid main(String args)ShellSort shell = newnew ShellSort(); Random random =newnew Random();intint test

13、= newnew intint10000;forfor (intint i=0; iai+1(i=1.n-1)则交换，得到一个最大元素放于 an；其次在n-1 个元素中，若aiai+1(i=1.n-2)则交换，这样得到的一个次大元素放于 an-1，以此类推，直到选出 n-1 个元素，排序完成。4.2、算法代码实现：publicpublic classclass BubbleSort publicpublic staticstatic voidvoid main(String args) intint vec = newnew intint 37, 46, 33, -5, 17, 51 ;int

14、int temp;longlong begin = System.currentTimeMillis();begin = System.currentTimeMillis();forfor (intint k = 0; k 1000000; k+) forfor (intint i = 0; i vec.length; i+) forfor (intint j = i; j vec.length - 1; j+) ifif (vecj + 1 vecj) temp = vecj + 1; vecj + 1 = vecj; vecj = temp; longlong end = System.c

15、urrentTimeMillis(); System.out.println(冒泡法用时为： + (end - begin);/打印排序好的结果forfor (intint i = 0; i vec.length; i+) System. out.println(veci); 4.3、算法讨论：冒泡排序算法稳定，O(1)的额外的空间，比较和交换的时间复杂度都是 O(n2)，自适应，对于已基本排序的算法，时间复杂度为 O(n)。冒泡算法的许多性质和插入算法相似，但对于系统开销高一点点。 使用冒泡排序法对 n 个数据进行排序， 共需要进行 n-1 次的比较。如果本来就是有顺序的数据，也需要进行n-

16、1 次比较。冒泡排序法的算法很简单，效率也较差。5 5、交换类排序、交换类排序- -快速排序快速排序5.1、快速排序（Quick Sorting）是对冒泡排序的一种改进。在冒泡排序中，记录的比较和交换是在相邻的单元中进行的， 记录每次交换只能上移或下移一个单元，因而总的比较和移动次数较多。而在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较小的记录一次就能从后面单元交换到前面去，而关键字较大的记录一次就能从前面的单元交换到后面的单元， 记录每次移动的记录较远，因此可以减少记录总的比较和移动次数。快速排序的基本做法是： 任取待排序的 n 个记录中的某个记录作为基准 （一般选取第一个记录

17、），通过一趟排序，将待排序记录分成左右两个字序列，左子序列记录的关键字均小于或等于该基准记录的关键字， 右子序列记录的关键字均大于或等于该基准记录的关键字，从而得到该记录最终排序的位置，然后该记录不再参加排序， 此一趟排序成为第一趟快速排序。然后对所分得左右子序列分别重复上述方法，直到所有的记录都处在他们的最终位置，此时排序完成。在快速排序中， 有时把待排序序列按照基准记录的关键字分为左右两个子序列的过程称为一次划分。5.2、快速排序的过程为：设待排序序列为 rs.t，为实现一次划分，可设置两个指针 low 和 high，他们的初值分别为 s 和 t。以 rs为基准，在划分的过程中：(1)从

18、high 端开始， 依次向前扫描， 并将扫描到的每一个记录的关键字同 rs （即基准记录） 的关键字进行比较， 直到 rhigh.keyrs.key 时， 将 rlow赋值到 high所指的位置。(3)如此交替改变扫描方向，重复上述两个步骤从两端各自向中间位置靠拢，直到low等于或大于high。 经过此次划分后得到的左右两个子序列分别为rs.low-1和 rlow+1.t。然后对这两个子序列按上述方法进行再次划分，依次重复，直到每个序列只剩一个元素为止。5.3 算法实现：publicpublic classclass QuickSort publicpublic voidvoid swap(i

19、ntint a, intint i, intint j) intint tmp = ai;ai = aj;aj = tmp;publicpublic intint partSort(intint a, intint low, intint high) intint pivot, p_pos, i;p_pos = low;pivot = ap_pos;forfor (i = low + 1; i pivot) p_pos+;swap(a, p_pos, i);swap(a, low, p_pos);returnreturn p_pos;publicpublic voidvoid quicksor

20、t(intint a, intint low, intint high) intint pivot;ifif (low high) pivot = partSort(a, low, high);quicksort(a, low, pivot - 1);quicksort(a, pivot + 1, high);publicpublic staticstatic voidvoid main(String args) / 快速排序法(Quick Sort)intint vec = newnew intint 37, 46, 33, -5, 17, 51 ;QuickSort s = newnew

21、QuickSort();longlong begin = System.currentTimeMillis();forfor (intint k = 0; k 1000000; k+) s.quicksort(vec, 0, 5);longlong end = System.currentTimeMillis();System.out.println(快速法用时为： + (end - begin);/ 打印排序好的结果forfor (intint i = 0; i vec.length; i+) System.out.println(veci);5.4 算法讨论：在快速排序中，若把每次划分所用

22、的基准记录看作根节点，把划分得到的左子序列和右子序列分别看成根节点的左、右子树，那么整个排序过程就对应着一颗具有 n 个节点的二叉排序树， 所需划分的层数等于二叉树的深度，所需划分的所有子序列数等于二叉树分枝结点数，而在快速排序中，记录的移动次数通常小于记录的比较次数。因此，讨论快速排序的时间复杂度时，仅考虑记录的比较次数即可。若快速排序出现最好的情况（左、右子序列的长度大致相等），则结点数n 与二叉树深度 h 应满足 log2(n)=h=log2(n+1)， 所以总的比较次数不会超过 （n+1）log2(n).因此，快速排序的最好时间复杂度应为O（nlog2(n)）。若快速排序出现最坏的情况

23、（每次能划分成两个子序列，但是其中一个为空），则此时得到的二叉树是一棵单枝树，得到的非空子序列包含有n-i（i 代表二叉树的层数），每层划分需要比较 n-i+2 次，所以总的比较次数为（ n2+3n-4）/2.因此，快速排序的最坏时间复杂度为 O(n2).快速排序所占用的辅助空间为递归时所需栈的深度， 故空间复杂度为 O （log2(n)） 。同时，快速排序是不稳定的排序。 6 6、选择类排序、选择类排序- -简单选择排序简单选择排序6.1、选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。如

24、对于一组关键字K1,K2,Kn，首先从 K1,K2,Kn 中选择最小值，假如它是 Kz， 则将 Kz 与 K1 对换； 然后从 K2， K3， ， Kn 中选择最小值 Kz，再将 Kz 与 K2 对换。如此进行选择和调换 n-2 趟，第(n-1)趟，从 Kn-1、Kn 中选择最小值 Kz 将 Kz 与 Kn-1 对换，最后剩下的就是该序列中的最大值，一个由小到大的有序序列就这样形成。6.2、n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果：初始状态：无序区为 R1.n，有序区为空。第 1 趟排序在无序区 R1.n中选出关键字最小的记录 Rk，将它与无序区的第 1 个记录

25、 R1交换，使 R1.1和 R2.n分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。第 i 趟排序第 i 趟排序开始时，当前有序区和无序区分别为 R1.i-1和 R(1in-1)。该趟排序从当前无序区中选出关键字最小的记录 Rk，将它与无序区的第 1 个记录 R 交换，使 R1.i和 R 分别变为记录个数增加 1 个的新有序区和记录个数减少 1 个的新无序区。这样，n 个记录的文件的直接选择排序可经过 n-1 趟直接选择排序得到有序结果。6.3、算法具体实现：publicpublic classclass SelectSort publicpublic staticst

26、atic voidvoid main(String args) intint vec = newnew intint 37, 46, 33, -5, 17, 51 ;intint temp;/选择排序法(Selection Sort)longlong begin = System.currentTimeMillis();forfor (intint k = 0; k 1000000; k+) forfor (intint i = 0; i vec.length; i+) forfor (intint j = i; j veci) temp = veci; veci = vecj; vecj =

27、 temp; longlong end = System.currentTimeMillis(); System.out.println(选择法用时为： + (end - begin);/打印排序好的结果forfor (intint i = 0; i =Key2i+1&key=key2i+2称为大顶堆，满足 Keyi=key2i+1&Keyi=key2i+2称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的， 小顶堆的堆顶的关键字是所有关键字中最小的。例：例：7.2、用大根堆排序的基本思想 先将初始文件 R1.n建成一个大根堆，此堆为初始的无序区； 再将关键字最大的记录 R

28、1（即堆顶）和无序区的最后一个记录Rn交换，由此得到新的无序区 R1.n-1和有序区 Rn，且满足 R1.n-1.keysRn.key；由于交换后新的根 R1可能违反堆性质，故应将当前无序区R1.n-1调整为堆。然后再次将 R1.n-1中关键字最大的记录R1和该区间的最后一个记录Rn-1交换，由此得到新的无序区 R1.n-2和有序区 Rn-1.n，且仍满足关系 R1.n-2.keysRn-1.n.keys，同样要将 R1.n-2调整为堆。直到无序区只有一个元素为止。（2）大根堆排序算法的基本操作： 初始化操作：将 R1.n构造为初始堆； 每一趟排序的基本操作： 将当前无序区的堆顶记录R1和该区

29、间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。7.3、基本排序过程：1. 1.将序列构造成一棵完全二叉树将序列构造成一棵完全二叉树 ；2. 2.把这棵普通的完全二叉树改造成堆，便可获取最小值把这棵普通的完全二叉树改造成堆，便可获取最小值 ；3. 3.输出最小值或者最大值；输出最小值或者最大值；4. 4.删除根结点，继续改造剩余树成堆，便可获取次小值删除根结点，继续改造剩余树成堆，便可获取次小值 ；5. 5.输出次小值输出次小值 ；6. 6.重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得重复改造，输出次次小值、次次次小值，直至所有结点均输出，便得到一个排序到一个排序

30、 。7.47.4、算法基本实现、算法基本实现（看了很多人写的算法，本人觉得这种算法蛮好）（看了很多人写的算法，本人觉得这种算法蛮好） ：publicpublic classclass HeapSort publicpublic staticstatic intint heap_size;/ 左孩子编号publicpublic staticstatic intint leftChild(intint i) returnreturn 2 * i+1; / 右孩子编号publicpublic staticstatic intint rightChild(intint i) returnreturn

31、2 * i + 2; /* * 保持最大堆的性质 * 堆中的数组元素 * 对以该元素为根元素的堆进行调整，假设前提：左右子树都是最大堆 * 由于左右孩子都是最大堆，首先比较根元素与左右孩子，找出最大值，假如大于根元素，则调整两个元素的值； * 由于左孩子 （右孩子） 的值与根元素交换， 有可能打破左子树 （右子树）的最大堆性质，因此继续调用，直至叶子元素。 */publicpublic staticstatic voidvoid max_heapify(intint a, intint i) intint left = leftChild(i);intint right = rightChil

32、d(i);intint largest = 0;ifif (left heap_size & ai aleft) largest = left; elseelse largest = i; ifif (right alargest) largest = right; ifif (largest = i) returnreturn; elseelse intint temp = ai; ai = alargest; alargest = temp;max_heapify(a, largest); /* * 建立最大堆。在数据中，下标a.length/2+1一直到最后的元素a.length-1都是

33、叶子元素 * 因此从其前一个元素开始，一直到 * 第一个元素，重复调用max_heapify函数，使其保持最大堆的性质 */publicpublic staticstatic voidvoid build_max_heap(intint a) /从0a.length/2中建立最大堆forfor (intint i = a.length / 2; i = 0; i-) max_heapify(a, i); /* * 堆排序：首先建立最大堆，然后将堆顶元素（最大值）与最后一个值交换，同时使得 堆的长度减小1 * 调用保持最大堆性质的算法调整，使得堆顶元素成为最大值，此时最后一个元素已被排除在外、

34、*/publicpublic staticstatic voidvoid heapSort(intint a) /构建最大堆build_max_heap(a);forfor (intint i = a.length - 1; i = 0; i-) /将第一个元素和最后一个元素进行互换intint temp = a0; a0 = ai; ai = temp;heap_size-;/调整堆为最大堆max_heapify(a, 0); publicpublic staticstatic voidvoid main(String args) intint a = 5, 4, 1, 3, 2, 16,

35、9, 10, 14, 8, 7;longlong begin = System.currentTimeMillis();forfor (intint k = 0; k 1000000; k+) heap_size = a.length;/最大数heapSort(a);/输出结果 longlong end = System.currentTimeMillis(); System.out.println(选择法用时为： + (end - begin);forfor (intint i = 0; i a.length; i+) System. out.print(ai + ); 7.5、算法讨论：从

36、上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。 只不过直接选择排序中， 为了从R1.n中选择最大记录， 需比较n-1次， 然后从R1.n-2中选择最大记录需比较 n-2 次。 事实上这 n-2 次比较中有很多已经在前面的n-1 次比较中已经做过， 而树形选择排序恰好利用树形的特点保存了部分前面的比较结果， 因此可以减少比较次数。对于 n 个关键字序列，最坏情况下每个节点需比较log2(n)次，因此其最坏情况下时间复杂度为 nlogn。堆排序为不稳定排序，不适合记录较少的排序。8 8、 二路归并排序二路归并排序8.1、归并排序归并排序（Merge）是将两个（或两个以上）有序表合并

37、成一个新的有序表，即把待排序序列分为若干个子序列， 每个子序列是有序的。 然后再把有序子序列合并为整体有序序列。归并-合并两个有序的序列假设有两个已排序好的序列A（长度为 n1） ，B（长度为 n2） ，将它们合并为一个有序的序列C（长度为 n=n1+n2)方法很简单：把A，B 两个序列的最小元素进行比较，把其中较小的元素作为C 的第一个元素；在 A，B 剩余的元素中继续挑最小的元素进行比较，确定 C 的第二个元素，依次类推，就可以完成对 A 和 B 的归并， 其复杂度为 O(n)。例如：A:138911B:2571013C:12357891011138.2、归并排序：1、递归基础：若序列只有

38、一个元素，则它是有序的，不执行任何操作2、递归步骤：先把序列划分成长度基本相等的两个序列对每个子序列递归排序把排好序的子序列归并成最后的结果例如：初始序列：8，4，5，6，2，1，7，3分解：8，4，5，62，1，7，3分解：8，45，62，17，3分解：84562173归并：4，85，61，23，7归并：4，5，6， 81，2，3，7归并：1，2，3， 4，5，6，7，88.3、算法具体实现：import java.util.Arrays;/二路归并排序主要分为/分割和合并public class MergeSort public static void main(String args)

39、int data = 2, 6, 10, 3, 9, 80, 1, 16, 27, 20 ; mergeSort(data,0,data.length-1); /直接打印 System.out.println(Arrays.toString(data); /二路归并的分割处理 public static void mergeSort(int array,int start,int end) if(startend) /划分为两部分，每次两部分进行归并 int mid=(start+end)/2; /两路归并 /先递归处理每一个部分 mergeSort(array,start,mid); mer

40、geSort(array,mid+1,end); /然后将已经排序好的，两两归并排序再进行合并处理 merge(array,start,mid,mid+1,end); 文档由小强收集，如果喜欢电影可以关注 pplive 网络电视官方下载 http:/ /二路归并两个部分的时候进行排序 public static void merge(intarray,int start1,int end1,int start2,int end2) int i=start1;/左路起始索引 int j=start2;/右路起始索引 int k=0; /归并的时候，会将两个数组数据按照大小输入到一个临时数组中 /

41、建立临时长度为两个子列表长度的数组 int temp=new intend2-start1+1; /循环遍历，按顺序找出两个表中的最小数据依次放入临时表中 /注意此时左路和右路已经是有序的了。 /当一路有一个小的，则会索引加1，继续喝另外一路的上次索引进行比较 while(i=end1&jarrayj) tempk+=arrayj+; else tempk+=arrayi+; /把剩下的元素放入临时数组中，只有一路的 while(i=end1) tempk+=arrayi+; while(j=end2) tempk+=arrayj+; k=start1; for(int item:temp)

42、arrayk+=item; 84、算法分析：归并排序先分解要排序的序列，从1 分成 2，2 分成 4，依次分解，当分解到只有 1 个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。 合并排序比堆排序稍微快一点， 但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。尽管归并排序最坏情况的比较次数比快速排序少，但它需要更多的元素移动，因此，它在实用中不一定比快速排序快9 9、 基数排序基数排序9.1 基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。最典型是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。最典型的应该就是扑克牌问题

43、。的应该就是扑克牌问题。基数排序就是借助于“分配基数排序就是借助于“分配” ”和和“ “收集收集” ”两种操作实现对单逻辑关键字的排序。两种操作实现对单逻辑关键字的排序。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。首先，单逻辑关键字通常都可以看作是由若干关键字复合而成。例，例，若关键字是数值，若关键字是数值，且值域为且值域为0K9990K999 ，故可以将故可以将 K K 看作是由看作是由 3 3 个关个关键字键字 K K0 0 K K1 1 K K2 2组成；组成；例，例，603603 是由是由6 60 03 3组成。组成。其次，利用其次，利用 LSDFLSDF 法实现对若干关键

44、字的排序。法实现对若干关键字的排序。例，序列例，序列278278109109063063930930589589184184505505269269008008083083各种排序算法的总结和比较各种排序算法的总结和比较排序方法 平均时间最坏时间辅助存储简单排序 O()O()O(1)快速排序 O(nlogn)O()O(logn)堆排序O(nlogn)O(nlogn)O(1)归并排序O(nlogn)O(nlogn)O(n)另外:直接插入排序、冒泡排序为简单排序，希尔排序（不稳定）一、时间性能按平均的时间性能来分，有三类排序方法：时间复杂度为 O(nlogn)的方法有：快速排序、堆排序和归并排序，

45、其中以快速排序为最好；时间复杂度为 O(n2)的有：直接插入排序、起泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此；当待排记录序列按关键字顺序有序时，直接插入排序和起泡排序能达到O(n)的时间复杂度;而对于快速排序而言，这是最不好的情况，此时的时间性能蜕化为O(n2)，因此是应该尽量避免的情况。简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。二、空间性能指的是排序过程中所需的辅助空间大小。1. 所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为 O(1)；2. 快速排序为 O(logn)，为栈所需的辅

46、助空间;3. 归并排序所需辅助空间最多，其空间复杂度为O(n);三、排序方法的稳定性能1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2. 当对多关键字的记录序列进行LSD 方法排序时，必须采用稳定的排序方法。3. 对于不稳定的排序方法，只要能举出一个实例说明即可。4. 希尔排序、快速排序和堆排序是不稳定的排序方法四、应用归并排序很难用于主存排序， 主要问题在于：合并两个排序的表需要线性附加内存， 在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样一些附加的工作， 其结果严重放慢了排序的速度。对于重要的内部排序应用而言，应选

47、择快速排序。快排和归并排序都是分治的递归算法。对于很小的数组（N=20） ，快速排序不如插入排序好。1 快速排序（QuickSort）快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。（1） 如果不多于 1 个数据，直接返回。（2） 一般选择序列最左边的值作为支点数据。（3） 将序列分成 2 部分，一部分都大于支点数据，另外一部分都小于支点数据。（4） 对两边利用递归排序数列。快速排序比大部分排序算法都要快。 尽管我们可以在某些特殊的情况下写出比快速排序快的算法， 但是就通常情况而言， 没有比它更快的了。 快速排序是递归的，对

48、于内存非常有限的机器来说，它不是一个好的选择。2 归并排序（MergeSort）归并排序先分解要排序的序列，从 1 分成 2，2 分成 4，依次分解，当分解到只有 1 个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。3 堆排序（HeapSort）堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。 这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢

49、出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。4 Shell 排序（ShellSort）Shell 排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是 O(nlogn)。其中分组的合理性会对算法产生重要的影响。 现在多用 D.E.Knuth 的分组方法。Shell 排序比冒泡排序快5 倍，比插入排序大致快2 倍。Shell 排序比起QuickSort，MergeSort，HeapSort 慢很多。但是它相对比较简

50、单，它适合于数据量在 5000 以下并且速度并不是特别重要的场合。 它对于数据量较小的数列重复排序是非常好的。5 插入排序（InsertSort）插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。 它比冒泡排序快2倍。 一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过 200 数据项的序列。6 冒泡排序（BubbleSort）冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n2)的算法。7 交换排序（ExchangeSort）和选择排序（