数据结构的排序方法有哪些？
先回答：（1）C，（2）A，（3）D，(4)B，(5)G
(1) C．插入排序 法从未排序的序列中依次取出元素，与已排序序列(初始时为空)中的元素作比较，将其放入已排序序列的正确位置上；
(2) A．选择排序 法从未排序的序列中挑选元素， 并将其依次放入已排序序列(初始时为空)的一端；交换排序方法是对序列中的元素进行一系列比较， 当被比较的两元素逆序时，进行交换；
(3) D．起泡排序 和 （4）B．快速排序 是基于这类方法的两种排序方法；
(5) G．堆排序 法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。
原题应该是：
排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5分）】
（1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序
E．归并排序 F．shell排序 G．堆排序 H．基数排序
【解答】（1）C，（2）A，（3）D，(4)B，(5)G
2、选择排序（直接选择排序和堆排序）
3、交换排序（冒泡排序和快速排序）
4、归并排序
5、基数排序
直接插入排序：逐个将后一个数加到前面的排好的序中。在直接插入排序过程中，对其中一个记录的插入排序称为一次排序；直接插入排序是从第二个记录开始进行的，因此，长度为n的记录序列需要进行n-1次排序才能完成整个序列的排序。时间复杂度为O(n2)。
希尔排序：希尔排序又称缩小增量排序，增量di可以有各种不同的取法，但最后一次排序时的增量必须为1，最简单可取di+1=di/2（取小）。时间复杂度为O(n(log2n)2)。
直接选择排序
说明：每次将后面的最小的找出来插入前面的已排好的序中。同理，具有n个记录的序列要做n-1次排序。
时间复杂度为O(n2)。
冒泡排序：两个两个比较，将大的往后移。通过第一次冒泡排序，使得待排序的n个记录中关键字最大的记录排到了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列，共需进行n次冒泡排序。时间复杂度为O(n2)。
快速排序：又叫分区交换排序，是对冒泡排序方法的一种改进。时间复杂度为O(nlog2n)。
归并排序：将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。时间复杂度为O(nlog2n)。
冒泡排序，快速排序，堆排序。
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名“冒泡排序”。
快速排序（Quicksort）是对冒泡排序的一种改进。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
稳定的
冒泡排序（bubble sort） — O(n2)
鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 额外 记忆体
计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外 记忆体
归并排序 （merge sort）— O(n log n); 需要 O(n) 额外记忆体
原地归并排序 — O(n2)
二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 额外记忆体
鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 额外记忆体
基数排序 （radix sort）— O(n·k);
不稳定
选择排序 （selection sort）— O(n2)
希尔排序 （shell sort）— O(n log n)
堆排序 （heapsort）— O(n log n) Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n)
先回答：（1）C，（2）A，（3）D，(4)B，(5)G
(1) C．插入排序 法从未排序的序列中依次取出元素，与已排序序列(初始时为空)中的元素作比较，将其放入已排序序列的正确位置上；
(2) A．选择排序 法从未排序的序列中挑选元素， 并将其依次放入已排序序列(初始时为空)的一端；交换排序方法是对序列中的元素进行一系列比较， 当被比较的两元素逆序时，进行交换；
(3) D．起泡排序 和 （4）B．快速排序 是基于这类方法的两种排序方法；
(5) G．堆排序 法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。
原题应该是：
排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端； 交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法， 而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 【北方交通大学 1999 一、3 （5分）】
（1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序
E．归并排序 F．shell排序 G．堆排序 H．基数排序
【解答】（1）C，（2）A，（3）D，(4)B，(5)G
