[TOC]  ## 冒泡排序 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。  ## 选择排序 选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。  ## 插入排序 插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。  ## 快速排序 1. 从数列中挑出一个元素，称为 “基准”（pivot）； 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作； 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 ``` public class QuickSort { public static void quickSort(int[] arr,int low,int high){ int i,j,temp,t; if(low>high){ return; } i=low; j=high; //temp就是基准位 temp = arr[low]; while (i<j) { //先看右边，依次往左递减 while (temp<=arr[j]&&i<j) { j--; } //再看左边，依次往右递增 while (temp>=arr[i]&&i<j) { i++; } //如果满足条件则交换 if (i<j) { t = arr[j]; arr[j] = arr[i]; arr[i] = t; } } //最后将基准为与i和j相等位置的数字交换 arr[low] = arr[i]; arr[i] = temp; //递归调用左半数组 quickSort(arr, low, j-1); //递归调用右半数组 quickSort(arr, j+1, high); } public static void main(String[] args){ int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19}; quickSort(arr, 0, arr.length-1); for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } } } ``` ## 归并排序 1. 把长度为n的输入序列分成两个长度为n/2的子序列； 2. 对这两个子序列分别采用归并排序； 3. 将两个排序好的子序列合并成一个最终的排序序列。  ## 堆排序 1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆 2. 将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn) 3. 对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换 4. 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。   ## java API 排序算法 Arrays.sort -> DualPivotQuicksort TimSort算法和双指针快速排序。 首先强调一下，这是个**稳定**的排序算法 看过代码之后觉得这个算法没有想象的那么难。逻辑很清晰，整个算法最大的特点就是充分利用数组中已经存在顺序。在归并的过程中有一个 Galloping Mode(翻译过来可以叫 飞奔模式)，这是整个排序算法中最不寻常的地方。简单的理解就是，归并过程中有两个数列，比较的时候，有个数列连续有{MIN\_GALLOP}个元素都比另一个数列的第一个元素小，那就应该数一下后面到底还有多少个元素比另一个数列的第一个元素小。数完之后一次copy过去，减少copy的次数。MIN\_GALLOP还是一个可以动态调整的值，这应该是统计优化的结果。 ## 参考资料 [读 Java TimSort算法 源码 笔记](https://www.jianshu.com/p/10aa41b780f2) [DualPivotQuickSort 双轴快速排序 源码 笔记](https://www.jianshu.com/p/6d26d525bb96) [十大经典排序算法最强总结](https://blog.csdn.net/hellozhxy/article/details/79911867) [排序六 堆排序](https://www.cnblogs.com/jingmoxukong/p/4303826.html)