目录
排序的概念：
排序算法的实现：
插入排序：
希尔排序：
选择排序：
堆排序：
冒泡排序：
快速排序：
快速排序的基本框架：
1.Hoare法
2. 挖坑法
3.前后指针法
快排的优化：
1. 三数取中法选key
2. 小区间使用插入排序
优化代码：
常见问题：
归并排序：
总结：
结语：
排序的概念：
排序：
所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持 不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳 定的；否则称为不稳定的（稳定可以转换成不稳定的，不稳定不可以转换成稳定的）。
内部排序：
数据元素全部放在内存中的排序。
外部排序：
数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
常见的排序算法：
直接插入排序，希尔排序，选择排序，堆排序，冒泡排序，快速排序，归并排序。
排序算法的实现：
说明：由于swap函数经常出现，为了使文章更加整洁，这里给出源码，下文直接调用不在说明。
private static void swap(int[] array,int i,int j){
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
插入排序：
思路：在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
动图演示如下：
代码实现如下：
public static void insertSort(int[] array){
for(int i = 1;i = 0; j--){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
结果演示：
直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定
希尔排序：
思路：希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达 =1时，所有记录在统一组内排好序。
动图演示：
代码实现如下：
在shellSort里面确定组的大小，在shell里面进行排序，通过计算确定gap的关系，间隔运行，一次通过。
public static void shellSort(int[] array){
int gap = array.length;
while(gap > 1){
gap /= 2;
shell(array,gap);
}
}
public static void shell(int[] array,int gap){
for(int i = gap; i = 0;j -= gap){
if(array[j] > tmp){
array[j+gap] = array[j];
}else{
break;
}
}
array[j+gap] = tmp;
}
}
结果演示：
希尔排序的特性总结：
1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排 序的时间复杂度都不固定。
4. 稳定性：不稳定
选择排序：
思路：
（1）在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素。
（2）若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换。
（3）在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。
动图演示：
代码实现如下：
//选择排序
public static void selectSort(int[] array){
for(int i = 0;i
结果演示：
选择排序的特性总结 ：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
堆排序：
思路：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
动图演示：
代码实现如下：
从小到大用大根堆
从大到小用小根堆
下面代码为大根堆
public static void heapSort(int[] array){
createBigHeap(array);
int end = array.length-1;
while(end > 0){
swap(array,0,end);
siftDown(array,0,end);
end--;
}
}
private static void createBigHeap(int[] array){
for(int parent = (array.length - 1 -1)/2; parent >= 0; parent--){
siftDown(array,parent,array.length);
}
}
private static void siftDown(int[] array,int parent,int end){
int child = parent*2+1;
while(child array[parent]) {
swap(array, child, parent);
parent = child;
child = parent * 2 + 1;
} else {
break;
}
}
}
结果演示：
堆排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定
冒泡排序：
简单就不给思路了
动图演示：
代码实现如下：
public static void bubbleSort(int[] array){
for(int i = 0; i array[j+1]){
swap(array,j,j+1);
flg = true;
}
}
if(flg == false){
return;
}
}
}
结果演示：
冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定
快速排序：
思路：任取待排序元素序列中的某元 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
快速排序的基本框架：
//快排的框架
public static void quickSort(int[] array,int left,int right){
if(right i){
while(j > i && array[j] >= pivot){
j--;
}
while(j > i && array[i] i){
while(j > i && array[j] >= pivot){
j--;
}
array[i] = array[j];
while(j > i && array[i] 1);
if(array[left]
2. 小区间使用插入排序
思路：我们直到插入排序在数组接近有序时是非常快的，而快排最后在堆上调用的空间是非常大的，故在小区间上使用插入排序可以达到优化的效果。
代码如下：
//优化1
if(right - left +1 = right){
return;
}
for(int i = 1 + left;i = left;j--){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}
优化代码：
为节省文章长度，下面个代码在上面给出，下面我就不给总代码了（抱歉）。
public static void quickSort(int[] array,int left,int right){
if(right > 1);
mergeSort(array,left,mid);
mergeSort(array,mid+1,right);
merge(array,left,mid,right);
}
private static void merge(int[] array,int left,int mid,int right){
int s1 = left;
int s2 = mid + 1;
int e1 = mid;
int e2 = right;
int k = 0;
int[] tmpArr = new int[right - left + 1];
while(s1 
