快速排序算法原理简介

前言

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

概念介绍

  • 排序算法" title="快速排序算法">快速排序算法是对冒泡排序算法" title="冒泡排序算法">冒泡排序算法的一种改进

  • 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列

原理讲解

我们以[2 17 17 24 34 41]这个序列为例说明快速排序算法的实现原理

  1. 未开始排序算法之前，此时效果如下图

    在这里插入图片描述

  2. 准备开始排序之前，我们取序列***最左边***的元素24所在位置为***low指针***，取序列***最右边***元素41所在位置为***high指针***。并取序列***最右边***元素24为***基准值***。此时效果如下图

    在这里插入图片描述

  3. 刚开始时，我们将high指针从右往左移动，寻找小于基准值24的元素。当找到第一个小于基准值的元素19时，此时效果如下图

    在这里插入图片描述

    将high指针所指的元素和low指针所指的元素交换位置。此时效果如下图

    在这里插入图片描述

  4. 再从low指针从左往右移动，寻找大于基准值24的元素。当找到第一个大于基准值的元素34时，此时效果如下图

    在这里插入图片描述

    将high指针所指的元素和low指针所指的元素交换位置。此时效果如下图

    在这里插入图片描述

  5. 此时low指针和high指针并未重合，说明整个序列并未遍历一遍。我们继续将high指针从右往左移动，寻找小于基准值24的元素，当再次找到第一个小于基准值的元素2时，此时效果如下图

    在这里插入图片描述

    将high指针所指的元素和low指针所指的元素交换位置。此时效果如下图

    在这里插入图片描述

  6. 经过上述步骤，low指针和high指针重合，序列完成第一次遍历。此时整个序列以[2 17 17 24 34 41]拆分成左子序列以[19 17 2]和右子序列以[24 34 41]，效果如下图

    在这里插入图片描述

  7. 将左子序列[19 17 2]和右子序以[24 34 41]分别进行快速排序过程，直至整个序列排序完成，此时效果如下图

    在这里插入图片描述

时间复杂度

  • 最优情况下，快速排序算法时间复杂度为O(N*logN)

  • 一般情况下，快速排序算法时间复杂度为O(N*logN)

  • 最差情况下，快速排序算法时间复杂度为O(N^2)

空间复杂度

  • 最优情况下，快速排序算法空间复杂度为O(logN)

  • 最差情况下，快速排序算法空间复杂度为O(N)。此时快速排序算法退化为冒泡排序算法

算法优缺点

  • 优点：速度快，效率高

  • 缺点：不稳定

效果展示

在这里插入图片描述

以上是 快速排序算法原理简介 的全部内容， 来源链接： utcz.com/a/25062.html

回到顶部