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

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

指针j向前搜索逐个记录与基准值进行比较，直到发现小于基准值的记录为止，将其与枢轴记录相互交换。

指针i向后搜索逐个记录与基准值进行比较，直到发现大于基准值的记录为止，将其与枢轴记录相互交换。

重复上述步骤直到 i = j为止。完成一轮排序，完成一次分割，对前后两个子表按上述原则再分割，知道所有子表的表长不超过1为止。

2.3.6简单选择排序

简单选择排序的基本思想是，首先从序列中选出关键字最小的记录送到最前位置，再从余下的序列中选取关键字最小的记录送到第二的位置，直至寻列中所有的记录都已经选择为止。

SelectSort()：

for( i = 1; i <= Num; i++) { min = i; for( j = Num; j > i; j--) { if(p[min] > p[j]) min = j; } p[0] = p[min];//利用p[0]中介交换 p[min] = p[i]; p[i] = p[0]; }

算法：对数组p[]，将其从小到大进行排序，首先从p[1],p[2],p[3], ,p[Num]中选择最小值，找到之后，则将它的值与p[1]对换(借助p[0])；然后从p[2],p[3],p[4], ,p[Num]中选择最小值，再将其与p[2]对换。如此进行选择和调换，对第i趟选择排序，进行Num – 1次关键字比较，从Num –i +1个记录中选出关键字最小的记录，并与第i个记录交换。令i从1 至Num-1，进行Num-1趟选择排序，有序序列就此形成。

2.3.7堆排序

堆排序是一种基于选择排序的排序方法。它是一种树形选择排序，利用堆顶记录的关键字最小这一特征，使得在当前无序区中选取最大关键字的记录变得简单。

对任意的p[i（i = 1，2，3 ）]都有p[i] >= p[2 *i]并且p[i] >= p[2*i+1]。 它的基本思想是，首先将待排序的记录序列构造成一个堆。此时，选出了堆中所有记录的最小值，然后将它从堆中移走，并将剩余的记录再调整成堆，又找