快速排序
type
status
date
slug
summary
tags
category
icon
password
从大二开始，就没写过任何算法相关的东西了，数据结构也只是知道一个大概而已。最近在看《Thinking in Java》，看到集合一章的时候，书中使用到了快速排序。我一直在自嘲不会手写快排，不会翻转二叉树，今天就顺便看了下快排的思想。
初步
对于一个数组（简化为整数数组）：
- 任选其中一个作为轴点（简化选择最后一个值）。
- 然后从两端用两个指针（L，R）进行遍历：
- L指针从左侧开始遍历，如果指向的数值不小于轴点，则停止。
- R指针开始从右侧遍历，如果指向的数值不大于轴点，则停止。
- 交换LR指针所指向的值,LR指针继续移动。
- 直至LR指针相遇
- LR指针指向同一点，交换此值与轴点。此时，此点左侧（L遍历过的）所有的值均小于此点，右侧（R遍历过的）所有的值均大于此点。
- 把此点左右分别进行递归快排。
实现
换种方式
再次把思路简化一下：
- 任选其中一个作为轴点。
- 搞个大动作，把轴点移动（交换到中间），使这个轴点左边的值均小于此点，右边的值都大于此点。
- 把此点左右分别进行递归快排。
伪实现
具体细节
依旧可以像上面那样两个指针LR，分别从左和从右开始遍历，直至相遇。
也可以这样：
- 用两个指针，一前一后进行遍历。
- 保证其中一个指针L左侧所有的值都小于等于轴点，所在点大于轴点。
- 另外一个指针P则由L向右移动，当P指向的值小于轴点时，交换LP所指向的值。
- L向前移动，P也继续向前移动。
- 直至P移动到最后一位。
- 此时L点左侧都小于轴点，右侧都大于轴点（因为P遍历过，如果存在小于轴点的点，早就交换位置了）。
具体实现
Loading...