C++快速排序的分析与优化详解(2)
运行结果如下： [songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1210309 clicks(about 1.21031 seconds). Randomized quicksort took 457573 clicks(about 0.457573 seconds). [songlee@loc
运行结果如下：
[songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1210309 clicks(about 1.21031 seconds). Randomized quicksort took 457573 clicks(about 0.457573 seconds). [songlee@localhost ~]$ ./QuickSort Traditional quicksort took 1208038 clicks(about 1.20804 seconds). Randomized quicksort took 644950 clicks(about 0.64495 seconds).
从运行结果可以看出，对于有序的输入，随机化版本的快速排序的效率会高很多。
问题记录：
我们知道交换两个变量的值有以下三种方法：
int tmp = a; // 方法一 a = b; b = tmp a = a+b; // 方法二 b = a-b; a = a-b; a = a^b; // 方法三 b = a^b; a = a^b;
但是你会发现在本程序中，如果swap函数使用后面两种方法会出错。由于方法二和方法三没有使用中间变量，它们交换值的原理是直接对变量的内存单元进行操作。如果两个变量对应的同一内存单元，则经过两次加减或异或操作，内存单元的值已经变为了0，因而不能实现变量值交换。所以当需要交换值的变量可能是同一变量时，必须使用第三变量实现交换，否则会对变量清零。
- 上一篇：C++线性时间的排序算法分析
- 下一篇：C++实现矩阵原地转置算法
精彩图集
精彩文章