## 插入排序

1. 初始状态 $a\left[0\right]$ 为有序序列，其余为待排序。
2. 选出待排序中第一个数字 $x$，在有序序列中找出 $y$，使得 $x < y$，则交换两者。
3. 对待排序序列中每一个数都进行步骤 2。

## 希尔排序

1. 按照步长划分子序列。
2. 对每个子序列进行插入排序。
3. 步长减半，重复 1、2 直到步长等于 1。

### 时间复杂度

$\frac{n}{2^i}$ $O\left(n^2\right)$
$2^k - 1$ $O\left(n^{\frac{3}{2}}\right)$
$2^i3^j$ $O\left(n\log^2n\right)$

## 选择排序

1. 初始状态 $a\left[0\right]$ 为有序序列，其余为待排序。
2. 在待排序 $a\left[i, \dots, n-1\right]$ 中找出最大的元素与 $a\left[i\right]$ 交换。
3. 重复步骤 2，直到 $i = n-1$

## 堆排序

$i$ 节点 $a\left[i\right]$ 的左孩子为 $a\left[2i+1\right]$
$i$ 节点 $a\left[i\right]$ 的右孩子为 $a\left[2i+2\right]$
$i$ 节点 $a\left[i\right]$ 的父亲为 $a\left[\left \lfloor \frac{i-1}{2}\right \rfloor \right]$

### 调整堆

1. 假设堆中还有 $m$ 个元素。将堆顶元素与堆中最后一个元素互换，然后剩下 $m-1$ 个元素。
2. 找出根节点左右孩子较大的一个。
3. 与较大的孩子互换。
4. 对被交换的孩子所在的子树进行 1、2、3 步骤，一直到叶子节点。

### 初始化堆

1. $n$ 个节点的堆中最后一个非叶子节点为第 $\frac{n}{2}$，下标为 $\frac{n}{2} - 1$
2. 从最后一个非叶子节点往前逐步调整堆。
3. 重复步骤 2 直到根节点。

## 冒泡排序

1. 从左开始比较相邻元素 $x$$y$，如果 $x > y$ 就交换两者，直到最后一个元素。
2. 重复步骤 1，直到 $n$ 次最大元素都移动到最右边。

## 快速排序

1. 从最左边挖出基准数 $a\left[i\right]$
2. 由右往左找出比它小的数字填进去，这时候产生新的坑 $a\left[j\right]$
3. 由左往右找出比它大的数字填进去，产生新的坑。
4. 重复步骤 2、3 直到 $i = j$，然后把基准数填入即可。

### 时间复杂度

\begin{aligned} C\left(n\right) &= n - 1 + \frac{1}{n}\sum_{i=0}^{n-1}\left(C\left(i\right) + C\left(n-i-1\right)\right) \\ &= 2n\ln n = 1.39n\log _2 n \end{aligned}

## 归并排序

1. 将原始数组分成 $n$ 个单位 1 的序列，然后两两合并成单位 2 的序列。
2. 按照 2 的倍数进行比较合并，直到整个序列有序。

## 桶排序

1. 先扫描一遍求出最大值 max 和最小值 min，设桶的个数为 k，那么把区间 [min, max] 均匀划分成 k 个区间，每个区间就是一个桶。
2. 对桶内每个元素进行排序。
3. 将桶中元素合并成总的有序序列。

### 实现

First Missing Positive

Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3,and [3,4,-1,1] return 2. Your algorithm should run in $O\left(n\right)$ time and uses constant space.

### 时间复杂度

$O\left(n\right) + O\left(m\right)O\left( \frac{n}{k} \log \left( \frac{n}{k} \right)\right) = O\left(n+n\log \left(\frac{n}{k}\right)\right) = O\left(n+n\log n - n\log k\right)$

## 基数排序

1. 将待排序的整数（必须非负整数）统一为位数相同的整数，位数少的前面补零。所以前提要找到最大值，得到最长位数，然后设 k 进制下最长的位数为 d。
2. 从最低位开始，依次往高位进行稳定排序

### 实现

Maximum Gap

Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. Return 0 if the array contains less than 2 elements. You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

## 计数排序

1. 把当前值减去 min 作为下标，改下标对应的计数器加 1。
2. 扫描一边，把各个值收集起来。

### 实现

H-Index

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index. According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.” For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.