试设计一个算法，使得在O(n)的时间内重排数组，将所有取负值的排序码排在所有取正值(非负值)的排序码之前.

已知奇偶交换排序算法如下描述:第一趟对所有奇数的i,将a[i]和ali+1]进行比较,第二趟对所有5.已知奇偶交换排序算法如下描述:第一趟对所有奇数的i,将a[i]和ali+1]进行比较,第二趟对所有直至整个数组有序。 （1)试问排序结束的条件是什么？ （2)编写一个实现上述排序过程的算法。

计数排序方法。该方法在声明元素时为每个元素增加一个计数域count，用于存放在已排好序的序列中该元素前面的元素数日，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个元素的序列，为确定所有元素的count值，最多需要进行n(n-1)/2次排序码比较。

设待排序的排序码序列为（12，2，16，30，28，10，16，20，6，18)，试分别写出使用以下排序方法每趟排序后

的结果，并说明做了多少次排序码比较，注意，后一个16附带一个“*”表明这是一个与前面某一个元素具有相同排序码值(16)的元素。

(1)直接插入排序

(2)希尔排序(增量为5，2，1)

(3)起泡排序

(4)快速排序

(5)简单选择排序

(6)锦标赛排序

(7)堆排序

(8)二路归并排序

(9)基数排序

首先对较短的子序列进行排序，试编写相应的算法，并说明在此做法下，快速排序所需要的栈的深度为O(log₂n)，

将5个不同的数据进行排序，最少需要（①)次排序码比较，最多需要（②)次排序码比较。

数项i扫描，若A[i]≥Ali+1]，则交换它们。第三趟对所有的奇数项扫描，第四趟对所有的偶数项扫描，……，如此反复，直到整个序列全部排好序为止。

(1)这种排序方法结束的条件是什么？

(2)写出奇偶交换排序的算法。

(3)当待排序排序码序列的初始排列是从小到大有序，或从大到小有序时，在奇偶交换排序过程中的排序码比较次数是多少？

对n个具有不同排序码值的元素进行起泡排序，在（①)情况下排序码比较次数最小;在（②)情况下排序码比较次数最大。