首页 > 数据结构与算法

算法原理

快速排序是目前各种排序算法中较为高效的一种算法,它的基本思想是分治法

分治法(Divide and Conquer Algorithm):把原问题分为若干个与原问题结构类似的子问题,然后对子问题进行递归求解,最后把这些子问题的解集全部合并起来就是原问题的解。

 

算法具体实现有三个步骤:

1. 从数组中选出一个元素,我们称之为 “基准”(pivot);

2. 先进行一次循环比较,把所有比基准小的数放左边,把所有比基准大的数放右边(相等的值随便哪边放都行),这个操作称为分区 (partition) 操作。当分区完成后,我们就得到了两个子分区,   其中一个分区的所有元素的值都比另外一个分区大。

3. 分别对步骤二分出来的两个子集进行递归排序,直到最后子集只剩一个元素为止。

2016050511445291

图片来自维基百科

继续阅读→

阅读全文

前言

  排序算法(Sorting algorithm)是一种能将一串数据依照特定排序方式的最基本最常用的算法,常见的有冒泡排序、快速排序、插入排序、二叉树排序等等,下面这个表格总结了各种排序算法的复杂度与稳定性:

2016050311055495

不同的场景对排序算法的选择有着不同的要求,对每种排序算法的深入理解能帮助我们更好地选择合适的算法。关于排序算法的理论书籍或博客已经非常的多,下面列举一些可视化的排序展示,换种方式看算法,以一种更直观的方式理解排序算法的工作原理。

继续阅读→

阅读全文