快速排序是一种分治策略的排序算法，关键过程是对数组进行划分。选择一个基准值（pivot element），围绕着这个基准值划分子数组，对子数组递归调用快速排序，直到数组有序。

1、选取基准元素。将最后一个元素（随机值、三数中值） 作为基准值 pivot。
2、划分子数组。遍历数组，将小于基准值的元素交换到左边，大于基准值的元素交换到右边，将基准值交换到正确的位置，并返回其索引作为分区点。经过这一步骤之后，数组被划分成小于和大于基准值的2个子数组。
3、递归调用。递归地对这2个子数组进行快速排序，直到整个数组有序。

• 一次快速排序的过程

• 快速排序全过程

• 数组变化

• 时间复杂度：O(n log n)
    快速排序的时间复杂度可以通过递归树来分析。在每一层中，我们选择一个主元素并将数组划分为两个子数组，时间复杂度为O(n)。如果我们将递归树表示为二叉树，则总共有 log n 层，并且每层的时间复杂度为 O(n)，因此整个算法的时间复杂度为 O(n log n)。

以下情况快速排序的时间复杂度将退化为 O(n^2)：
  1、数组已经有序。在待排序数组已经有序的情况下，每次划分只能减少一个元素，时间复杂度将退化为 O(n^2)。
  2、基准值有问题。选择的基准值不能把数组分区成均衡的两部分，基准值都是最小或最大的元素，导致每次分区后，一个子数组为空，而另一个子数组包含剩余的所有元素，时间复杂度将退化为O(n^2)。

• 空间复杂度：O(log n)
    快速排序的空间复杂度主要由递归调用栈决定。在最好的情况下（即每次分区都非常平衡），递归深度为 log n，因此空间复杂度为 O(log n)。

  在最坏的情况下（即每次分区都极度不平衡），递归深度可以达到 n，空间复杂度将退化为 O(n)。

  快速排序是不稳定的排序算法，因为在排序过程中会涉及到交换操作，可能导致相同元素的相对顺序发生变化。

    以上就是本篇文章【go 语言实现快速排序】的全部内容了，欢迎阅览 ！ 文章地址：http://ww.kub2b.com/news/18282.html
     栏目首页      相关文章      动态      同类文章      热门文章      网站地图      返回首页 企库往资讯移动站 http://ww.kub2b.com/mobile/ , 查看更多