有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。 插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
代码实现：
public void insertSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 1; i < array.length; i++) {
// 当前比较节点的下标
int index = i;
// 当前节点值
int curr = array[i];
// 当前节点值小于前一结点要交换位置
while (index > 0 && curr < array[index - 1]) {
array[index] = array[--index];
}
array[index] = curr;
}
}由于插入算法每次都需要往前遍历，最好情况下，所有元素都有序，其时间复杂度为O(n)，最坏情况下为O(n^2)，所以其时间复杂度为O(n^2)。
由于插入算法没有破坏相同值的相对位置，因此具有稳定性
代码实现：
冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。
public static void bubbleSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
boolean isSorted = true;
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j + 1] < array[j]) {
isSorted = false;
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
if (isSorted) {
return;
}
}
}由于冒泡法排序需要两趟遍历，故其时间复杂度为O(n^2)。
由于在冒泡过程中，相邻两个位置如果值相同，是不会进行交换的，没有破坏相同值的相对位置，因此具有稳定性
选择排序法是对冒泡排序法的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。
简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。
代码实现：
public void selectionSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
for (int i = 0; i < array.length; i++) {
// 保存本次遍历最小值的下标
int minIndex = i;
for (int j = i + 1; j < array.length; j++) {
minIndex = array[minIndex] < array[j] ? minIndex : j;
}
// 将最小值放到最前面
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = array[minIndex];
}
}由于选择法排序需要两趟遍历，故其时间复杂度为O(n^2)。
举个例子：
假设现在的数组元素顺序为 5 8 5 2 9
在进行第一遍选择的时候会将最小值2选择出来与第一个位置的5进行交换，破坏了原来两个5之间的相对位置
由于在选择过程中，可能会破坏原有同值元素的相对位置，因此不具有稳定性
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组。
代码实现：
public void shellSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
// 插入间隔从数组长度一半开始，每次除以二，直至间隔为1
for (int gap = array.length >> 1; gap >= 1; gap >>= 1) {
for (int i = 0; i < array.length; i++) {
// 保存当前操作数下标
int index = i;
// 保存当前值
int curr = array[i];
while (index >= gap && array[index - gap] > curr) {
array[index] = array[index - gap];
index -= gap;
}
array[index] = curr;
}
}
}希尔排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快O(n(logn)),因此中等大小规模表现良好
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。
代码实现：
public static void mergeSort(int[] array, int start, int end) {
if (start >= end) {
return;
}
int mid = (start + end) >> 1;
mergeSort(array, start, mid);
mergeSort(array, mid + 1, end);
merge(array, start, mid, end);
}
private static void merge(int[] array, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int l = start, r = mid + 1;
for (int i = 0; i < temp.length; i++) {
if (l <= mid && r <= end) {
temp[i] = array[l] > array[r] ? array[r++] : array[l++];
} else if (l > mid) {
temp[i] = array[r++];
} else {
temp[i] = array[l++];
}
}
for (int num : temp) {
array[start++] = num;
}
}归并排序比较占用内存，但却是一种效率高且稳定的算法。其时间复杂度为O(nlog(n))
合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
快速排序（Quicksort）是对冒泡排序的一种改进。 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
代码实现：
public static void quickSort(int[] array, int start, int end) {
if (array == null || end <= start) {
return;
}
int pos = partition(array, start, end);
quickSort(array, start, pos - 1);
quickSort(array, pos + 1, end);
}
private static int partition(int[] array, int start, int end) {
int temp = array[start];
int i = start, j = end;
while (i < j) {
while (i < j && array[j] > temp) {
j--;
}
while (i < j && array[i] <= temp) {
i++;
}
if (i < j) {
swap(array, i, j);
}
}
swap(array, start, i);
return i;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}快速排序的平均时间复杂度为O(nlogn)。
举个例子：
例如 5 3A 6 3B ，对这个进行排序，排序之前相同的数3A与3B，A在B的前面，经过排序之后会变成 3B 3A 5 6 ，所以说快速排序是一个不稳定的排序
在介绍堆排序之前，首先需要说明一下，堆是个什么玩意。
堆是一棵顺序存储的完全二叉树。
其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整;
代码实现：
public static void heapSort(int[] array) {
if (array == null || array.length < 2) {
return;
}
int len = array.length;
// 构建一个大根堆，从第一个非叶子结点开始往前依次调整
for (int i = (len - 2) / 2; i >= 0; i--) {
adjust(array, i, len);
}
// 循环将大根堆首位(最大)与末位交换，最终得到的数组即为排序树组
while (--len > 0) {
swap(array, 0, len);
adjust(array, 0, len);
}
}
// 进行大根堆的调整
private static void adjust(int[] array, int index, int len) {
// 定位到index节点的左子树
int j = index * 2 + 1;
// 左子树不存在
if (j >= len) {
return;
}
// j为左右子节点中最大的
j = (j + 1 < len && array[j + 1] > array[j]) ? j + 1 : j;
// 保证父节点最大
if (array[index] < array[j]) {
swap(array, index, j);
adjust(array, j, len);
}
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}堆排序的平均时间复杂度为O(nlogn)。
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
list.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop().right;
}
return list;
}public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
list.add(node.val);
node = node.right;
}
return list;
}public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
// 上一次访问的节点
TreeNode pre = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.peek();
// 如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时，当前结点出栈
if ((curr.left == null && curr.right == null)
|| (pre != null && (pre == curr.left || pre == curr.right))) {
pre = curr;
res.add(stack.pop().val);
} else {
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
}
}
return res;
}/**
* 朴素字符串匹配算法
*
* @param str 文本串
* @param dest 模式串
* @return 起始下标
*/
public static int kmp(String str, String dest) {
int[] next = next(dest);
for (int i = 0, j = 0; i < str.length(); i++) {
while (j > 0 && str.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
if (str.charAt(i) == dest.charAt(j)) {
j++;
}
if (j == dest.length()) {
return i - j + 1;
}
}
return -1;
}
/**
* 计算最长公共前后缀长度数组
*
* @param dest 模式串
* @return int[]
*/
private static int[] next(String dest) {
int[] next = new int[dest.length()];
for (int i = 1, j = 0; i < dest.length(); i++) {
while (j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
next[i] = j;
}
return next;
}