七种排序算法的实现
插入排序
直接插入排序
原理
整个区间被分为：有序区间 无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置进行插入。
1.取一个bound位置。【0，bound) 已排序区间 【bound,size)待排序区间。
2.先取bound位置的元素（初始值为0），往前面已排序区间插入。
3.插入完毕后已排序区间仍然有序。
4.把bound位置的元素在前面找到一个合适的位置，同时需要搬运相关元素。
代码实现
public static void insertSort(int[] array) {
//通过bound划分区域
for (int bound = 1; bound <array.length ; bound++) {
int v=array[bound];
int cur=bound-1;//已排序区间的最后一个元素下标
for (;cur>=0;cur--) {
if(array[cur]>v) {
array[cur+1]=array[cur];
array[cur]=v;
} else {
//此时已经找到合适位置
break;
}
}
array[cur+1]=v;
}
}
性能分析
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定排序
特点：
1.当待排序区间元素比较少的时候，排序效率比较高。
2.当整个数组比较接近有序的时候，排序效率也很高。
希尔排序
原理
进阶版本的插入排序
1.先分组
2.针对每组进行插入排序，逐渐缩小组的个数，最终整个数组就接近有序了。
代码实现
public static void shellSort(int[] array) {
int gap=array.length/2;
while (gap>1) {
inserSortgap(array,gap);
gap=gap/2;
}
inserSortgap(array,1);
}
public static void inserSortgap(int[] array, int gap) {
for (int bound = gap; bound <array.length ; bound++) {
int v=array[bound];
int cur=bound-gap;//已排序区间的最后一个元素下标
for (;cur>=0;cur-=gap) {//找相同组中相邻的元素 同组元素下标差值为gap
if(array[cur]>v) {
array[cur+gap]=array[cur];
array[cur]=v;
} else {
//此时已经找到合适位置
break;
}
}
array[cur+gap]=v;
}
}
性能分析
时间复杂度：理论极限O(n^1.3) ,按照size/2,size/4,…,1这种方式分组O(n*n)
空间复杂度：O(1)
稳定性：不稳定
选择排序
选择排序
原理
打擂台形式,每次从数组中找出最小值，然后把最小值放到合适的位置上。
代码实现
public static void selectSort(int[] array) {
for(int bound=0;bound<array.length;bound++) {
for (int cur=bound+1;cur<array.length;cur++) {
if(array[bound]>array[cur]) {
//交换
int tmp=array[bound];
array[bound]=array[cur];
array[cur]=tmp;
}
}
}
}
性能分析
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
堆排序
原理
升序排序：
1.把数组建立一个小堆，取出最小值放到另一个数组中。循环取堆顶元素尾插到新数组即可（缺陷，需要额外O(N)的空间）。
2.把数组建立一个大堆，把堆顶元素和堆的最后一个元素互换，把最后一个元素删除，再从堆顶向下调整。
代码实现
public static void heapSort(int[] array) {
//构建堆
createHeap(array);
//循环交换堆顶元素到最后，并调整堆
//循环length-1,当堆中只剩一个元素时，就一定是有序的
for(int i=0;i<array.length-1;i++) {
//交换堆顶元素与最后一个元素
//堆的元素相对与array.length-i
//堆的最后一个元素下标array。length-i-1；
swap(array,0,array.length-1-i);
//删除堆中最后一个元素
//堆大小就变为array。length-i-1；
//[0.array.length-i-i)待排序区间
//[array.length.i-1,size)已排序区间
shiftDown(array,array.length-i-1,0);
}
}
private static void createHeap(int[] array) {
//从最后一个非叶子节点出发向前循环，依次进行向下调整
for (int i = (array.length-1-1)/2; i>=0 ; i--) {
shiftDown(array,array.length,i);
}
}
private static void shiftDown(int[] array, int helpLength, int index) {
//升序排序，建立大堆
int parent=index;
int child=parent*2+1;
while (child<helpLength) {
if(child+1<helpLength&&array[child+1]>array[child]) {
child=child+1;
}
//此时child已经是左右子树比价的的值的下标
if(array[child]>array[parent]) {
swap(array,child,parent);
} else {
break;
}
parent=child;
child=parent*2+1;
}
}
private static void swap(int[] array, int i, int j) {
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
性能分析
时间复杂度：O(n*logn)
空间复杂度：O(1)
稳定性：不稳定
交换排序
冒泡排序
原理
代码实现
public static void bubbleSort(int[] array) {
for (int i = 0; i <array.length-1 ; i++) {
boolean flag=true;
for (int j = 0; j<array.length-i-1 ; j++) {
if(array[j]>array[j+1]) {
int tmp=array[j];
array[j]=array[j+1];
array[j+1]=tmp;
flag=false;
}
}
if(flag) {
break;
}
}
}
性能分析
时间复杂度:O(n^2)
空间复杂度：O(1)
稳定性：稳定
快速排序
原理（递归）
1.在待排序区间中，找到一个基准值（常见的可以取区间的第一个元素或者最后一个元素）
2.以基准值为中心，把整个区域整理成三部分：左侧部分元素的元素都小于等于基准值；右侧部分的元素都大于等于基准值。
3.再次针对左侧调整好的区间和右侧整理好的区间，进一步进行递归，重复刚才的整理过程。
代码实现
public static void quickSort(int[] array) {
quickSortHelper(array,0,array.length-1);
}
private static void quickSortHelper(int[] array, int left, int right) {
if(left>=right) {
//区间有0个元素或者1个元素，此时不需要排序
return;
}
//针对[left,right]区间进行整理
//index返回值就是整理完毕后，left和right重合位置
int index=partition(array,left,right);
quickSortHelper(array,0,index-1);
quickSortHelper(array,index+1,right);
}
private static int partition(int[] array, int left, int right) {
int i=left;
int j=right;
int base=array[right];//取最右侧为基准值
while (i<j) {
//从左往右找比基准值大的值
while (i<j&&array[i]<=base) {
i++;
}
//上边循环结束，i要么与j重合，或者i指向的值大于base
//从右往左找比基准值小的值
while (i<j&&array[j]>=base) {
j--;
}
//上边循环结束，i要么与j重合，或者j指向的值小于base
//交互i 与 j 的值
swap(array,i,j);
}
//当i与j重合时候，最后一步，要把重合位置的元素与基准值进行交换
swap(array,i,right);
return i;
}
private static void swap(int[] array, int i, int j) {
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
性能分析
时间复杂度:O(n^2)
空间复杂度:O(n)
稳定性:不稳定
归并排序
归并排序
原理
基本思路来源与一个经典问题：把两个有序链表/数组合并成一个。
代码实现
//[left,mid）有序区间
//[mid,right)有序区间
public static void merge(int[] array,int low,int mid,int high) {
int[] output=new int[high-low];
int outputIndex=0;//记录output放入多少个元素
int cur1=low;
int cur2=mid;
while (cur1<mid&&cur2<high) {
if(array[cur1]<=array[cur2]) {
output[outputIndex]=array[cur1];
outputIndex++;
cur1++;
} else {
output[outputIndex]=array[cur2];
outputIndex++;
cur2++;
}
}
//当上面循环结束的时候，肯定是cur1或者cur2其中一个先到达末尾，将另一个剩下的部分直接拷贝到output中
while (cur1<mid) {
output[outputIndex]=array[cur1];
outputIndex++;
cur1++;
}
while (cur2<high) {
output[outputIndex]=array[cur2];
outputIndex++;
cur2++;
}
//将output中元素放回原来数组zhong
for (int i = 0; i <high-low ; i++) {
array[low+i]=output[i];
}
}
public static void mergeSort(int[] array) {
mergeSortHelper(array,0,array.length);
}
private static void mergeSortHelper(int[] array, int low, int high) {
if(high-low<=1) {
return;
}
int mid=(low+high)/2;
mergeSortHelper(array,low,mid);
mergeSortHelper(array,mid,high);
//当把左右区间已经归并排序完，说明左右区间已经有序了；
//接下来针对两个有序区间进行合并
merge(array,low,mid,high);
}
性能分析
时间复杂度：O(nlogn)
空间复杂度：O(n)
稳定性：稳定
特点：可以适用于外部排序，也可以适用于链表排序。
总结
