import java.util.Arrays;
public class Sort {
public static void main(String[] args) {
int []array={124,23,315,12,66,1,35,647,2,14,66};
heapSort(array);
System.out.println(Arrays.toString(array));
}
//合并排序
public static void mergeSort(int[]a,int i,int j){
if(i>=j){
return;
}
mergeSort(a,i,(i+j)/2);
mergeSort(a,(i+j)/2+1,j);
merge(a,i,j);
}
public static void merge(int[]a,int i,int j){
int[] temp=new int[j-i+1];
int la=i;
int ra=(i+j)/2+1;
int count=0;
while(la<=(i+j)/2&&ra<=j){
if(a[ra]<a[la]){
temp[count]=a[ra];
count++;
ra++;
}else{
temp[count]=a[la];
count++;
la++;
}
}
if(la==(i+j)/2+1){
while(ra<=j){
temp[count]=a[ra];
count++;
ra++;
}
}else{
while(la<=(i+j)/2){
temp[count]=a[la];
count++;
la++;
}
}
int ai=i;
while(ai<=j){
a[ai]=temp[ai-i];
ai++;
}
}
//插入排序
public static void insertSort(int[] a){
if(a==null||a.length==1||a.length==0){
return;
}
for(int i=1;i<a.length;i++){
int temp=a[i];
int j=i-1;
for(;j>=0&&a[j]>temp;j--){
a[j+1]=a[j];
}
a[j+1]=temp;
}
}
//冒泡排序
public static void bubbleSort(int[] a){
for(int i=0;i<a.length-1;i++){
boolean isSwap=false;
for(int j=0;j<a.length-i-1;j++){
if(a[j]>a[j+1]){
swap(a,j,j+1);
isSwap=true;
}
}
if(isSwap==false){
return;
}
}
}
//选择排序
public static void selectSort(int[]a){
for(int i=0;i<a.length-1;i++){
for(int j=i+1;j<a.length;j++){
if(a[j]<a[i]){
swap(a,j,i);
}
}
}
}
//快速排序
public static void quickSort(int[]a,int i,int j){
if(i>=j){
return;
}
int s=partition(a,i,j);
quickSort(a,i,s-1);
quickSort(a,s+1,j);
}
public static int partition(int[]a,int i,int j){
int l=a[i];
int left=i+1;
int right=j;
while(left<right){
while(a[left]<l){
left++;
}
while(a[right]>l){
right--;
}
swap(a,left,right);
}
swap(a,left,right);
swap(a,right,i);
return right;
}
/*堆排序
*
*/
public static void heapSort(int[]a){
buildMaxHeap(a);
swap(a,0,a.length-1);
for(int i=a.length-2;i>=1;i--){
fixMaxHeap(a,0,i);
swap(a,0,i);
}
}
/*
* 自底向上算法，构件最大堆
*/
public static void buildMaxHeap(int[]a){
for(int i=(a.length-1)/2;i>=0;i--){
fixMaxHeap(a,i,a.length-1);
}
}
/*交换元素后，修复为最大堆结构
*
*/
public static void fixMaxHeap(int[]a,int i,int n){
int k=i;
int v=a[i];
boolean heap=false;
while(!heap&&2*k+1<=n){
int j=2*k+1;
if(j<n&&a[j]<a[j+1]){
j=j+1;
}
if(v>=a[j]){
heap=true;
}else{
a[k]=a[j];
k=j;
}
}
a[k]=v;
}
public static void swap(int a[],int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
待补充。。
转载请注明原文地址: https://ju.6miu.com/read-19495.html
