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

软件编程 java 分类:[default] 更新日期: 2016-12-11
下面小编就为大家带来一篇比较排序之快速排序实例代码。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧

快速排序(简称快排)因为其效率较高(平均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)

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


> 本站内容系网友提交或本网编辑转载,其目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题,请及时与本网联系,我们将在第一时间删除内容!

相关文章
  • Flex输出文件到本地的两种方法
    flex中输出文件到本地有两种方法分别是File和FielRefreence,下面的实例代码,大家可以看看在flex中输出文件到本地目前我用到两种方法,分别是File和FielRefreence 例子: var exportString:String = "这就是一个测试" 1.File输出 代码如下:var ff:File = File ...
  • 将PHP的session数据存储到数据库中的代码实例
    这里我们将分享两个将PHP的session数据存储到数据库中的代码实例,分别针对PostgreSQL与MySQL,需要的朋友可以参考下一个开发环境有多个网站,需要使用不同的session,解决方案很多.不过这次也高大上一把,用数据库存,方便以后扩展. PostgreSQL版首先是数据库的部分 --drop table php_session create u ...
  • php项目开发中用到的快速排序算法分析
    这篇文章主要介绍了php项目开发中用到的快速排序算法,结合实例形式详细分析了php快速排序的原理与使用方法,需要的朋友可以参考下本文实例讲述了php项目开发中用到的快速排序算法.分享给大家供大家参考,具体如下: 实际上在,做web开发,比较少遇到使用一些算法之类的,毕竟不是做搜索引擎,也不是写底层(比如写个类似于mysql这样的数据库,里面需要自己实现排序算 ...
  • ASP.NETWebApi2实现多文件打包并下载文件的实例
    ASP.NETWebApi2实现多文件打包并下载文件的实例
    这篇文章主要介绍了ASP.NET Web Api 2利用ByteArrayContent和StreamContent实现多文件打包并下载的方法,提供源码下载,需要的朋友可以参考下.最近由于工作和个人事务,站点也好久没更新了,但这并不影响我对.NET的热情.站点的更新工作还是得想办法抽时间来完成的. 今天利用中午的时间来写一篇关于Asp.Net Web Api ...
  • 详解表单验证正则表达式实例(推荐)
    这篇文章主要介绍了详解表单验证正则表达式实例推荐的相关资料,非常不错,具有参考借鉴价值,特此分享到平台供大家参考验证:!reg.test(value) 邮箱: 代码如下:reg = /^\w+((-\w+)|(\.\w+))*\@[A-Za-z0-9]+((\.|-)[A-Za-z0-9]+)*\.[A-Za-z0-9]+$/i; 不包含中文: 代码如下:r ...
  • Linux上安装Python的PIL和Pillow库处理图片的实例教程
    这里我们来看一下在Linux上安装Python的PIL和Pillow库处理图片的实例教程,包括一个使用Pillow库实现批量转换图片的例子:安装正常情况,只需 pip install PIL==1.1.7 或者 pip install Pillow==2.9.0 即可.但需留意安装后的输出安装完成后,需留意输出: *** TKINTER support no ...
猜你喜欢