冒泡，插入，选择，快排，归并学习ing。。请直接看源码；原理在注释中有体现，嘻嘻。。
public class SortTest {
public static void main(String[] args){
int[] a = new int[]{3,1,5,8,4,6,5,10,9};
splitMerge(a,0,a.length-1);
for(int value : a) {
System.out.print(value + ",");
}
}
/**
* 快速排序
* 分治+递归 选取第一个元素作为分界点，将其比他大和小的分成两组，与中间元素替换位置，依次对左，右两边进行递归
* 时间复杂度 O(nlog2n) 空间O(logn)
* @param a
* @param low
* @param high
*/
public static void fastSort(int a[],int low,int high) {
if(low >= high){
return;
}
int l = low;
int r = high-1;
int temp = a[low];
while(l!=r){
while(a[r] >= temp && l<r){
r--;
}
while(a[l]<= temp && l<r){
l++;
}
if(l<r){
swap(a,l,r);
}
}
swap(a,low,l);
fastSort(a,low,l-1);
fastSort(a,l+1,high);
}
private static void swap(int a[],int i, int r) {
int temp = a[i];
a[i] = a[r];
a[r] = temp;
}
/**
* 选择排序
* 每轮循环记录数组中最小元素位置，将其与循环最开始端替换
* @param a
* @param low
* @param high
*/
private static void chooseSort(int a[],int low,int high){
for(int i = low ;i < high-1 ;i++){
int min = i;
for(int j = i+1;j < high;j++){
if(a[min] > a[j]){
min = j;
}
}
if(i!= min)
swap(a,i,min);
}
}
/**
* 插入排序
* 从第1个元素开始，将其插入前面已排好序的队列中，需要注意，内部循环必须从右往左替换
* @param a
* @param low
* @param high
*/
private static void insertSort(int a[],int low,int high){
for(int i = low+1;i<high;i++){
int temp = a[i];
for(int j = i-1;j>=0;j--){
if(temp < a[j]){
swap(a,j,j+1);
temp = a[j];
}
}
}
}
/**
* 冒泡排序
* 两辆相邻元素比较，将最大值推到循环末端
* @param a
* @param low
* @param high
*/
private static void maopaoSort(int a[],int low,int high){
for(int i=low;i<high-1;i++){
for(int j =0;j<high-i-1;j++){
if(a[j] > a[j+1]){
swap(a,j,j+1);
}
}
}
}
/**
* 两个数组之间比较 low至mid ,mid+1至high
* 请注意入参是mid+1,开区间
* @param a
* @param low
* @param mid
* @param high
*/
private static void mergeSort(int a[],int low,int mid, int high){
int[] leftArr = new int[mid - low];
int[] rightArr = new int[high - mid+1];
//往数组填充数据
for(int i=0;i<mid-low;i++){
leftArr[i]= a[low+i];
}
for(int j = 0;j<= high-mid;j++){
rightArr[j] = a[mid+j];
}
int i = 0,j= 0,k = low;
while(i < leftArr.length && j < rightArr.length){
if(leftArr[i] <= rightArr[j]){
a[k++]=leftArr[i++];
}else{
a[k++]=rightArr[j++];
}
}
while(i < leftArr.length ){
a[k++]=leftArr[i++];
}
while(j < rightArr.length ){
a[k++]=rightArr[j++];
}
}
//递归拆分数组,当数组中只有一个元素时停止
private static void splitMerge(int a[],int low,int high){
if(low == high){
return ;
}
int mid = (low+high)/2;
splitMerge(a,low,mid);
splitMerge(a,mid+1,high);
mergeSort(a,low,mid+1,high);
}
}
