0.总结
常用的八种排序算法的时间、空间复杂度和稳定性总结如下：
下面我们分别介绍下每种算法的排序思路以及java的实现方法。
1.冒泡排序
1.1 基本思想：
设数组的长度为N：
（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
（2）这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就“沉”到数组第N-1个位置。
（3）N=N-1，如果N不为0就重复前面二步，否则排序完成。
1.2 代码实现：
我们可以很快想到一种最简便的排序方法：
public static void bubbleSort1(int[] array, int N) {
int temp = 0;
for (int i = 0; i < array.length; i++) {
for (int j = i; j < array.length; j++) {
if (array[i] > array[j]) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
}
但是这种方法不好啊，原因就是最大的一个数据就“沉”到数组第N-1个位置，下一次就不需要再将待排序的数据与之比较，而且，如果一个本身有序的序列，或者序列后面一大部分都是有序的序列，这种冒泡算法还在执行。
那怎么办呢？有两点可以改进：
（1）每次排序，都会排除一个元素，所以每次循环都将队尾元素剔除出排序的序列。
（2）设置一个标志位，如果从第一个到队尾的元素都没有发生交换，则可认为已经排完序。
public static void bubbleSort2(int[] array, int N) {
int temp = 0;
Boolean flag = false;//设置一个标志，如果这一趟发生了交换，则为true，否则为false。明显如果有一趟没有发生交换，说明排序已经完成。
for (int i = array.length-1; i > 0; i--) {
flag = false;
for (int j = 0; j < i; j++) {
count++;
if (array[j] > array[j+1]) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
flag = true;
}
}
if(flag == false) {
break;
}
}
}
利用数组 {1, 1, 2, 0, 9, 3, 12, 7, 8, 3, 4, 65, 22}测试发现，将两种方法一对比，方法一执行了91遍，方法二执行了50遍。
2.插入排序
2.1 基本思想：
从数组的第二个元素开始循环，将选中的元素与之前的元素一一比较，如果选中的元素小于之前的元素，则将之前的元素后移，最后再将选中的元素放在合适的位置。在这个算法执行的过程中，总是保持着索引i之前的数组是升序排列的。
2.2 代码实现：
public static void insertSort(int[] array, int N) {
int i,j, temp = 0;
for ( i = 1; i < array.length; i++) {//从数组的第二个元素开始循环
temp = array[i];//选中的元素
for ( j = i; j > 0 && array[j - 1] > temp; j--) {//上一个元素是否大于选中的元素,
array[j] = array[j - 1]; //如果选中的元素大于之前的元素，则将之前的元素后移
}
array[j] = temp;//再将选中的元素放在合适的位置
}
}
冒泡排序和插入排序的排序方法他的平均时间复杂度都是Ω（n2）（Ω表示算法下届），为什么呢，主要是它们都是只交换相邻元素，而且每次只消除一个逆序对，那怎么才能提高效率呢？两个办法
（1）每次不止消除一个逆序对
（2）每次交换可以相隔更远
3.希尔排序
3.1 基本思想
在直接插入排序的基础上进行的优化，每次交换可以相隔更远。其步骤大概分为两步：
（1）先选取一个小于n的整数d（步长），然后按照步长d将待排序序列分为d组，从第一个记录开始间隔为d的为一个组；
（2）然后对各组内进行直接插入排序，一趟过后，间隔为d的序列有序，随着有序性的改善，减少步长d重复进行 ，直到d=1。
3.2 代码实现：
public static void shellSort(int[] array, int N) {
int i, j, D, temp = 0;
for (D = N / 2; D >= 1; D /= 2) {//步长
for (i = 1; i < array.length; i++) {// 从数组的第二个元素开始循环
temp = array[i];// 选中的元素
for (j = i; j >= D && array[j - D] > temp; j-= D) {// 上一个元素是否大于选中的元素,
array[j] = array[j - D]; // 如果选中的元素大于之前的元素，则将之前的元素后移
}
array[j] = temp;// 再将选中的元素放在合适的位置
}
}
}
4.选择排序
4.1 基本思想
在直接插入排序的基础上进行的优化，每次不止消除一个逆序对，其步骤人如下：
（1）对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；
（2）接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。
4.2 代码实现：
public static void selectSort(int[] array, int N) {
int i, j = 0;
for (i = 0; i < array.length; i++) {
int k = i;
//找到最小值的下标
for (j = k + 1; j < array.length; j++) {
if (array[j] < array[k]) {
k = j;
}
}
//如果最小值不是array[i],将最小值和与array[i]交换。
if (k != i) {
int temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
简单选择排序是从n个记录中找出一个最小的记录，需要比较n-1次。但是这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。
5.堆排序
5.1 基本思想
堆排序是选择排序的一种升级，它的方法步骤如下：
（1）将待排序的序列构造成一个大顶堆。（整个序列的最大值就是堆顶的根节点）
（2）将它移走(其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值)
（3）将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次最大值。如此反复执行，就能得到一个有序序列了。
- 什么是堆？
堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆。
5.2 java代码
private static void heapSort(int[] arr) {
int len = arr.length - 1;
// 步骤1：堆构造 只要从非叶子节点开始
for (int i = len / 2 - 1; i >= 0; i--) {
heapAdjust(arr, i, len);
}
while (len >= 0) {
// 步骤2：将堆顶元素与尾节点交换后，长度减1，尾元素最大
swap(arr, 0, len--);
// 步骤3：再次对堆进行调整
heapAdjust(arr, 0, len);
}
}
/*
* 参数1：数组 参数2：当前元素 父节点编号 参数3：数组长度
*
*/
public static void heapAdjust(int[] arr, int i, int len) {
int left, right, j;
while ((left = 2 * i + 1) <= len) {// 判断当前父节点有无左节点（即有无孩子节点，left为左节点）
right = left + 1; // 右节点
j = left; // j指向左节点
if (j < len && arr[left] < arr[right]) // 右节点大于左节点
j++; // 当前把"指针"指向右节点
if (arr[i] < arr[j]) // 将父节点与孩子节点交换
swap(arr, i, j);
else // 说明比孩子节点都大，直接跳出循环语句
break;
i = j;// 当前元素指向j，指向左子节点，子节点如果还有叶子节点的话 还要向下比较，不然就不是真正的最大堆
}
}
public static void swap(int[] arr, int i, int len) {
int temp = arr[i];
arr[i] = arr[len];
arr[len] = temp;
}
6.归并排序
6.1基本思想
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列之间有序。将两个有序数组合并成一个有序数组，称为二路归并(binary merge)。
简而言之，就是如下图所示的过程：
6.2 java代码
- 1.对于两个有序的数组，要将其合并为一个有序数组，我们可以很容易地写出如下代码：
/**
* 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
*
* @param data 数组对象
* @param left 左数组的第一个元素的索引
* @param right 右数组最后一个元素的索引
* @param rightEnd 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
*/
public static void merge(int[] data, int left, int right, int rightEnd) {
// 临时数组
int[] tmpArr = new int[data.length];
// 左边终点位置
int leftEnd = right - 1;
// 缓存左数组第一个元素的索引
int tmp = left;
int elementsNum = rightEnd - left + 1;
while (left <= leftEnd && right <= rightEnd) {
// 从两个数组中取出最小的放入临时数组
if (data[left] <= data[right]) {
tmpArr[tmp++] = data[left++];
} else {
tmpArr[tmp++] = data[right++];
}
}
// 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
while (left <= leftEnd) {
tmpArr[tmp++] = data[left++];
}
while (right <= rightEnd) {
tmpArr[tmp++] = data[right++];
}
for (int i = 0; i < elementsNum; i++, rightEnd--) {
data[rightEnd] = tmpArr[rightEnd];
}
}
2.如果A,B无序，怎么办呢？可以把它们再分成更小的数组。如此一直划分到最小，每个子数组都只有一个元素，则可以视为有序数组。
3.从这些最小的数组开始，逆着上面的步骤合并回去，整个数组就排好了。
总而言之，归并排序就是使用递归，先分解数组为子数组，再合并数组。
/**
* 递归实现归并排序
*
* @param data 数组对象
* @param left 左数组的第一个元素的索引
* @param rightEnd 左数组的最后一个元素的索引，center+1是右数组第一个元素的索引
*/
public static void sort(int[] data, int left, int rightEnd) {
if (left < rightEnd) {
// 找出中间索引
int center = (left + rightEnd) / 2;
// 对左边数组进行递归
sort(data, left, center);
// 对右边数组进行递归
sort(data, center + 1, rightEnd);
// 合并
merge(data, left, center + 1, rightEnd);
print(data);
}
}
递归实现的归并排序算法稳定，但是需要额外的存储空间才能实现，如果使用的是数组需要O(n)的额外空间，链表需要O(log(n))的额外空间。
