1.插入排序
思想：拿一个元素和它相邻前面的元素相比较，如果比这个元素小，那么就不动，如果比它大那么就交换位置。利用这种思想，我们先拿第二个元素与第一个元素相比较，比较完后，前两个就是有序的，然后再拿第三个与前两个相比，前三个就是有序的，以此类推，一直到arr.lenth的元素与前arr'.lenth-1个元素相比较。那么前arr.lenth的元素都是有序的。
代码如下：
public static void sort1(int []arr){
int i = 1;
while(i< arr.length) {
int j = i - 1;
int tmp = arr[i];
while(j>=0&&arr[j] > tmp){
arr[j+1] = arr[j];
arr[j] = tmp;
j--;
}
i++;
}
}
时间复杂度
最好：O(n)
平均：O(n^2)
最坏：O(n^2)
空间复杂度：O(1)
稳定性：稳定
特点：插入排序，初始数据越接近有序，时间效率越高。
2.希尔排序
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个步长，把数据隔步长分为几个组，先在这几个组中把数据进行排序好，然后缩小步长，重复上述操作，当步长为1时，进行排序这段数据就是有序的了。
希尔排序可以看为改进版的直接插入排序，因为插入排序，初始数据越接近有序，时间效率越高，所以我们想先分组把它排得大概有序，然后再当步长为1时，就是直接插入排序，然后进行排序。这样时间复杂度可降低。
public static void headle_gap(int[]arr){
int gap=arr.length;
while(gap>1){
gap=gap/3+1;
sort2(arr,gap);
}
}
public static void sort2(int []arr,int gap){
for (int i = gap; i < arr.length; i++) {
int j=i;
j-=gap;
int tmp=arr[i];
while(arr[j]>tmp&&j>=0){
arr[j+gap]=arr[j];
arr[j]=tmp;
if(j-1<0){
break;
}
j-=gap;
}
}
}
时间复杂度
最好：O(n)
平均：(O^1.3)
最坏：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
3.选择排序
选择排序就是拿一个元素与每一个元素进行比较进行,如果这个元素与后面的元素相比大于它，则交换，把每个元素都与其后面的元素相比。则最终排序好。
代码如下：
public static void sort3(int []arr){
int i=0;
while(iarr[j]){
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
}
i++;
}
}
时间复杂度
恒为：O(n^2)
空间复杂度：O(1)
稳定性：不稳定
4.堆排序
原理：把堆按大根堆进行排序，那么root就为这个这个堆的最大值，所以可以建一个数组把它放进去，然后再把堆重新整理为大根堆，然后再把新的root放入数组中，重复上述操作直到把值放完。然后再逆序数组就可以得到排序好的数组。
public static void dui(int []arr,int root,int len){
int parent=root;
int child= 2*parent+1;
while (child arr[child]) {
child++;
}
if(arr[child]>arr[parent]){
int tmp=arr[child];
arr[child]=arr[parent];
arr[parent]=tmp;
parent=child;
child=parent*2+1;
}else {
break;
}
}
}
//把数组建为大根堆
public static void creat_dui(int []arr) {
for (int i = (arr.length-1-1)/2; i >=0; i--) {
dui(arr,i,arr.length);
}
}
public static void sort4(int[]arr){
creat_dui(arr);
int end= arr.length-1;
while(end>0){
int tmp=arr[0];
arr[0]=arr[end];
arr[end]=tmp;
dui(arr,0,end);
end--;
}
}
时间复杂度
恒为：O(nlog(n)) //log以二为底的n
空间复杂度：O(1)
稳定性：不稳定
5.冒泡排序
原理：在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序.
public static void sort5(int []arr){
for (int i = 0; i < arr.length-1; i++) {
boolean flg=false;
for (int j = 0; j < arr.length-1-i; j++) {
if(arr[j+1]
时间复杂度
最好：O(n)
平均：O(n^2)
最坏：O(n^2)
空间复杂度：O(1)
稳定性：稳定
6.快速排序
快排采用的思想主要为分治思想，从待排序区间选择一个数，作为基准值(pivot)，遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边，采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间 的长度 == 0，代表没有数据。
//填坑法
public static int sap(int []arr,int low,int high){
int tmp=arr[low];
while (low=arr[low]){
low++;
}
arr[high]=arr[low];
}
arr[low]=tmp;
return low;
}
//递归
public static void fast_sort6(int []arr,int low,int high){
if(low>=high){
return;
}
int pivot=sap(arr,low,high);
fast_sort6(arr,low,pivot-1);
fast_sort6(arr,pivot+1,high);
}
提升效率：1.对于这个方法取基准值是尤为重要的，当取到中间值时代码的效率是最高的，所以就出现了三数取中法。(代码如下)2.如果数据小于一个阈值，可进行直接插入排序
public static void exchange(int arr[],int x,int y){
int tmp=arr[x];
arr[x]=arr[y];
arr[y]=tmp;
}
public static void selectnumber(int []arr,int low,int high,int mid){
//arr[mid]arr[high]){
exchange(arr,low,high);
}
if(arr[mid]>arr[high]){
exchange(arr,mid,high);
}
}
非递归版本
/非递归实现快速排序
public static void fast_sort8(int []arr) {
Stackstack=new Stack<>();
int low=0;
int high=arr.length-1;
int prvot=sap(arr,low,high);
if(prvot>low+1){
stack.add(low);
stack.add(prvot-1);
}
if(prvotlow+1){
stack.add(low);
stack.add(prvot-1);
}
if(prvot
时间复杂度
最好：O(n * log(n))
平均：O(n * log(n))
最坏：O(n^2)
空间复杂度
最好：O(log(n))
平均：O(log(n))
最坏 ： O(n)
7.归并排序
该排序主要采用的是分治法：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子 序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
递归实现
public static void sort9(int []arr){
sort9_detach(arr,0,arr.length-1);
}
//分离的过程
public static void sort9_detach(int []arr,int low,int high){
if(low>=high){
return;
}
int mid=(low+high)/2;
sort9_detach(arr,low,mid);
sort9_detach(arr,mid+1,high);
sort9_merge(arr,low,mid,high);
}
//合并过程
public static void sort9_merge(int []arr,int low,int mid,int high){
int s1=low;
int e1=mid;
int s2=mid+1;
int e2=high;
int[] tmp=new int[high-low+1];
int k=0;
while(s1<=e1&&s2<=e2) {
if (arr[s1] <= arr[s2]) {
tmp[k++] = arr[s1++];
} else {
tmp[k++] = arr[s2++];
}
}
while(s1<=e1){
tmp[k++]=arr[s1++];
}
while(s2<=e2){
tmp[k++]=arr[s2++];
}
for (int i = 0; i < tmp.length; i++) {
arr[i+low]=tmp[i];
}
}
非递归实现
public static void sort11(int[]arr,int i){
int s1=0;
int e1=s1+i-1;
int s2=e1+1;
int e2=s2+i-1>=arr.length?arr.length-1:s2+i-1;
int[] tmp=new int[arr.length];
int k=0;
while(s2=arr.length?arr.length-1:s2+i-1;
}
while(s1<=arr.length-1){
tmp[k++]=arr[s1++];
}
for (int j = 0; j < tmp.length; j++) {
arr[j]=tmp[j];
}
}
public static void sort10(int[]arr){
for (int i = 1; i < arr.length; i*=2) {
sort11(arr,i);
}
}
时间复杂度
恒为：O(n * log(n))
空间复杂度
恒为：O(n)
