常用排序算法的比较(8)

0。0 第一次写了10KB+的代码略感动。 虽然好多都是来源于书本,但理解起来还是略费尽。总之还是很有成就感的!

所有记录重新排列成关键字有序的序列。

2.3.4冒泡排序.

冒泡排序的基本思想就是将待排序的元素看作是竖着排列的“气泡”，关键字较小的元素比较轻，从而要往上浮。在冒泡排序算法中需要对这个“气泡”序列处理若干遍。处理方法为，自底而上检查一遍整个序列，并时刻注意两个相邻元素的顺序是否正确。如果发现两个相邻元素逆序，即“轻”的元素如果在下边，就交换它们的位置。这样处理一遍之后，“最轻”的元素浮到了第一个，处理第二遍之后“次轻”的元素就浮到了第二个位置。并且，在作第二遍处理的时候，由于第一个位置上的元素已经是“最轻”，所以不必再次比较。即，第i遍处理时，不必检查第i个位置以下的元素。

BubbleSort（）：

for( i = Num; i >= 1; i--) { for( j = Num; j > swap; j--) { if(p[j] < p[j -1])//如果“轻”的元素在下边，则将其与上一个元素交换位置

{ p[0] = p[j -1]; p[j - 1] = p[j]; p[j] = p[0]; } } swap++;//监控排序次数 }

基本过程和算法：

第一遍冒泡排序，首先第Num个元素与第Num – 1个元素比较，逆序则交换；然后第Num -1元素与第Num – 1个元素比较；直到第二个元素与第一个元素比较为止。结果，关键字最小的元素放在第一的位置。

第二遍冒泡排序，除了对第一个之外的Num -1个元素进行相同操作，结果次小元素放在第二的位置上。

在排序过程中监控比较次数，当比较次数为 temp为 Num -1时，排序过程结束，所有元素都已经有序。

2.3.5快速排序

快速排序的基本思想是，通过一轮排序将序列分割成独立的两部分，其中一部分序列的关键字均比另一部分关键字小。继对长度缩短的序列进行同样的分