import java.util.Arrays;

public class SortDemo {

private static long[] arr = {6,5,2,7,1,8,4,3};

// private static long[] arr = {1,2,3,4,5,6,7,8};

private static int count = 0;

/**

* 冒泡排序

* O(n2)

*/

public static void bubble(){

long temp = Long.MIN_VALUE;

int len = arr.length;

for(int j = 0;j<len;j++){

for(int i = 0;i<len-1;i++){

if(arr[i]>arr[i+1]){

temp = arr[i+1];

arr[i+1] = arr[i];

arr[i] = temp;

}

}

}

}

/**

* 选择排序

* O(n2)

*/

public static void select(){

int len = arr.length;

long temp = Long.MIN_VALUE;

int index = 0;

for(int j = 0;j<len;j++){

index = j;

for(int i = j;i<len;i++){

if(arr[i]<arr[index]){

index = i;

}

}

temp = arr[j];

arr[j] = arr[index];

arr[index] = temp;

print();

}

}

/**

* 插入排序

* O(n2)

*/

public static void insert(){

int len = arr.length;

long temp;

for(int i=1;i<len;i++){

int j = i-1;

temp = arr[i];

while(j>=0 && temp<arr[j]){

arr[j+1] = arr[j];

j--;

}

arr[j+1] = temp;

print();

}

}

/**

* 快速排序

* O(N*longN)

*/

public static void quick(){

quick(arr,0,arr.length-1);

print();

}

private static long[] quick(long[] a,int lo,int hi){

if(hi<lo)return a;

long temp = 0;

int index = lo;

for(int i = lo;i<hi;i++){

if(a[i]<a[hi]){

temp = a[i];

a[i] = a[index];

a[index++] = temp;

}

}

temp = a[hi];

a[hi] = a[index];

a[index] = temp;

if(index==lo)return a;

quick(a,lo,index-1);

quick(a,index+1,hi);

return a;

}

/**

* 归并排序

* O(N*longN)

*/

public static void merge (){

merge(arr,0,arr.length-1);

print();

}

public static void merge(long[] a,int lo,int hi){

int mid = lo +(hi-lo)/2;

if(lo < hi){

merge(a,lo,mid);

merge(a,mid+1,hi);

merge(a,lo,mid,hi);

}

}

public static void merge(long[] a,int lo,int mid,int hi){

long[] temp = new long[hi-lo+1];

int i=lo,j=mid+1,index=0;

while(i<=mid&&j<=hi){

if(a[i]>a[j]){

temp[index++] = a[j++];

}else{

temp[index++] = a[i++];

}

}

while(i<=mid){

temp[index++] = a[i++];

}

while(j<=hi){

temp[index++] = a[j++];

}

System.arraycopy(temp, 0, a, lo, temp.length);

}

public static void print(){

System.out.println(Arrays.toString(arr));

}

public static void main(String[] args) {

merge();

}

}