//：class Sort
public class Sort{
public Sort(){} file://构造方法
/********************************************************************************
*选择排序法
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n 表示数组的长度
*@precondition
*从data[first]开始，data中至少还要有n个单元
*@postcondition
*data中的元素已经排序
********************************************************************************/
public static void selectionSort(int[] data,int first,int n){
for(int i=0;i<n;i++){
int k=i;
for(int j=i+1;j<n;j++){
if(data[j+first]<data[k+first]) k=j;
}
if(i!=k){
int temp=data[i+first];
data[i+first]=data[k+first];
data[k+first]=temp;
}
}
}
/********************************************************************************
*插入排序法
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n 表示数组的长度
*@precondition
*从data[first]开始，data中至少还要有n个单元
*@postcondition
*data中的元素已经排序
*********************************************************************************/
public static void insertSort(int[] data,int first,int n){
int j;
for(int i=1;i<n;i++){
int temp=data[i+first];
for(j=i-1;j>=0;j--){
if(data[j+first]>temp){
data[j+1+first]=data[j+first];
}
else
break;
}
data[j+first+1]=temp;
}
}
/********************************************************************************
*冒泡排序法
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n 表示数组的长度
*@precondition
*从data[first]开始，data中至少还要有n个单元
*@postcondition
*data中的元素已经排序
*********************************************************************************/
public static void effervesceSort(int[] data,int first,int n){
boolean flag=true;
for(int i=0;flag==true&&i<n;i++){
flag=false;
for(int j=n-1;j>i;j--){
if(data[j+first]<data[j-1+first]){
int temp=data[j+first];
data[j+first]=data[j+first-1];
data[j+first-1]=temp;
flag=true;
}
}
}
}
/********************************************************************************
*归并排序法的准备工作
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n1 表示数组的长度
*@param n2 表示数组的长度

*********************************************************************************/
public static void merge(int[] data,int first,int n1,int n2){
int[] temp=new int[n1+n2];
int copied=0;
int copy1=0;
int copy2=0;
while(copy1<n1&&copy2<n2){
if(data[copy1+first]<data[copy2+first+n1]){
temp[copied++]=data[(copy1++)+first];
}
else{
temp[copied++]=data[(copy2++)+first+n1];
}
}
while(copy1<n1){
temp[copied++]=data[(copy1++)+first];
}
while(copy2<n2){
temp[copied++]=data[(copy2++)+first+n1];
}
for(int i=0;i<n1+n2;i++){
data[i+first]=temp[i];
}
}
/*********************************************************************************
*归并排序法
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n 表示数组的长度
*@precondition
*从data[first]开始，data中至少还要有n个单元
*@postcondition
*data中的元素已经排序。
*其中用到了合并两个数组的函数merge,其参数有data,first,n1,n2
*data表示数组，first表示数组的起始位置，n1,n2表示数组的长度。
**********************************************************************************/
public static void mergeSort(int[] data,int first,int n){
int n1,n2;
if(n>1){
n1=n/2;
n2=n-n1;
mergeSort(data,first,n1);
mergeSort(data,first+n1,n2);
merge(data,first,n1,n2);
}
}
/********************************************************************************
*快速排序法中用到的方法：找基准元素的下标
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n 表示数组的长度
*********************************************************************************/
public static int partition(int[] data,int first,int n){
int pivotIndex=first;
int small=first+1;
int big=first+n-1;
while(small<=big){
while(data[pivotIndex]>=data[small]) small++;
while(data[pivotIndex]<data[big]) big--;
if(small<big){
int temp=data[small];
data[small]=data[big];
data[big]=temp;
}
}
int temp=data[big];
data[big]=data[pivotIndex];
data[pivotIndex]=temp;
return big;
}
/********************************************************************************
*快速排序法
*@param data 表示数组
*@param first 表示排序数组的起始位置
*@param n 表示数组的长度
*@precondition
*从data[first]开始，data中至少还要有n个单元
*@postcondition
*data中的元素已经排序。
*该方法中调用了partition函数，该函数的作用是找到数组的基准元素的下标
*并将其作为函数的返回值。参数如quickSort方法。
*********************************************************************************/
public static void quickSort(int[] data,int first,int n){
int pivotIndex;
int n1,n2;
if(n>1){
pivotIndex=partition(data,first,n);
n1=pivotIndex-first;
n2=n-n1-1;
quickSort(data,first,n1);
quickSort(data,pivotIndex+1,n2);
}
}
/********************************************************************************
*堆排序法的准备工作
*********************************************************************************/
public static int parent(int k){
if(k>0)
return (k-1)/2;
else throw new NullPointerException("参数k的值要大于0");
}
public static void makeHeap(int[] data,int n){
for(int i=1;i<n;i++){
int k=i;
try{
while(k!=0&&data[k]>data[parent(k)]){
int temp=data[k];
data[k]=data[parent(k)];
data[parent(k)]=temp;
k=parent(k);
}
}catch(NullPointerException e){
System.out.println("catch an exception");
}
}
}
public static void reHeapDown(int[] data,int n){
boolean heapOK=false;
int current=0;
int bigChildIndex;
while(!heapOK&&(2*current+1)<n){
if((2*current+2)<n)
bigChildIndex=Math.max(data[2*current+1],data[2*current+2])==data[2*current+1]?2*current+1:2*current+2;
else
bigChildIndex=2*current+1;
if(data[current]<data[bigChildIndex]){
int temp=data[current];
data[current]=data[bigChildIndex];
data[bigChildIndex]=temp;
current=bigChildIndex;
}
else heapOK=true;
}
}
/********************************************************************************
*堆排序法：
*@param data 数组
*@param n 数组长度
*@precondition
*从data[0]开始，data中至少还要有n个单元
*@postcondition
*data中的元素已经排序。
*该方法中调用makeHeap函数来构造堆，和reHeapDown函数来重新向下调整堆。
*这两个函数的参数设置如heapSort方法。
*在构造堆和向下重新调整堆的时候，为了方便，我们引入了Parent方法得到双亲结点的下标。
*********************************************************************************/
public static void heapSort(int[] data,int n){
makeHeap(data,n);
int unsorted=n;
while(unsorted>1){
unsorted--;
int temp=data[0];
data[0]=data[unsorted];
data[unsorted]=temp;
reHeapDown(data,unsorted);
}
}
/*******************************************************************************
*此处主函数用来测试
*分别去掉函数前的注释符，用来测试各个排序方法
********************************************************************************/
public static void main(String[] args){
int[] data={10,2,3,4,2,1,7,8,1,79};
file://selectionSort(data,0,10);
file://insertSort(data,0,10);
file://effervesceSort(data,0,10);
file://mergeSort(data,0,10);
file://quickSort(data,0,10);
file://heapSort(data,10);
for(int i=0;i<10;i++)
System.out.println(data[i]);
}
}