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

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

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

网页标题：比较排序之快速排序(实例代码)
本文链接：http://scyanting.com/article/iishss.html

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

其他资讯