/**
插入排序：直接，希尔
选择排序：选择排序，堆排序
交换排序：冒泡，快速
归并排序：归并
*/
public class Sort{
public static void main(String[] agrs){
int[] a = new int[] {5,6,8,7,4,9,3,1,2,0};
//int[] a = new int[] {9,8,7,6,5,4,3,2,1,0};
System.out.println("Sort:");
ArrayPrint(a);
//InsertSort(a);
//ShellSort(a);
//SelectSort(a);
//HeapSort(a);
//BubbleSort(a);
//QuickSort(a,0,a.length-1);
MergeSort(a,0,a.length-1);
ArrayPrint(a);
}
public static void ArrayPrint(int[] a){
for(int i=0; i<a.length; i++){
System.out.print(a[i]+" ");
}
System.out.println();
}
public static void Swap(int[] a,int i,int j){
int tmp =a[i];
a[i] = a[j];
a[j] = tmp;
}
//直接插入排序
public static void InsertSort(int[] a){
int end = 0, i=0;
for(;i<a.length-1;i++){
end = i;
int tmp = a[end+1];
while(end>=0&&tmp<a[end]){
a[end+1] = a[end];
--end;
}
a[end+1]=tmp;
}
}
//希尔排序
public static void ShellSort(int[] a){
int pox=a.length;
while(pox>1){
pox = pox/3+1;
for(int i=0;i<a.length-pox;++i){
int end = i;
int tmp = a[i+pox];
while(end>=0&&tmp<a[end]){
a[end+pox]=a[end];
end-=pox;
}
a[end+pox]=tmp;
}
}
}
//选择排序
public static void SelectSort(int[] a){
int left=0, right=a.length-1;
int min=0,max=0;
while(left<right){
min=max=left;
for(int i=left;i<=right;++i){
if(a[i]<a[min]){
min = i;
}
if(a[i]>a[max]){
max = i;
}
}
Swap(a,left,min);
if(max==left){
max=min;
}
Swap(a,right,max);
++left;
--right;
}
}
//堆排序
public static void AdjustDown(int[] a, int n, int i){
int parent = i;
int child = parent*2+1;
while(child<n){
child = parent*2+1;
if((child+1)<n&&a[child]>a[child+1]){
child++;
}
if(child<n&&a[parent]>a[child]){
Swap(a,parent,child);
parent = child;
}
else
break;
}
}
public static void HeapSort(int[] a){
int i = (a.length-2)/2;
for(;i>=0;--i){
AdjustDown(a,a.length,i);
}
ArrayPrint(a);
for(i=a.length-1;i>=0;i--){
Swap(a,i,0);
AdjustDown(a,i,0);
}
}
//冒泡排序
public static void BubbleSort(int[] a){
int end = a.length-1;
for(;end>0;--end){
int flag=0;
for(int i=0;i<end;i++){
if(a[i]>a[i+1]){
Swap(a,i,i+1);
flag=1;
}
}
if(0==flag){
return;
}
}
}
//快速排序(难点)***********************************
public static int FindMid(int[] a,int left,int right){
int mid=left+((right-left)>>1);
if(a[left]>a[right]){
if(right>a[mid])
return right;
else if(a[left]>a[mid])
return mid;
else
return left;
}
else {
if(a[left]>a[mid])
return left;
else if(a[right]>a[mid])
return mid;
else
return right;
}
}
//左右指针法
public static int partion1(int[] a, int left, int right){
int begin=left, end=right;
int mid=FindMid(a,left,right);
Swap(a,mid,right);
int key=a[right];
while(begin<end){
while(a[begin]<=key&&begin<end)
begin++;
while(a[end]>=key&&begin<end)
end--;
Swap(a,begin,end);
}
Swap(a,begin,right);
return begin;
}
//挖坑法
public static int partion2(int[] a,int left,int right){
int begin=left,end=right;
int mid=FindMid(a,left,right);
Swap(a,mid,right);
int key=a[right];
while(begin<end){
while(a[begin]<=key&&begin<end)
begin++;
a[end]=a[begin];
while(a[end]>=key&&begin<end)
end--;
a[begin]=a[end];
}
a[begin]=key;
return begin;
}
//前后指针法(难点)*****
public static int partion3(int[] a,int left,int right){
int prev=left-1, cur=left;
int mid = FindMid(a,left,right);
Swap(a,mid,right);
while(cur<right){
if(a[cur]<=a[right]&&++prev!=cur){
Swap(a,prev,cur);
}
cur++;
}
Swap(a,++prev,right);
return prev;
}
public static void QuickSort(int[] a,int left,int right){
int div;
if(left<right){
div = partion3(a,left,right);
QuickSort(a,left,div-1);
QuickSort(a,div+1,right);
}
}
//并归排序
public static void Merge(int[] a,int left,int mid,int right){
int begin1=left,end1=mid,begin2=mid+1,end2=right,i=0;
int[] tmp = new int[right-left+1];
while(begin1<=end1&&begin2<=end2){
if(a[begin1]<a[begin2])
tmp[i++]=a[begin1++];
else
tmp[i++]=a[begin2++];
}
while(begin1<=end1){
tmp[i++]=a[begin1++];
}
while(begin2<=end2){
tmp[i++]=a[begin2++];
}
for(i=0;i<=right-left;i++){
a[i+left]=tmp[i];
}
}
public static void MergeSort(int[] a,int left,int right){
int mid = left+((right-left)>>1);
if(left>=right)
return;
MergeSort(a,left,mid);
MergeSort(a,mid+1,right);
Merge(a,left,mid,right);
}
}
