排序的相关概念
排序的分类
根据在排序过程中带排序的记录是否全部被放置在内存中,排序分为:
1.内排序
内排序是在排序整个过程中,带排序的所有记录全部放置在内存中。
影响内排序的主要因素:
根据排序过程中借助的主要操作,内排序分为:
2.外排序
外排序是由于排序的记录个数太多,不能同时放置在内存中,整个排序过程需要在内外存之间多次交换数据才能进行。 按照算法的复杂度分类
冒泡排序算法
因为在冒泡排序中要用到顺序表结构和数组两元素的交换,先把这些写成函数
冒泡排序(Bubble Sort)是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止。
对于这段代码,是最简单的冒泡,其实就是最简单的交换排序而已。它的思路就是让每一个关键字,都和它后面的每一个关键字比较,如果大则交换,这样第一位置的关键字在第一次循环后一定变成最小值。
假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
i = 1
时,9与1交换后,在第一位置的1与后面的关键字比较都小,因此它就只最小值。i = 2
时,第二位置先后由9换成5,换成3,换成2,完成了第二小的数字交换。1.2 冒泡排序的实现
对于上面的算法,代码虽然简单易懂,但是效率非常低。可以改进成接下来的代码
代码解释
假设我们待排序的关键字序列是{9,1,5,8,3,7,4,6,2}
当i = 1
时,变量j由8反向循环到1,逐个比较,将较小值交换到前面,直到最后找到最小值放置在了第1的位置。
当i = 1
、 j = 8
时,6 > 2 ,因此交换了它们的位置,j = 7
时,4 > 2, 所以交换......直到j = 2
时,因为 1 < 2, 所以不交换。j = 1 时,9 > 1,交换,最终得到最小值1放置第一的位置。
在不断循环的过程中,除了将关键字1放到第一的位置,还将关键字2从第九位置提到了第三的位置,显然比前面的算法有进步。
当i = 2
时,变量j
由8反向循环到2,逐个比较,在将关键字2交换到第二位置的同时,也将关键字4和3有所提升。
#define N 9
int main(int argc, const char * argv[]) {
int i;
int d[N] = {9,1,5,8,3,7,4,6,2};
SqList l0;
for (i = 0; i < N; i++)
l0.r[i+1] = d[i];
l0.length = N;
printf("排序前:\n");
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.0 初级冒泡排序结果:\n");
BubblSort0(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.1 冒泡排序结果:\n");
BubbleSort(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
printf("1.2 优化后冒泡排序结果:\n");
BubbleSort1(&l0);
for (i = 0; i < l0.length; i++) {
printf("%d ", l0.r[i+1]);
}
printf("\n");
return 0;
}
简单选择排序
简单选择排序法(Simple Selection Sort)是通过n-i
次关键字间的比较,从n-i+1
个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换。
简单选择排序法的工作原理是:每一次从无序组的数据元素中选出最小(或最大)的一个元素,存放在无序组的起始位置,无序组元素减少,有序组元素增加,直到全部待排序的数据元素排完。
O(n^2)
。直接插入排序
直接插入排序(Straight Insertion Sort)的基本操作是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录增1的有序表。
直接插入排序的核心思想:将一个记录插入到一个已经排序好的表中,以得到一个记录增加1的有序表。并且它把当前元素大的记录都往后移动,用以腾出“自己”该插入的位置。当n-1趟插入完成后该记录就是有序序列。
O(n^2)
。希尔排序
希尔排序是对直接插入排序的改进:
dlta[k] = 2^(t-k+1) - 1
时,可以获得不错的效果。希尔排序的核心思想:希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。
O(n^(3/2))
,要好于直接插入排序的O(n^2);堆排法
堆是具有如下性质的完全二叉树:
堆排序(Heap Sort)是利用堆(假设是大顶堆)进行排序。 堆排序的核心思想:
n-1
个序列重新构造成一个堆,这样就会得到n个元素的次小值。HeapSort
中有两个for循环:第一个for循环完成将现在的待排序序列构建成一个大顶堆;第二个for循环完成逐渐将每个最大值的根节点与末尾元素交换,并且再调整其成为大顶堆。i = L->length / 2
,i
从[9/2]=4
开始,4->3->2->1的变化量。(这里赋值的原因是这些都是有孩子的结点)HeadAdjust
的作用是将数组构建成一个大顶堆,在构建的时候利用了二叉树的性质。O(n)
,重建堆的时间复杂度为O(nlogn)
,所以总体来说堆排序的时间复杂度为O(nlogn)
,性能上远好于冒泡、简单选择、直接插入的时间复杂度。归并排序
归并排序(Merging Sort)是利用归并的思想实现的。2路归并排序的核心思想如下:
n
个记录,则可以看成是n
个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2
个长度为2或者1的有序子序列n
的有序序列为止。归并排序的总结(递归实现)
O(nlogn)
,并且这是归并排序算法中最好、最坏、平均的时间性能。O(n+logn)
用迭代实现的话,可以从最小的序列开始归并直到完成。
log2n
的栈空间,空间只是用到申请归并临时用的TR
数组,因此空间复杂度为O(n)
.快速排序
快速排序(Quick Sort)的基本思想是:
Partition
函数就是将选取的pivotkey
不断交换,将比它小的换到它的左边,比它大的交换到它的右边,它也在交换中不断更改自己的位置,直到完全满足这个要求为止。O(nlogn)
。O(nlogn)
。快速排序的优化
pivotkey = L->r[low]
,即用序列的第一个元素作为枢轴,这是理想情况下 L->r[low]
是中间数。但是对于其他情况,这种固定选取第一个关键子作为首个枢轴的方法就不是很合理。于是可以用下面的方法优化:
三数取中(median-of-three)法:取三个关键子进行排序,将中间数作为枢轴,一般取左端、右端和中间三个数,也可以随机选取。
九数取中(median-of-nine)法:先从数组中分三次取样,每次取三个数,三个样品各取中数,然后从这三个数当中再取出一个中数作为枢轴。三数取中(median-of-three)法代码:
排序总结