排序算法简记

列举几种基本的排序算法和排序思想

排序就是将一组对象按照某种逻辑顺序重新排列的过程。

一、选择排序

1、基本原理

最基本的排序，每次都从原有数据中选择最小或最大的数组放入新数据集中

2、步骤(以从小到大为例)

首先， 找到数组中最小的那个元素，

其次， 将它和数组的第一个元素交换位置（ 如果第一个元素就是最小元素那么它就和自己交换） 。

再次， 在剩下的元素中找到最小的元素， 将它与数组的第二个元素交换位置。 如此往复， 直到将整个数组排序。

这种方法叫做选择排序， 因为它在不断地选择剩余元素之中的最小者

3、特点

复杂度 O(n2)

运行时间和输入无关

数据移动是最少的

二、插入排序

1、基本原理

为了给要插入的元素腾出空间， 我们需要将其余所有元素在插入之前都向右移动一位。 这种算法叫做插入排序

2、特点

插入排序所需的时间取决于输入中元素的初始顺序

插入排序对于实际应用中常见的某些类型的非随机数组很有效

3、几种典型的部分有序的数组：
（1）数组中每个元素距离它的最终位置都不远；
（2）一个有序的大数组接一个小数组；
（3） 数组中只有几个元素的位置不正确。
插入排序对这样的数组很有效， 而选择排序则不然

4、提升方法

要大幅提高插入排序的速度并不难， 只需要在内循环中将较大的元素都向右移动而不总是交换
两个元素（ 这样访问数组的次数就能减半）

三、希尔排序

1、基本原理

希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。

这样的数组被称为 h 有序数组。

2、h有序数组

 一个 h 有序数组就是 h 个互相独立的有序数组编织在一起组成的一个数组 。

在进行排序时，如果 h 很大， 我们就能将元素移动到很远的地方，为实现更小的 h 有序创造方便。

用这种方式，对于任意以 1 结尾的 h 序列，都能够将数组排序。

3、实现方法

对于每个 h， 用插入排序将 h 个子数组独立地排序。

但因为子数组是相互独立的， 一个更简单的方法是在 h- 子数组中将每个元素交换到比它大的元素之前去（ 将比它大的元素向右移动一格） 。

只需要在插入排序的代码中将移动元素的距离由 1 改为 h 即可。

这样， 希尔排序的实现就转化为了一个类似于插入排序但使用不同增量的过程。

四、归并排序

1、基本原理

两个有序的数组归并成一个更大的有序数组。

2、基本方法

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

实现归并的一种直截了当的办法是将两个不同的有序数组归并到第三个数组中

3、特点

它能够保证将任意长度为 N 的数组排序所需时间和 NlogN 成正比；

它的主要缺点则是它所需的额外空间和 N 成正比

4、几种方法

原地归并

是将两个不同的有序数组归并到第三个数组中

自顶向下

基于分支思想，如果能将两个子数组排序，就能够通过归并两个子数组来将整个数组排序

自底向上

先归并那些微型数组，然后再成对归并得到的子数组，直到将整个数组归并在一起。这种实现方法比标准递归方法 所需要的代码量更少

5、局限性
（1） 归并排序的空间复杂度不是最优的；
（2）在实践中不一定会遇到最坏情况；
（3）除了比较，算法的其他操作（例如访问数组）也可能很重要；
（4）不进行比较也能将某些数据排序。

五、快速排序 

1、基本原理

快速排序是一种常用的排序算法，比选择排序快得多。

快速排序使用了D&C。

2、基本步骤

首先，从数组中选择一个元素，这个元素被称为基准值（pivot）。

接下来，找出比基准值小的元素以及比基准值大的元素，被称为分区（ partitioning）

得到

（1）一个由所有小于基准值的数字组成的子数组；

（2）基准值；
（3）一个由所有大于基准值的数组组成的子数组

如果子数组是有序的，就可以合并得到一个有序的数组：左边的数组 + 基准值 + 右边的数组
对于包含两个元素的数组（左边的子数组）以及空数组（右边的子数组），只要对这两个子数组进行快速排序，再合并结果，就能得到有序数组
总结得到基本步骤：

(1) 选择基准值。
(2) 将数组分成两个子数组：小于基准值的元素和大于基准值的元素。
(3) 对这两个子数组进行快速排序

3、特点

快速排序的独特之处在于，其速度取决于选择的基准值

在最糟情况下，其运行时间为O(n2)。

平均情况下，快速排序的运行时间为O(nlogn)

最佳情况也是平均情况。只要你每次都随机地选择一个数组元素作为基准值，快速排序的平均运行时间就将为O(nlogn)。快速排序是最快的排序算法之一，也是D&C典范。

六、优先队列

1、数据结构

一个合适的数据结构应该支持两种操作： 删除最大元素和插入元素。这种数据类型叫做优先队列。

优先队列的使用和队列（删除最老的元素）以及栈（删除最新的元素）类似

2、排序方法

通过插入一列元素然后一个个地删掉其中最小的元素，我们可以用优先队列实现排序算法。

堆排序就是基于堆的优先队列的实现。

3、二叉堆

数据结构二叉堆能够很好地实现优先队列的基本操作。

在二叉堆的数组中，每个元素都要保证大于等于另两个特定位置的元素。

相应地，这些位置的元素又至少要大于等于数组中的另两个元素，以此类推

当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序

4、优先队列排序

我们可以把任意优先队列变成一种排序方法。

将所有元素插入一个查找最小元素的优先队列，然后再重复调用删除最小元素的操作来将它们按顺序删去。

用无序数组实现的优先队列这么做相当于进行一次选择排序

5、堆排序

堆排序可以分为两个阶段。

在堆的构造阶段中，我们将原始数组重新组织安排进一个堆中；

然后在下沉排序阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。