请选择 进入手机版 | 继续访问电脑版
贠老师培训群:150322713    贠老师QQ:767708506

贠老师office培训-excel学习网

 找回密码
 立即注册
点击咨询贠老师
查看: 136|回复: 6

[C语言] C语言排序方法中,哪一种最快?

[复制链接]

3172

主题

3269

帖子

2万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
22691
发表于 2015-12-28 10:31:33 | 显示全部楼层 |阅读模式
首先,对大多数包含排序应用的程序来说,排序算法的速度并不重要,因为在程序中排序  的工作量并不是很多,或者,与排序相比,程序中其它操作所花费的时间要多得多。

实际上,没有哪一种排序算法永远是最快的,在运行程序的软硬件环境相同的情况下,不同排序算法的速度还与数据的长度、性质以及数据的初始顺序有关。

在笔者的“工具箱”中,有三种算法在不同的情况下都是最快、最有用的,这三种算法分别是快速排序、归并排序和基数排序。

快速排序
快速排序是一种分割处理式的排序算法,它将一个复杂的排序问题分解为若干较容易处理的排序问题,然后逐一解决。在快速排序算法中,首先要从数据集的数据中选择一个数据作为分割值,然后将数据分成以下3个子集:
    (1) 将大于分割值的数据移到分割值前面,组成子集1;
    (2) 分割值本身为子集2;   
    (3) 将小于分割值的数据移到分割值后面,组成子集3。
等于分割值的数据可以放在任意一个子集中,这对快速排序算法没有任何影响。由于子集2已经是有序的,所以此后只需对子集1和子集3进行快速排序。

需要注意的是,当数据集很小时,无法进行快速排序,而要使用其它排序算法。显然,当数据集中的数据只有两个或更少时,就不可能将数据集再分割成三个子集。实际上,当数据集比较小时,程序员就应该考虑是否仍然采用快速排序算法,因为在这种情况下另外一些排序算法往往更快。

例3. 2a用快速排序算法重写了例3.1中的字符串数组排序程序,你同样可以将它和本章末尾的有关代码一起编译成一个可执行程序。程序中定义了一个宏,它可使程序更易读,并能加快执行速度。

快速排序算法是由程序中的myQsort()函数实现的,它是按升序对一个字符串数组进行排序的。函数myQsort()的具体工作过程如下:
    (1)首先检查最简单的情况。在第17行,检查数组中是否没有或只有一个元素——在这种情况下,数组已经是有序的,函数就可以返回了。在第19行,检查数组中是否只有两个元素——在这种情况下,要么数组已经是按升序排列的,要么交换这两个元素的位置,使它们按升序排列。
    (2)在第28行至第53行,将数组分割为两个子集:第一个子集中的数据大于或等于分割值,第二个子集中的数据小于分割值。

在第28行,选择数组中间的元素作为分割值,并将其和数组中的第一个元素交换位置。在第37行至第39行,在数组中找到属于第二个子集的第一个元素;在第45行至第47行,在数组中找到属于第一个子集的最后一个元素。在第49行,检查属于第二个子集的第一个元素是否位于属于第一个子集的最后一个元素的后面,如果是,则第一个子集的所有元素都已在第二个子集的所有元素的前面,数据已经划分好了;否则,交换这两个元素的位置,然后重复上述这种检查。
    (3)当两个子集分割完毕后,在第55行,将分割值和第一个子集中的最后一个元素交换位置,排序结束时这个分割值将仍然排在现在这个位置。在第57行和第58行,分别调用myQsort()函数对分割所得的子集进行排序。当所有的子集都经过排序后,整个数组也就排好序了。

例3. 2a一个不使用qsort()函数的快速排序算法程序

1: #include <stdlib.h>
2:
3: #define exchange(A, B, T)  ((T) = (A), (A) = (B),(B)=(T))
4:                                       
5:
6: / * Sorts an array of strings using quick sort algorithm * /
7: static void myQsort(const char * array[], size_t num)
8: {
9:     const char * temp
10:     size_t i, j;
11:
12:       /*
13:       * Check the simple cases first:
14:       * If fewer than 2 elements, already sorted
15:       * If exactly 2 elements, just swap them (if needed).
16:          * /
17:       if (num <2)
18:                return;
19:       else if (num==2)
20:        {
21:           if (strcmp(array[O], array[1])>O)
22:                 exchange (array[0], array[1] ,temp)
23:        }
24:        / *
25:        * Partition the array using the middle (num/2)
26:        element as the dividing element.
27:          * /
28:       exchange (array[0], array[num / 2], temp)
29:       i=1;
30:       j=num;
31:       for (; ;)
32:         {
33:             / *
34:               * Sweep forward until and element is found that
35:               * belongs in the second partition.
36:               * /
37:              while (i<j && strcmp (array, array[0])
38:                                                   <=0)
39:                    i++;
40:              / *
41:                * Then sweep backward until an element
42:                * is found that belongs in the first
43:                * partition.
44:                * /
45:             while (i<j&& strcmp(array[j-1], array[O]
46:                                               >=0)
47:                  j--;
48:              / * If no out-of-place elements, you're done * /
49:            if (i>=j)
50:                  break
51:               / * Else, swap the two out-of-place elements * /
52:              exchange(array, array[j-l], temp)
53:        }
54:       / * Restore dividing element * /
55:       exchange(array[O], array[i-1], temp)
56:       / * Now apply quick sort to each partition * /
57:       myQsort (array, i-1 )
58:       myQsort (array + i, num-i)
59:  }
60:
61: / * Sort strings using your own implementation of quick sort * /
62: void sortStrings (char * array[])
63: {
64:       / * First, determine the length of the array * /
65:       int num
66:
67:       for (num = O; array[num] ; num++ )
68:
69:       myQsort((void * ) array, num)
70: }

回复

使用道具 举报

2

主题

948

帖子

83

积分

注册会员

Rank: 2

积分
83
发表于 2016-1-27 22:24:19 | 显示全部楼层
很不错的帖子,又学到了,力挺
回复 支持 反对

使用道具 举报

1

主题

345

帖子

364

积分

中级会员

Rank: 3Rank: 3

积分
364
QQ
发表于 2016-2-1 18:31:38 | 显示全部楼层
顶楼主,帮你顶个贴,我挣个积分
回复 支持 反对

使用道具 举报

1

主题

1022

帖子

69

积分

注册会员

Rank: 2

积分
69
发表于 2016-7-14 16:26:14 | 显示全部楼层
好啊楼主,没想到啊,太好了
回复 支持 反对

使用道具 举报

1

主题

1042

帖子

76

积分

注册会员

Rank: 2

积分
76
发表于 2016-11-3 11:01:47 | 显示全部楼层
一下子解决了我工作当中的难题,谢谢楼主,非常感谢!
回复 支持 反对

使用道具 举报

0

主题

957

帖子

52

积分

注册会员

Rank: 2

积分
52
发表于 2018-10-22 10:32:06 | 显示全部楼层
顶一个
回复 支持 反对

使用道具 举报

1

主题

851

帖子

7

积分

注册会员

Rank: 2

积分
7
发表于 昨天 16:48 | 显示全部楼层
有些不是太明白,研究研究再说
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则



陕ICP备15003731号  

贠老师培训 GMT+8, 2018-11-21 01:33 , Processed in 0.221445 second(s), 32 queries .

快速回复 返回顶部 返回列表