排序思想分类
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。（大部分排序算法）
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序（计数排序、桶排序、基数排序）
n²三兄弟
一、冒泡排序（简单交换排序）
用两个指针遍历数组，比较，让较大的数移动到后面 每遍历一次，就能将一个最大的数移动到数组末尾二、选择排序
两个指针，一个固定指开头，一个遍历数组 每遍历一次，将最小一个放到开头，头指针后移三、插入排序
一个指针，指向未排序的元素，遍历往前找合适的位置插入 插入：塞进去，后面的全部后移nlogn排序
基本都用了分治思想四、希尔排序（间隔分组插排）
1959年Shell发明，是第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。 又称为分组插入排序、递减增量排序 是插入排序的改进版，但是一种非稳定排序算法 根据插入排序特性：插入排序在对几乎已经排好序的数据操作时，效率高，可以达到线性（O(n)）的效率 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位1.间隔分组，通常为总长度的一半
如总长度为8，则初始间隔取4，每4个数连一条线，分为一组2.组内排序
3.重新设置间隔分组，为前一次分组的一半
4.再次组内排序
对每一组内位置进行简单插入排序5.再次分组，间隔为一，则对整组进行简单插入排序
时间复杂度：最坏情况下为O(n^2)，平均时间复杂度为O(nlogn)；术语讲解：每次的分组间隔术语称之为“增量”
既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。五、归并排序
详见：
把长度为n的输入序列分成两个长度为n/2的子序列； - 对这两个子序列分别采用归并排序； - 将两个排序好的子序列合并成一个最终的排序序列。 递归地把序列拆为子序列 拆到每个子序列只有一个元素了（原子化）就开始合并 将子序列进行有序合并（双指针）function mergeSort(arr) //拆分
{
var len = arr.length;
if (len < 2) //直到拆到只有一个元素为止,返回
{
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right)); //递归地拆，然后一层层合并上去
}
function merge(left, right) //双指针合并有序序列
{
var result = [];
while (left.length>0 && right.length>0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) //处理余下序列，直接塞入结果序列中
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}六、快速排序(中间冒泡排序)
核心思想：先确定序列中间元素的位置 将合适的数位置移动到中间，减少移动路程 (冒泡排序是移动到数组一端，预计路程较长) 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 算法描述 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下： 核心：递归地排序基准左右两边的序列- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
function quickSort(arr, left, right)
{
var len = arr.length,
partitionIndex,
left = typeof left != 'number' ? 0 : left, //防止left和right超出数组边界
right = typeof right != 'number' ? len - 1 : right;
if (left < right)
{
partitionIndex = partition(arr, left, right); //分割并获取基准下标
quickSort(arr, left, partitionIndex-1); //排序 基准左边 序列
quickSort(arr, partitionIndex+1, right); //排序 基准右边 序列
}
return arr;
}
function partition(arr, left ,right) // 分区操作(双指针, 存放指针+遍历指针)
{
var pivot = left, // 设定最左边为 基准（pivot）
index = pivot + 1; //从基准的下一个作为遍历起点
for (var i = index; i <= right; i++)
{
if (arr[i] < arr[pivot]) //遍历序列，比基准小的都往前移
{
swap(arr, i, index);
index++; //小于基准的数的存放指针
}
}
swap(arr, pivot, index - 1); //把基准移动到存放指针 ( 小于基准的序列的末尾 )
return index-1;
//分割完毕后，基准左边都小于基准，基准右边都大于基准
}
function swap(arr, i, j) //交换函数
{
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}七、堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 堆排序算法建立在 堆数据结构 的基础上 将输入数组建立为一个 大顶堆（最大堆），反复取出堆顶逆序排列 (最先取出的放在最后) ，并对剩余元素重建大顶堆，即可将原数组从小到大排列完成排序。 【一个一个放进最大堆，再一个一个地取出完成排序】 一个直接的想法是在原数组之外新建一个数组保存每次取得的堆顶，这样会有 O(n) 的空间开销，可以用一种称作 「原地堆排序」 的技巧避免此开销，具体做法如下。 首先将原待排序数组 arr[]建立为一个大顶堆。 交换堆顶和当前未排序部分中最末尾元素，则堆顶元素已排序（此时在数组最末尾）。 剩余元素中 只有当前堆顶 (上一步被交换的末尾元素) 可能造成 堆失序，因此只需对堆顶调用一次调整堆序的下滤 (siftDownsiftDown) 操作 (操作范围为未排序部分) ，即可恢复未排序部分的堆序。 重复 2，3 直到所有元素已排序，返回 arr[] 。 上述通过交换堆顶与当前未排序部分末尾元素的做法，避免了额外的空间开销，即 原地堆排序，程序结束后返回的 arr[]arr[] 为已排序状态。 稳定性：不稳定。 交换可能会破坏稳定性。例：输入数组 \{1, 2_{red}, 2_{green}\}{1,2 red,2 green} ，灰色表示已排序。排序后最终为 \{1, 2_{green}, 2_{red}\}{1,2 green,2 red} ,可以看到2_{red}2red和 2_{green}2 green的相对顺序相比输入已改变。步骤1.堆化 (heapify)
将数组变为最大堆 将原输入数组看作一棵 完全二叉树(Complete Binary Tree) 。根节点下标为 0，于是根据完全二叉树的结构性质，任意一个节点 (下标为 i) 的左子节点下标为 2 * i + 1，右子节点下标为 2 * i + 2，父节点下标为 (i-1) / 2。 堆化过程即使得整棵树满足堆序性质，也即任意一个节点大于等于其子节点（大顶堆）。 父→子公式（已知父下标为i）：左子节点下标 = 2 * i + 1，右子节点下标 = 2 * i + 2 子→父公式（已知子下标为i）：父节点下标 = (i-1) / 2下滤方法(siftDown)
下滤 (siftDown) 是堆排序的核心方法，在堆排序中的如下两种操作中调用： 排序开始时 创建最大堆 的堆化方法 每次排序取走堆顶时用于 恢复未排序部分的堆序时间复杂度
原地堆排序的时间复杂度为 O(nlogn)。 最好 / 平均 / 最坏时间复杂度均为 O(nlogn) 建堆时间复杂度: O(n) 因为是原地算法，空间复杂度为O(1)，不需要额外空间 当前堆顶通过交换完成排序时，其下滤次数取决于当前树高 设当前未排序元素个数为 ii ，其下滤次数最多为层高减1 (根节点为第1层) ，可估计为 logilogi。每排序一次堆顶，待排序部分元素个数减1，于是从一个大顶堆开始完成排序所需时间取决于 n - 1n−1 次堆顶下滤 (下滤范围分别为 n, n -1, n-2,...,1n,n−1,n−2,...,1 ) 次数总和最大值 (实际上只剩一个元素时排序已经完成，对于最后一个元素无需下滤，不过考虑到 log1=0log1=0 并不影响结果，因此 ii 仍从 1 开始)。代码实现
#include<iostream>
using namespace std;
void sw(int &a,int &b)
{
int temp = a;
a = b;
b = temp;
}
// arr[]为完全二叉树层序遍历得到的数组
// n为完全二叉树的节点，即数组长度
// i为待维护的节点
void heapify(int arr[], int n, int i) //下滤函数 参数:数组、数组边界下标、当前树顶下标
{
//前提条件：除 i与 i下方这两层外，下方已完全堆化
//找到树中最大元素，并将其移动到顶端
if (i >= n) return; //递归出口:堆化到数组最后一个元素
int largest = i;
int lson = i * 2 + 1; //左子节点
int rson = i * 2 + 2; //右子节点
if (lson < n && arr[largest] < arr[lson])
{ //和左子节点数值比较，找到最大节点，赋值下标
largest = lson;
}
if (rson < n && arr[largest] < arr[rson])
{ //和右子节点数值比较，找到最大节点，赋值下标
largest = rson;
}
if (largest != i)
{ //如果树中最大元素和顶端的不一样，那么交换二者的数值，将最大节点移动到顶端
swap(arr[largest], arr[i]); //找到的最大值换上来，原堆顶换下去
heapify(arr, n, largest); //对换下去的数再进行堆化判断
//进行一个递归，因为在原堆顶换下去之后，无法保证下面的堆序
}
}
void heap_sort(int arr[], int n) //堆排序函数 参数：原始数组 数组size
{
//建堆，将原数组堆化
int lastNode = n - 1;
int parent = (lastNode - 1) / 2; //找到最后一个节点的父节点，即最后一个非叶节点
for (int i = parent; i >= 0; i--) //从后往前堆化
{
heapify(arr, n, i); //二层树堆化函数
}
//堆排序，取出堆顶放到数组末尾，然后再堆化
for (int i = n - 1; i >= 0; i--)
{
sw(arr[i], arr[0]); //把取出的堆顶放数组末尾，最后形成从小到大的有序数组
heapify(arr, i, 0); //堆化，将换上来的原末尾元素移动（下滤）到合适位置
}
}
int main()
{
int arr[5] = { 5,4,3,2,1 };
heap_sort(arr, sizeof(arr) / sizeof(arr[0])); //调用堆排序
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
cout << arr[i] << endl;
}
return 0;
}