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

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

割，最后达到整体有序。在排序过程中，由于已经分开的两部分的元素不再需要进行比较，所以减少了比较次数，提高了排序效率，降低了排序时间。

QuickSort（）： temp = p[x]; while( i < j) { while((p[j] >= temp)&&(j > i))//j向前搜索，寻找关键字小于基准值的位置

{ j--; } if(j > i) { p[i] = p[j]; i++; while((p[i] <= temp) && ( i < j))//i 向后搜索，寻找关键字大于基准值的位置

{ i++; } if( i < j) { p[j] = p[i]; j--; } } }

p[i] = temp; if( i- 1 > x) QuickSort(p, x, i-1); if( j+1 < y) QuickSort(p, j+1, y);

首先，在序列p中选取一个中轴值p[x]，而后将p分开成为两个部分，其中左边的部分中的元素均小于或者等于p[x]，右边部分的元素均大于或等于中轴值，而后通过递归调用快速排序的过程分别对这两个部分进行排序，最后将这两个部分产生的结果合并即可得到最后的排序序列。

关于“基准值”，我使用的是第一个记录的关键字值。数组中待排序的记录中有j个记录的关键字小于基准值，这些记录就放在数组的最左边的k个位置（不包括p[0]）上，而大于基准值的记录就放在数组最右边的Num –j个位置上。基准值的位置的下标就是j。第一次划分之后，再用相同的算法对“基准值”左右子序列分别进行类似的操作，其中一个子序列有j个记录，另一个子序列有Num -（k+1）个记录。依此递归执行，知道每个子序列中的记录个数不超过一个为止，排序过程结束。

基本过程与算法：

首先选第一个记录作为枢轴附设两个指针i和j分别指向第一个记录和最后一个记录。