package sort_test;
public class test {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = {23,54,36,64,7,3,67,85,66,44};
// int n=a.length;
// for(int i=n/2-1;i>=0;i--){//i=n/2-1为非叶子结点最后一个父节点
// build_max_heap(a,i,n);
// }
merge_sort(a,0,a.length-1);
for(int i:a){
System.out.println(i);
}
// int nn = binarySearch2(a,36,0,a.length-1);
// System.out.println(nn);
}
//is item v less than w?
private static boolean less(int v,int w){
return v < w;
}
//swap item in array a[] at index i with the one in index j
private static void exch(int[] a,int i,int j){
int temp = a[i];
a[i]=a[j];
a[j]=temp;
}
//基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止
public static void select_sort(int[] a){
int n=a.length;
for(int i=0;i<n;i++){
int min=i;//先假设最小位置在0
for(int j=i+1;j<n;j++){//遍历比较位置0和后面任意位置的值，找出最小值的index
if(less(a[j],a[min])){
min=j;
}
}
exch(a,min,i);//把最小值的index和index为i的值对换
}
}
//从第一个数起，比较相邻两数，把较大的放置在后面，一次循环结束，最后一个数最大。除去最后一个数，对前n-1个数重复同样的方法
public static void bubble_sort(int[] a){
int n=a.length;
for(int i=0;i<n-1;i++){
for(int j=0;j<n-1-i;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
//前面n-1个数已经是排好的序列，现在要把第n个数查到其中
public static void insert_sort(int[] a){
int n=a.length;
for(int i=0;i<n;i++){
for(int j=i;j>0;j--){
if(less(a[j],a[j-1])){
exch(a,j-1,j);
}
}
}
}
//将未排序部分元素逐个排序插入,但是插入的过程不同,需要每次求一个中间位置,和中间位置元素比较大小,然后根据大小情况,将高位左移或者将低位右移
public static void binary_insert_sort(int[] a){
int n=a.length;
int i,j,temp,low,mid,high;
for(i=1;i<n;i++){
low=0;//排序部分的最低位
temp=a[i];//未排序部分的最低位
high=i-1;//排序部分的最高位
while(low<=high){
mid=(low+high)/2;
if(a[mid]>temp){
high=mid-1;
}else{
low=mid+1;
}
}
for(j=i-1;j>high;j--){//将high+1 ~ i的所有元素后移一位
a[j+1]=a[j];
}
a[high+1]=temp;//插入元素
}
}
//分组的插入排序
public static void shell_sort(int[] a){
int n=a.length;
int h=1;
while(h<n/3){
h=3*h+1;//h为步长
}
while(h>=1){
for(int i=h;i<n;i++){
for(int j=i;j>=h&&less(a[j],a[j-h]);j-=h){
exch(a,j,j-h);
}
}
h/=3;
}
}
public static void quick_sort(int[] a,int left,int right){
int ileft=left;
int iright=right;
int imiddle=(ileft+iright)/2;
int temp=a[imiddle];
while(true){
while(a[iright]>temp) iright--;
while(a[ileft]<temp) ileft++;
if(ileft>=iright) break;
exch(a,ileft,iright);
}
if(ileft!=left) quick_sort(a,left,ileft-1);
if(iright!=right) quick_sort(a,iright+1,right);
}
//构建最大堆
private static void build_max_heap(int[] a,int parent,int length){
int lchild=2*parent+1;
int rchild=2*parent+2;
int largest=parent;
if(lchild<length&&a[lchild]>a[largest]){
largest=lchild;
}
if(rchild<length&&a[rchild]>a[largest]){
largest=rchild;
}
if(largest!=parent){
exch(a,largest,parent);
build_max_heap(a,largest,length);
}
}
public static void heap_sort(int[] a){
//建堆
int n=a.length;
for(int i=n/2-1;i>=0;i--){//i=n/2-1为非叶子结点最后一个父节点
build_max_heap(a,i,n);
}
//已经是最大堆，排序
// for(int j=n-1;j>0;j--){
// exch(a,0,j);
// build_max_heap(a,0,--n);
// }
while(n>0){
exch(a,0,--n);
build_max_heap(a,0,n);
}
}
private static void merge(int[] a,int low,int mid,int high){
int i=low;//左指针
int j=mid+1;//右指针
int k=0;
int[] temp=new int[high-low+1];
// 把较小的数先移到新数组中
while(i<=mid&&j<=high){
if(a[i]<a[j]){
temp[k++]=a[i++];
}else{
temp[k++]=a[j++];
}
}
// 把左边剩余的数移入数组
while(i<=mid){
temp[k++]=a[i++];
}
// 把右边边剩余的数移入数组
while(j<=high){
temp[k++]=a[j++];
}
// 把新数组中的数覆盖a数组
for(int k2=0;k2<temp.length;k2++){
a[k2+low]=temp[k2];
}
}
public static void merge_sort(int[] a,int low,int high){
int mid=(low+high)/2;
if(low<high){
//左边递归
merge_sort(a,low,mid);
//右边递归
merge_sort(a,mid+1,high);
merge(a,low,mid,high);
}
}
public static int binarySearch(int[] a,int x){
int low=0;
int high=a.length-1;
while(low<=high){
int middle=(low+high)/2;
if(x==a[middle]){
return middle;
}else if(x<a[middle]){
high=middle-1;
}else{
low=middle+1;
}
}
return -1;
}
public static int binarySearch2(int[] a,int x,int low,int high){
if(low<=high){
int middle=(low+high)/2;
if(x==a[middle]){
return middle;
}else if(x<a[middle]){
return binarySearch2(a,x,low,middle-1);
}else{
return binarySearch2(a,x,middle+1,high);
}
}
return -1;
}
}
网友评论