专栏首页余林丰6.比较排序之快速排序

6.比较排序之快速排序

  快速排序(简称快排)因为其效率较高(平均O(nlogn))经常在笔试题中对其考查。

  对于快排的第一步是选取一个“基数”,将会用这个“基数”与其它数进行比较交换。而这个“基数”的选择将影响到快排的效率如何,但如果为了选择基数而选择基数则会本末倒置。例如为了找到最佳基数,则需要在整个待排序列中找到中位数,但查找中位数实际上代价又会很高。基数的选择通常来说就是待排序序列中的第一个对象或者中间的一个对象或者最后一个对象。本文以选取第一个元素为例对快排做一个简要分析实现。

  以待排序列{6, 5, 3, 1, 7, 2, 4}为例,选取第一个元素6为基数。

  选择了基数过后则需要进行和数组元素进行比较交换,如何进行比较和谁进行比较?快排第二步在数组的第一个元素和最后元素各设置一个“哨兵”。

  选好基数,设置好哨兵过后,接下来则是开始比较,将基数先与最后一个哨兵j进行比较,如果大于哨兵j则与其进行交换同时哨兵i+1

  此时基数不再与哨兵j进行比较,而是与哨兵i进行比较,如果基数大于哨兵i,则哨兵一直向后移,直到大于基数为止交换同时哨兵j-1。

  重复上面的步骤,基数再与哨兵j比较。

  最终结果可见哨兵i的位置=哨兵j的位置,此时将基数赋值给这个位置。

  这样就达到了基数6左边的数字均小于它,右边的数字均大于它,再利用递归对其左右数组进行同样的步骤选取基数,设置哨兵,最后即可完成排序。

Java

 1 package com.algorithm.sort.quick;
 2 
 3 import java.util.Arrays;
 4 
 5 /**
 6  * 快速排序
 7  * Created by yulinfeng on 2017/6/26.
 8  */
 9 public class Quick {
10     public static void main(String[] args) {
11         int[] nums = {6, 5, 3, 1, 7, 2, 4};
12         nums = quickSort(nums, 0, nums.length - 1);
13         System.out.println(Arrays.toString(nums));
14     }
15     
16     /**
17      * 快速排序
18      * @param nums 待排序数组序列
19      * @param left 数组第一个元素索引
20      * @param right 数组最后一个元素索引
21      * @return 排好序的数组序列
22      */
23     private static int[] quickSort(int[] nums, int left, int right) {
24         if (left < right) {
25             int temp = nums[left];    //基数
26             int i = left;    //哨兵i
27             int j = right;    //哨兵j
28             while (i < j) {
29                 while (i < j && nums[j] >= temp) {
30                     j--;
31                 }
32                 if (i < j) {
33                     nums[i] = nums[j];
34                     i++;
35                 }
36                 while (i < j && nums[i] < temp) {
37                     i++;
38                 }
39                 while (i < j) {
40                     nums[j] = nums[i];
41                     j--;
42                 }
43             }
44             nums[i] = temp;
45             quickSort(nums, left, i - 1);
46             quickSort(nums, i + 1, right);
47         }
48         return nums;
49     }
50 }

  Python3

 1 #快速排序
 2 def quick_sort(nums, left, right):
 3     if left < right:
 4         temp = nums[left]    #基数
 5         i = left    #哨兵i
 6         j = right    #哨兵j
 7         while i < j:
 8             while i < j and nums[j] >= temp:
 9                 j -= 1
10             if i < j:
11                 nums[i] = nums[j]
12                 i += 1
13             while i < j and nums[i] < temp:
14                 i += 1
15             if i < j:
16                 nums[j] = nums[i]
17                 j -= 1
18         nums[i] = temp
19         quick_sort(nums, left, i - 1)
20         quick_sort(nums, i + 1, right)
21     
22     return nums
23 
24 nums = [6, 5, 3, 1, 7, 2, 4]
25 nums = quick_sort(nums, 0, len(nums) - 1)
26 print(nums)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript强化教程——AngularJS 指令

    本文为 H5EDU 机构官方 HTML5培训 AngularJS 通过被称为 指令 的新属性来扩展 HTML。 AngularJS 通过内置的指令来为应用添加功...

    IMWeb前端团队
  • JAVA学习Swing绝对局部简单学习

    package com.swing; import java.awt.Container; import javax.swing.JButton; impo...

    别先生
  • Java中IO流,输入输出流概述与总结

    总结的很粗糙,以后时间富裕了好好修改一下。 1:Java语言定义了许多类专门负责各种方式的输入或者输出,这些类都被放在java.io包中。其中, 所有输入流类都...

    别先生
  • Java抽象类与接口的区别

    很多常见的面试题都会出诸如抽象类和接口有什么区别,什么情况下会使用抽象类和什么情况你会使用接口这样的问题。本文我们将仔细讨论这些话题。

    Java后端工程师
  • Java攻城狮面试考题

    1 <html> 2 <head> 3 <meta http-equiv="Content-Type" content="text/html; chars...

    别先生
  • JAVA学习绘图颜色及其笔画属性设置字体显示文字

    package com.graphics; import java.awt.*; import java.awt.geom.Rectangle2D; impo...

    别先生
  • jQuery/javascript实现简单网页计算器

    1 <html> 2 <head> 3 <meta charset="utf-8"> 4 <title>jQuery实现</title> 5 <scr...

    别先生
  • JAVA学习AWT绘图

    package com.graphics; import java.awt.Graphics; import javax.swing.JFrame; imp...

    别先生
  • Nativescript跨终端应用程序开发方案研究

    1.环境准备 安装nodejs 安装nativescript $npm install -g nativescript 或者下载github上项目代码进行构建(...

    IMWeb前端团队
  • Es6浅析

    Es6浅析 Babel 是一个 JavaScript编译器,它可以把我们编写的符合 ECMAScript 6 标准的代码完美地转换为 ECMAScript 5 ...

    IMWeb前端团队

扫码关注云+社区

领取腾讯云代金券