快捷搜索:

实例:C语言排序算法五例

一、插入排序(Insertion Sort)

1. 基础思惟:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素整个插入完为止。

2. 排序历程:【示例】:

[初始关键字] [49] 38 65 97 76 13 27 49

J=2(38) [38 49] 65 97 76 13 27 49

J=3(65) [38 49 65] 97 76 13 27 49

J=4(97) [38 49 65 97] 76 13 27 49

J=5(76) [38 49 65 76 97] 13 27 49

J=6(13) [13 38 49 65 76 97] 27 49

J=7(27) [13 27 38 49 65 76 97] 49

J=8(49) [13 27 38 49 49 65 76 97]

Procedure InsertSort(Var R : FileType);

//对R[1..N]按递增序进行插入排序, R[0]是监视哨//

Begin

for I := 2 To N Do //依次插入R[2],...,R[n]//

begin

R[0] := R[I]; J := I - 1;

While R[0]

二、选择排序

1. 基础思惟:每一趟从待排序的数据元素中选出最小(或最大年夜)的一个元素,顺序放在已排好序的数列的着末,直到整个待排序的数据元素排完。

2. 排序历程:【示例】:

初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 [38 65 97 76 49 27 49]

第二趟排序后 13 27 [65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [49 97 65 76]

第五趟排序后 13 27 38 49 49 [97 97 76]

第六趟排序后 13 27 38 49 49 76 [76 97]

第七趟排序后 13 27 38 49 49 76 76 [ 97]

着末排序结果 13 27 38 49 49 76 76 97

Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 //

Begin

for I := 1 To N - 1 Do //做N - 1趟选择排序//

begin

K := I;

For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]//

begin

If R[J]I Then //互换R[I]和R[K] //

begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;

end

End; //SelectSort //

三、冒泡排序(BubbleSort)

1. 基础思惟:两两对照待排序数据元素的大年夜小,发明两个数据元素的序次相反时即进行互换,直到没有反序的数据元素为止。

2. 排序历程:设想被排序的数组R[1……N]垂直直立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反滥觞基本则的轻气泡,就使其向上\"漂浮\",如斯反复进行,直至着末任何两个气泡都是轻者在上,重者鄙人为止。

【示例】:

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//

Begin

For I := 1 To N-1 Do //做N-1趟排序//

begin

NoSwap := True; //置未排序的标志//

For J := N - 1 DownTo 1 Do //从底部往上扫描//

begin

If R[J+1]

四、快速排序(Quick Sort)

1. 基础思惟:在当前无序区R[1……H]中任取一个数据元素作为对照的\"基准\"(不妨记为X),用此基准将当前无序区划分为阁下两个较小的无序区:R[1……I-1]和R[I+1……H],且左边的无序子区中数据元素均小于即是基准元素,右边的无序子区中数据元素均大年夜于即是基准元素,而基准X则位于终极排序的位置上,即R[1……I-1]≤X.Key≤R[I+1……H](1≤I≤H),当R[1……I-1]和R[I+1……H]均非空时,分手对它们进行上述的划分历程,直至所有无序子区中的数据元素均已排序为止。

2. 排序历程:【示例】:

初始关键字 [49 38 65 97 76 13 27 49]

第一次互换后 [27 38 65 97 76 13 49 49]

第二次互换后 [27 38 49 97 76 13 65 49]

J向左扫描,位置不变,第三次互换后 [27 38 13 97 76 49 65 49]

I向右扫描,位置不变,第四次互换后 [27 38 13 49 76 97 65 49]

J向左扫描 [27 38 13 49 76 97 65 49]

(一次划分历程)

初始关键字 [49 38 65 97 76 13 27 49]

一趟排序之后 [27 38 13] 49 [76 97 65 49]

二趟排序之后 [13] 27 [38] 49 [49 65]76 [97]

三趟排序之后 13 27 38 49 49 [65]76 97

着末的排序结果 13 27 38 49 49 65 76 97

各趟排序之后的状态

Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer);

//对无序区R[1,H]做划分,I给以出本次划分后已被定位的基准元素的位置 //

Begin

I := 1; J := H; X := R[I] ;//初始化,X为基准//

Repeat

While (R[J] >= X) And (IX //

beginR[J] := R[I]; //相称于互换R[I]和R[J]//

J := J - 1

end

Until I = J;

R[I] := X //基准X已被终极定位//

End; //Parttion //

Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//

Begin

If S

五、堆排序(Heap Sort)

1. 基础思惟:堆排序是一树形选择排序,在排序历程中,将R[1……N]当作是一颗完全二叉树的顺序存储布局,使用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

2. 堆的定义: N个元素的序列K1,K2,K3,……,Kn.称为堆,当且仅当该序列满意特点:Ki≤K2i Ki ≤K2i+1(1≤ I≤ [N/2])

堆实质上是满意如下性子的完全二叉树:树中任一非叶子结点的关键字均大年夜于即是其孩子结点的关键字。例如序列10,15,56,25,30,70便是一个堆,它对应的完全二叉树如上图所示。这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆。反之,若完全二叉树中任一非叶子结点的关键字均大年夜于即是其孩子的关键字,则称之为大年夜根堆。

3. 排序历程:堆排序恰是使用小根堆(或大年夜根堆)来拔取当前无序区中关键字小(或最大年夜)的记录实现排序的。我们不妨使用大年夜根堆来排序。每一趟排序的基础操作是:将当前无序区调剂为一个大年夜根堆,拔取关键字最大年夜的堆顶记录,将它和无序区中的着末一个记录互换。这样,恰恰和直接选择排序相反,有序区是在原记录区的尾部形成并慢慢向前扩大年夜到全部记录区。

【示例】:

对关键字序列42,13,91,23,24,16,05,88建堆

Procedure Sift(Var R :FileType; I, M : Integer);

//在数组R[I..M]中调用R[I],使得以它为完全二叉树构成堆。事先已知其左、右子树(2I+1

六、几种排序算法的对照和选择

1. 拔取排序措施必要斟酌的身分:

(1) 待排序的元素数目n;

(2) 元素本身信息量的大年夜小;

(3) 关键字的布局及其散播环境;

(4) 说话对象的前提,帮助空间的大年夜小等。

2. 小结:

(1) 若n较小(n <= 50),则可以采纳直接插入排序或直接选择排序。因为直接插入排序所需的记录移动操作较直接选择排序多,因而当记录本身信息量较大年夜时,用直接选择排序较好。

(2) 若文件的初始状态已按关键字基础有序,则选用直接插入或冒泡排序为宜。

(3) 若n较大年夜,则应采纳光阴繁杂度为O(nlog2n)的排序措施:快速排序、堆排序或归并排序。 快速排序是今朝基于对照的内部排序法中被觉得是最好的措施。

(4) 在基于对照排序措施中,每次对照两个关键字的大年夜小之后,仅仅呈现两种可能的转移,是以可以用一棵二叉树来描述对照鉴定历程,由此可以证实:当文件的n个关键字随机散播时,任何借助于\"对照\"的排序算法,至少必要O(nlog2n)的光阴。

(5) 当记录本身信息量较大年夜时,为避免消费大年夜量光阴移动记录,可以用链表作为存储布局。

您可能还会对下面的文章感兴趣: