快速排序的实现方式?

我在实现快速排序时看见了几种方式,当面试问第一趟排序时的序列,我该选择那种。

pivot变量的存储方式:

  1. 把pivot 放到末尾或者开始。然后进行排序交换。
int pivot = serial[end];
int left = start, right = end - 1;
  1. 使用一个临时变量temp 保存 pivot的值,最后 serial[left] = temp

值的交换方式:

  1. 第一趟 right 索引找到比 pivot小的数就赋值给serial[left] = serial[right], 然后找到left索引比 pivot大的值serial[right] = serial[left]
  2. 同时找到 left 和 right 然后 swap(&serial[left], &serial[right]

请问那种方式最合适,或者面试问的时那种。感谢你的帮助。

我一般都随机一个,你直接问 pivot 取哪个就好?

可以参考下这个https://github.com/freebsd/freebsd/blob/master/lib/libc/stdlib/qsort.c

2 个赞

两个应该都可以.

我第一次见到 serial[left] = serial[right] 这种写法的时候, 很惊奇, 因为这样可以减少交换所需的临时变量, 写法也更简单一点. 不过见到更多的还是第二种. 两种写法应该没什么区别, 不晓得有没有人能说一下.

我也是对此很迷惑