常见排序

package sort;

public class SOrton {
public static void main(String[] args) {
int [] arrs = {6,1,2,7,9,3,4,5,10,8,3,4,6,10,43,2,12,66,66,1,77};
long a =System.currentTimeMillis();
//quickSort(arrs,0,arrs.length-1);
//bubbleSort(arrs);
//insertSort(arrs);
///selectSort(arrs);
mergeSort(arrs,0,arrs.length-1);
//shellSort(arrs,arrs.length);
long b =System.currentTimeMillis();
System.out.println("耗时 :"+(b-a));
for(int i = 0;i<arrs.length;i++) {
System.out.print(arrs[i]+" ");
}
}
/**
* 归并排序 (需要使用递归)
* @param arrs
* @param start 数组开始
* @param end 数组结束
*/
public static void mergeSort(int [] arrs,int start,int end) {
  if(start<end) {
int mid = (end+start)/2;
mergeSort(arrs,start,mid);
mergeSort(arrs,mid+1,end);
merge(arrs,start,mid,end);
}
}
/**
*
* @param arrs
* @param left 序列数组开始
* @param mid  中间
* @param right 结束 如 [left,..mid] [mid+1,..right]
* [1,2] [3,4,5,6]  通过检测tmp =[1,2,..]
* 由于还有[3,4,5,6]没有参与检测 直接合并到 tmp={1,2,3,4,5,6}
*/
public static void merge(int arrs [] ,int left ,int mid,int right) {
      int [] tmp = new int[arrs.length];//申请临时数组
      int p1 = left,p2=mid+1,k=left;
      while(p1<=mid && p2<=right) {
      if(arrs[p1]<arrs[p2])
      tmp[k++]=arrs[p1++];
      else
      tmp[k++]=arrs[p2++];
      }
      //还有没有检测比较的数据 直接 加在数组的后面（合并）
  while(p1<=mid)
  tmp[k++]=arrs[p1++];
  while(p2<=right)
  tmp[k++]=arrs[p2++];
        //复制回原素组
        for (int i = left; i <=right; i++)
        arrs[i]=tmp[i];
}
/***
* 希尔排序
* @param arrs
* @param size
*/
public static void shellSort(int [] arrs,int size) {
if(size ==1)
return;
int s = size/2;
for(int i=s;i<arrs.length;i+=s) {
  int j=i;
  while(j>=s && arrs[j]<arrs[j-s]) {
  int tmp =arrs[j];
  arrs[j]=arrs[j-s];
  arrs[j-s]=tmp;
  j-=s;
  }
}
shellSort(arrs,s);
}
/**
* 选择排序
* @param arrs
*/
public static void selectSort(int [] arrs) {
for(int i=0;i<arrs.length;i++) {
for(int j = i+1;j<arrs.length;j++) {
if(arrs[i]>arrs[j]) {
  int tmp =arrs[j];
  arrs[j]=arrs[i];
  arrs[i]=tmp;
}
}
}
}
/***
   * 插入排序
   * @param arrs
   */
  public static void insertSort(int arrs []) {
  for(int i=1;i<arrs.length;i++) {
  int j=i;
  while(j>=1 && arrs[j]<arrs[j-1]) {
  int tmp =arrs[j];
  arrs[j]=arrs[j-1];
  arrs[j-1]=tmp;
  j--;
  }
  }
  }
/***
* <h1>快速排序<h1>
* @param arrs
* @param left 开始的索引
* @param right 结束的索引
*
* 注意  只能从基数的对面开始 否则 如6,1,2,7,9  -->7,6,1,2,9 错误的结果
*
* 思想 :
* <br>
* 1、从由开始遍历，找到一个小于基数的则停下 i
* <br>
* 2、从左开始 找到大于基数的停止j
* <br>
* 3、  交换i和j
* <br>
* 4、若i==j 则 交换基数和i的值
* <br>
* 5、重复1-4
*
*/
  public static void quickSort(int [] arrs,int left,int right) {
  //选择一个数作为轴值
  if(left>right)
  return;
  int key = arrs[left],i = left,j = right;
  while(i!=j) {
  while(key<=arrs[j] && i<j)
    j--;
  while(key>=arrs[i] && i<j)
        i++;
  if(i<j) {
  int tmp = arrs[i];
  arrs[i]=arrs[j];
  arrs[j]=tmp;
  }
  }
  arrs[left] = arrs[i];
  arrs[i]=key;
 
  quickSort(arrs,left,i-1);
  quickSort(arrs,i+1,right);
  }
  /**
   * <h1>冒泡排序<h1>
   * @param arrs
   */
  public static void bubbleSort(int arrs[]) {
  for(int i=0;i<arrs.length;i++) {
  for(int j = arrs.length-1;j>i;j--) {
  if(arrs[j]<arrs[j-1]) {
  int tmp = arrs[j];
  arrs[j]=arrs[j-1];
  arrs[j-1]=tmp;
  }
  }
  }
  }
}