快速排序原理
快速排序是基于 "分治法" 原理实现, 所谓分治法就是不断的将原数组序列按照一定规律进行拆分, 拆分后各自实现排序直到拆分到序列只剩下一个关键字为止. 快速排序首先选取一个关键字为标志位(关键字的选取影响排序效率), 然后将序列中小于标志位的关键字移动至标志位左侧, 大于标志位的关键字移动至右侧. 一趟比较完成后, 整个序列以选取的标志位为界, 左侧均小于标志位, 右侧均大于关键字. 但左右两侧内部并不是有序的(左右两侧关键字个数也不一定相同). 进而继续将左右两侧分别再以这种方式进行排序, 直到将序列拆分的剩余一个关键字为止, 整个序列即变成有序.
图解快速排序
下面以 [6 ,1 ,2 ,7, 9 ,3 ,4 ,5 ,10 ,8] 序列为例用图解的方式讲解快速排序的过程
这里我们选取标志位的方式是: 序列左边第一个关键字即 6 并放入标志位变量 flag 中 , 然后将 L(left)指针指向最左边, 将 R(right)指针指向最右边.
然后从右边指针开始让 R 指针指向的关键字与标志位 flag 比较, 如果关键字大于或等于 flag, 则继续向左移动(右侧关键字本身就要大于 flag), 直到找到小于 flag 的关键字, 即关键字 5.R 指针停止移动. 并开始让 L 指针指向的关键字与 flag 比较, 如果小于 flag 则 L 指针继续向后移动, 直到找到大于 flag 的关键字, 即关键字 7. 此时序列如下图所示
此时再比较指针 L 是否小于 R, 满足条件, 交换两指针对应的值, 即 7 与 5 交换. 交换后仍满足 L<R 指针, 继续从 R 指针与 flag 比较, 找小于 6 的关键字, 即指向关键字 4,R 指针停止移动. 并开始让 L 指针指向的关键字与 flag 比较, 找大于 6 的关键字, 即指向关键字 9. 此时序列如下图所示
此时仍满足 L<R 的条件, 所以将 9 与 4 交换. 继续按照上述步骤进行, R 向前移动并找到小于 flag 的关键字 3,R 指针停止移动. 并开始 L 指针向后移动, 当 L 指针指向 3 时, 虽然满足 3<6, 但此时不再满足 L<R(此时 L=R). 然后将 L 和 R 同时指向的关键字 3 移动至序列左边第一个关键字中, 并将 flag 放入 L 和 R 指向的位置, 这一趟比较结束. 此时序列如下图所示
从图中可以看到, 一趟比较后, 整个序列以我们选取的标志位为界, 将整个序列分为两个部分, 其中左边部分关键字都小于标志位, 而右侧部分均大于标志位. 但左右两侧内部无序.
然后再将左右两侧子序列分别执行上述步骤, 直至左右两侧剩余一个元素无法再拆分时, 整个序列即为有序.
代码实现
- public static void quickSort(int[] array ,int left,int right){
- int l,r,flag,temp;
- if(left>= right){
- return;
- }
- l = left;
- r = right;
- flag = array[left];
- while (l <r){
- // 先从右边找
- while (array[r]>= flag && l < r){
- r --;
- }
- // 再从左边找
- while (array[l] <= flag && l < r){
- l ++;
- }
- // 交换
- if(l < r){
- temp = array[l];
- array[l] = array[r];
- array[r] = temp;
- }
- }
- // 一趟交换完将基准值放入临界位置
- array[left] = array[l];
- array[l] = flag;
- // 向左递归
- quickSort(array,left,l-1);
- quickSort(array,l+1,right);
- }
代码分析
1)选取数组左边第一个关键字为标志位, 并暂存至 flag 中(注: 标志位选取的方式可用不同方式)
2)第一层 while 循环用于保证一趟比较遍历完所有关键字
3)第二层第一个 while 循环用于从右侧依次向左找小于 flag 的关键字
4)第二层第二个 while 循环用于从左侧依次向右找大于 flag 的关键字
5)第二层的两个 while 循环执行后, 如果 l<r 则进行交换
6)一趟比较后, 将 l 和 r 共同指向的关键字放入最左侧, 即 flag 的选取位置, 并将 flag 值放入此位置, 此时序列便以 flag 为界, 左边均小于 flag, 右边均大于 flag
7)然后再用 "分治法" 分别向左和向右递归执行上述步骤, 直到无法拆分为止, 整个序列即为有序
时间复杂度
快速排序时间复杂度为 O(NlogN)
测试算法执行效率
与前面的排序算法相同, 我们依然生成 10 万个随机数的数组, 使用插入排序方法进行排序, 看其执行时间. 测试代码如下
- public static void main(String[] args){
- int array[] = new int[100000];
- for (int i = 0; i < 100000; i++) {
- array[i] = (int) (Math.random()*1000000);
- }
- long begin = System.currentTimeMillis();
- quickSort(array,0,array.length-1);
- System.out.println("总耗时 ="+(System.currentTimeMillis()-begin)+"毫秒");
- }
测试结果
可以看到快速排序对 10 万个关键字的数组进行排序, 只用了 50 多毫秒, 相比我们前面讲解的希尔排序又快了许多.
总结
快速排序每趟比较首先选取某个关键字作为标志位, 然后使用左右指针遍历数组关键字与 flag 进行比较, 并将右侧小于 flag 的关键字与左侧大于 flag 的关键字进行交换. 然后再使用 "分治法" 方式对数组拆分, 将数组以 flag 为界拆分为左右两个子序列, 并对两个子序列递归执行上述步骤, 直到子序列剩余 1 个关键字无法拆分为止, 此时整个序列即为有序.
来源: https://www.cnblogs.com/menglong1108/p/11749616.html