内部排序（所有的排序流程都是在内存中完成）
插入排序
直接插入排序希尔排序选择排序
简单选择排序堆排序交换排序
冒泡排序快速排序归并排序
基数排序
外部排序（要用到内存和外存）
直接插入排序
例子：8,2,4,9,3,6 1）选定第一个数8，此时8是有序的 8 2,4,9,3,6 2）将2插到8的前面，此时2,8是有序的 2,8 4,9,3,6 3）将4插到8的前面，此时2,4,8是有序的 2,4,8 9,3,6 4）9的位置不变，此时2,4,8,9是有序的 2,4,8,9 3,6 5）将3插到4的前面，此时2,3,4,8,9是有序的 2,3,4,8,9 6 6）将6插到8的前面，此时全部都有序了 2,3,4,6,8,9 void Insertsort3(int a[], int n){ int i, j; for (i = 1; i < n; i++){ for (j = i - 1; j >= 0 && a[j] > a[j + 1]; j--){ Swap(a[j], a[j + 1]); } } }希尔排序（缩小增量排序）
按步长将序列分组，每个组组内进行插入排序首步长 = 数据总数 / 2后面的步长 = 当前步长 / 2 void shellsort3(int a[], int n){ int i, j, gap; for (gap = n / 2; gap > 0; gap /= 2){ for (i = gap; i < n; i++){ for (j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap){ Swap(a[j], a[j + gap]); } } } }简单选择排序
简单选择排序和直接插入排序类似，都将数据分为有序区和无序区
和插入排序的不同处：
直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区简单选择排序是从无序区选一个最小的元素直接放到有序区的最后。案例
源码
public int[] selectionSort(int[] A, int n) { for(int x = 0; x < n-1; x++){ //记录最小的那个值 int min = A[x]; //记录最小值所对应的索引 int min_index = x; //0~N-1，1~N-1，2~N-1.... for(int y = x+1; y < n; y++){ //循环找出最小的那个值及对应的索引 if(min > A[y]){ min = A[y]; min_index = y; } } //交换位置 if(min_index != x){ int t = A[x]; A[x] = min; A[min_index] = A[x]; } } return A; }堆排序
堆是一颗完全二叉树
堆必须满足以下条件：
所有父结点均小于等于它的两个叶子结点（小顶堆）
或者所有父结点均大于等于它的两个叶子结点（大顶堆）
对于结点i，i >= n/2 时，表示结点i为叶子结点
堆排序就是把一个序列不断的建堆再不断取堆顶点的一个过程
堆排序过程：
源码
package sort; /** * 堆排序 * * @author huangxj 2017年4月10日 * * @version v1.0 */ public class HeapSort { public static void main(String[] args) { // 输入数列 int[] data = new int[] { 34, 234, 2, 4, 45, 435, 12, 995, 32, 356, 2, 324 }; // 排序 sort(data); for (int i : data) { System.out.print(i + ","); } } public static void sort(int[] data) { // 获取结点个数 int dataNum = data.length; // 有多少个数就要构建多少次堆，最后一个只剩一个元素，可建可不建 for (int i = 0; i < dataNum - 1; i++) { // 第一次的话就要直接进行堆的构建操作 if (i == 0) { // 从倒数第一个非叶子结点处开始遍历到根结点，即第dataNum/2个结点，转换成数组的角标就是dataNum/2 - 1 for (int j = (dataNum / 2) - 1; j >= 0; j--) { // 将每遍历到的结点下面的子树转换成堆 adjustToMaxdHeap(data, dataNum, j); } } else { // dataNum-i表示断开完全二叉树中的最后一条边，0表示只需对根结点进行调整就行了 adjustToMaxdHeap(data, dataNum - i, 0); } // 将根结点和堆中的最后一个结点交换 swap(data, 0, dataNum - i - 1); } } /** * 将完全二叉树中以parent结点为根的子树调整成堆 * * @param data * 完全二叉树 * @param dataNum * 完全二叉树结点个数 * @param parent * 完全二叉树的某个子结点的角标 * * @author huangxj 2017年4月10日 * * @version v1.0 */ public static void adjustToMaxdHeap(int[] data, int dataNum, int parent) { // 结点parent的左子结点是(parent+1)*2 -1 = 2*parent + 1 int left = 2 * parent + 1; // 如果节点parent的左子结点存在的话 while (left < dataNum) { // 先记录左后子结点中较大的那一个为左子结点 int biggerChild = left; // 获得右子结点 int right = left + 1; // 如果右子结点存在并且右子结点的值大于左子结点的话 if (right < dataNum - 1 && data[right] > data[left]) { // 抛弃左子结点，将左后子结点中较大的那一个记录为右子结点 biggerChild = right; } // 如果当前结点小于其最大的子结点的话 if (data[parent] < data[biggerChild]) { // 互换两者的值 swap(data, parent, biggerChild); // 此时parent结点的位置是biggerChild的位置 parent = biggerChild; // 获取parent结点新的左子结点 left = 2 * parent + 1; } else { // 因为建堆时是从下往上遍历，所以当父结点的值最大的时，则表示以parent结点为根的子树已构建成堆 break; } } } /** * 交换位置 * * @author huangxj 2017年4月10日 * * @version v1.0 */ public static void swap(int[] data, int i, int j) { if (i == j || data[i] == data[j]) { return; } data[i] = data[i] ^ data[j]; data[j] = data[i] ^ data[j]; data[i] = data[i] ^ data[j]; } }冒泡排序
比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。例子：8,2,4,9,3,6 1）第一趟排序 8,2,4,9,3,6 2,8,4,9,3,6 2,4,8,9,3,6 2,4,8,9,3,6 2,4,8,3,9,6 2,4,8,3,6 9 2）第二趟排序 2,4,8,3,6 9 2,4,8,3,6 9 2,4,8,3,6 9 2,4,3,8,6 9 2,4,3,6 8,9 3）第三趟排序 2,4,3,6 8,9 2,4,3,6 8,9 2,3,4,6 8,9 2,3,4,6 8,9 2,3,4 6,8,9 源码public static void sort(int a[], int n) { for (int i = 0; i < n; i++) { for (int j = 1; j < n - i; j++) { if (a[j - 1] > a[j]) { swap(a[j - 1], a[j]); } } } }快速排序
快速排序的基本思想：
先从数列中随机取出一个数作为基准数。
将小于或等于它的数统一放到它的左边，比这个数大的数统一放到它的右边。
再对左右区间重复第二步，直到各区间只有一个数。
快速排序一次完整划分的过程：
源码：
package bear.sort; /** * 快速排序 * * @author huangxj 2017年4月16日 * * @version v1.0 */ public class QuickSort { public static void main(String[] args) { int[] data = new int[] { 34, 234, 2, 4, 45, 435, 12, 995, 32, 356, 2, 324 }; quickSort(data, 0, data.length - 1); for (int i : data) { System.out.print(i + ","); } } private static void quickSort(int[] data, int begin, int end) { // 区间只有一个数或区间没有数，则直接return if (begin >= end) { return; } // 选择第一个数为基数 int base = data[begin]; // 将基数和最后一个数交换 swap(data, begin, end); // 蓝色指针，指向小于等于区间的最后一位 int lessEnd = begin - 1; for (int i = begin; i <= end; i++) { // i是绿色指针 if (data[i] <= base) { // 当前数小于等于基数，则将它和区间的后一位数进行交换，同时并将区间向右扩充一位 lessEnd++; swap(data, i, lessEnd); } } quickSort(data, begin, lessEnd - 1); quickSort(data, lessEnd + 1, end); } /** * 将i和j上的数据对调 * * @author huangxj 2017年4月16日 * * @version v1.0 */ public static void swap(int[] data, int i, int j) { if (i == j || data[i] == data[j]) { return; } data[i] = data[i] ^ data[j]; data[j] = data[i] ^ data[j]; data[i] = data[i] ^ data[j]; } }归并排序
归并排序示意图如下：基数排序
先按个位排序，再按十位排序，最后按百位排序稳定排序：相同的数经过排序之后位置不变。
直接插入排序冒泡排序归并排序基数排序不稳定排序：相同的数经过排序之后位置变了。
希尔排序选择排序堆排序快速排序稳定排序的应用：
如果对某个数列的排序有多个指标，如要求序列先按年龄排序之后再按身高排序，那么此时就必须使用稳定排序才行，不然的话身高相同的两个人，经过不稳定排序算法进行排序之后，可能他们的顺序就没有按年龄进行排序了。各个排序算法性能对比表
