比较排序之快速排序(实例代码)_网络技术_宿州市腾雀网络科技有限公司

比较排序之快速排序(实例代码)

发布时间 - 2026-01-11 02:04:15 点击率：次

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

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

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

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

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

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

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

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

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

java

package com.algorithm.sort.quick;

import java.util.Arrays;

/**
 * 快速排序
 * Created by yulinfeng on 2017/6/26.
 */
public class Quick {
  public static void main(String[] args) {
    int[] nums = {6, 5, 3, 1, 7, 2, 4};
    nums = quickSort(nums, 0, nums.length - 1);
    System.out.println(Arrays.toString(nums));
  }
  
  /**
   * 快速排序
   * @param nums 待排序数组序列
   * @param left 数组第一个元素索引
   * @param right 数组最后一个元素索引
   * @return 排好序的数组序列
   */
  private static int[] quickSort(int[] nums, int left, int right) {
    if (left < right) {
      int temp = nums[left];  //基数
      int i = left;  //哨兵i
      int j = right;  //哨兵j
      while (i < j) {
        while (i < j && nums[j] >= temp) {
          j--;
        }
        if (i < j) {
          nums[i] = nums[j];
          i++;
        }
        while (i < j && nums[i] < temp) {
          i++;
        }
        while (i < j) {
          nums[j] = nums[i];
          j--;
        }
      }
      nums[i] = temp;
      quickSort(nums, left, i - 1);
      quickSort(nums, i + 1, right);
    }
    return nums;
  }
}

Python3

#快速排序
def quick_sort(nums, left, right):
  if left < right:
    temp = nums[left]  #基数
    i = left  #哨兵i
    j = right  #哨兵j
    while i < j:
      while i < j and nums[j] >= temp:
        j -= 1
      if i < j:
        nums[i] = nums[j]
        i += 1
      while i < j and nums[i] < temp:
        i += 1
      if i < j:
        nums[j] = nums[i]
        j -= 1
    nums[i] = temp
    quick_sort(nums, left, i - 1)
    quick_sort(nums, i + 1, right)
  
  return nums

nums = [6, 5, 3, 1, 7, 2, 4]
nums = quick_sort(nums, 0, len(nums) - 1)
print(nums)

以上这篇比较排序之快速排序(实例代码)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。

# 快速排序 # java # 快速排序的原理及java代码实现 # 快速排序的深入详解以及java实现 # 第一个 # 对其 # 给大家 # 为例 # 递归 # 则需 # 本末倒置 # 则是 # 较高 # 要在 # 很高 # 希望能 # 做一个 # 为其 # 又会 # 影响到 # 这篇 # 会用 # 第二步 # 则会

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：在CentOS上运行PyTorch脚本的技巧

下一篇：潍坊网站优化策略：提升排名与流量的秘籍

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：在CentOS上运行PyTorch脚本的技巧

下一篇：潍坊网站优化策略：提升排名与流量的秘籍