经典排序算法:快速排序、归并排序、堆排序、选择排序、希尔排序、插入排序、冒泡排序（Java版）

经典排序算法

• • 定义排序类
  • 插入排序
  • 希尔排序
  • 选择排序
  • 冒泡排序
  • 快速排序
  • 堆排序
  • 归并排序

用Java实现经典的排序算法，便于以后查询使用

定义排序类

public class Sort{
	public int[] arr;
	public Sort(int n){
		arr=new int[n];
	}
	public Sort(int[] arr){
		int len=arr.length;
		this.arr=new int[len];
		for(int i=0;i<len;++i){
			this.arr[i]=arr[i];
		}
	}
}
           

插入排序

//插入排序(小->大)
	public void insertSort(){
		int arrLen=arr.length;
		for(int i=1;i<arrLen;++i){
			int temp=arr[i];
			int j=i-1;
			while(j>=0){
				if(arr[j]<=temp){
					break;
				}
				arr[j+1]=arr[j];
				--j;
			}
			arr[j+1]=temp;
		}
	}
           

希尔排序

//希尔排序(小->大)
	public void shellSort(int k){
		int arrLen=arr.length;
		while(k>0){
			for(int i=k;i<arrLen;i+=k){
			int temp=arr[i];
			int j=i-k;
			while(j>=0){
				if(arr[j]<temp){
					break;
				}
				arr[j+k]=arr[j];
				j -=k;
			}
			arr[j+k]=temp;
			}
			k /=2;	
		}
	}
           

选择排序

//选择排序(小->大) 选topK可以用这个
	public void selectSort(){
		int arrLen=arr.length;
		for(int i=0;i<arrLen-1;++i){
			int min=i;
			for(int j=i+1;j<arrLen;++j){
				if(arr[min]>arr[j]){
					min=j;
				}
			}
			if(min!=i){
				int temp=arr[i];
				arr[i]=arr[min];
				arr[min]=temp;
			}
		}	
	}
           

冒泡排序

//冒泡排序(小->大)
	public void bubbleSort(){
		int arrLen=arr.length;
		for(int i=0;i<arrLen-1;++i){
			for(int j=arrLen-1;j>i;--j){
				if(arr[j]<arr[j-1]){
					int temp=arr[j];
					arr[j]=arr[j-1];
					arr[j-1]=temp;
				}
			}
		}
	}
           

快速排序

//快速排序 (小->大)
	public void quickSort(int low, int high){
		if(low<high){
			int privot=arr[low];
			int i=low,j=high;
			while(i<j){
				for(;i<j&&arr[j]>=privot;--j);
				if(i<j){
					arr[i]=arr[j];
					++i;
				}
				for(;i<j&&arr[i]<=privot;++i);
				if(i<j){
					arr[j]=arr[i];
					--j;	
				}
			}
			arr[i]=privot;
			quickSort(low,i-1);
			quickSort(i+1,high);
		}
	}
           

堆排序

//堆排序(大->小)注意：数组下标从0开始
	// 将节点index放置在堆的合适位置
	private void placeOneNode(int index, int len){
		int i=index;
		int value=arr[i];
		int j=2*i+1;
		if((j+1)<len&&arr[j]>arr[j+1]){
					++j;
				}
		while(j<len&&value>arr[j]){
			arr[i]=arr[j];
			i=j;
			j=2*i+1;
			if((j+1)<len&&arr[j]>arr[j+1]){
				++j;
			}
		}
		arr[i]=value;
	}
	// 建小根堆完全二叉树
	private void buildHeap(){
		int  arrLen=arr.length;
		for(int i=(arrLen/2)-1;i>=0;--i){
			placeOneNode(i,arrLen);
		}
	}
	// 进行推排序
	public void heapSort(){
		buildHeap();
		int  arrLen=arr.length;
		for(int i=arrLen-1;i>0;--i){
			int temp=arr[i];
			arr[i]=arr[0];
			arr[0]=temp;
			placeOneNode(0,i);
		}
	}
           

归并排序

//归并排序 (小->大)
	public void mergeSort(int low,int high){
		if(low<high){
			int mid=(low+high)/2;
			mergeSort(low,mid);
			mergeSort(mid+1,high);
			merge(low,mid,high);
		}
	}
	// 归并排序合并过程
	private void merge(int low,int mid,int high){
		int i=low,j=mid+1;
		int[] buffer=new int[high-low+1];
		int num=0;
		while(i<=mid&&j<=high){
			if(arr[i]<arr[j]){
				buffer[num++]=arr[i];
				++i;
			}
			else{
				buffer[num++]=arr[j];
				++j;
			}
		}
		while(i<=mid){
			buffer[num++]=arr[i];
			++i;
		}
		while(j<=high){
			buffer[num++]=arr[j];
			++j;
		}
		for(int k=0,s=low;k<num&&s<=high;++k,++s){
			arr[s]=buffer[k];
		}
	}