快速排序相比于其他O(nlogn)的算法,大多数情况下都要更快,因为其内部循环在大部分框架上可以很有效率地达成。采用分而治之的思想,步骤如下:
-
挑选一个元素作为基准,通常为第一个元素;
-
从右往左找小于基准的元素,再从左往右找大于基准的元素,将两者交换位置;
-
重复步骤2直到 j = i,将当前元素与基准交换;
-
此时基准数将数列分割成为了两个长短不一的子数列,分别进行如上排序,直至排序完成。
代码写得很烂,请大家不要喷我。。。
要注意在分割数列时,一定是先从右往左找小于等于基准的元素,否则可能会把大于基准的数放到基准数的左侧导致排序出错。
点赞 (1)
回复