排序算法

一:直接插入法

//升序

public static int[] insertSort(int[] source){
int tmp=0;
for(int i=1;i<source.length;i++){
if(source[i]<source[i-1]){
tmp=source[i]; int j=i-1;
do{
source[j+1]=source[j];
j--;
}while(j>=0 && tmp<source[j]);
source[j+1]=tmp;
}

}
return source;
}

//倒序

public static int[] insertSort(int[] source){
int tmp=0;
for(int i=1;i<source.length;i++){
if(source[i]>source[i-1]){
tmp=source[i]; int j=i-1;
do{
source[j+1]=source[j];
j--;
}while(j>=0 && tmp>source[j]);
source[j+1]=tmp;

}

二:快速排序

/***
* 随机化分
* @param source
* @param low
* @param high
* @return
*/
private static int randomizedPartition(int[] source,int low,int high){
int k;
k=getRandom(low,high);
int tmp=source[low];
source[low]=source[high];
source[high]=tmp;
return partition(source,low,high);
}
private static int partition(int[] source,int low,int high){
int pivot=source[low];
while(low<high){
while(low<high && source[high]>=pivot)
high--;
if(low<high)
source[low++]=source[high];
while(low<high && source[low]<=pivot)
low++;
if(low<high)
source[high--]=source[low];
}
source[low]=pivot;
return low;
}
/***
* 快速排序
* @param source
* @param low
* @param high
*/
private static void quickSort(int[] source,int low,int high){
int pivotPos;
if(low<high){
pivotPos=partition(source,low,high);
quickSort(source,low,pivotPos-1);
quickSort(source,pivotPos+1,high);
}
}
/***
* 随机快速排序
* @param source
* @param low
* @param high
*/

public static void randomizedQuickSort(int[] source,int low,int high){
int pivotPos;
if(low<high){
pivotPos=randomizedPartition(source,low,high);
quickSort(source,low,pivotPos-1);
quickSort(source,pivotPos+1,high);
}
}


/***
* return >= start && <=end 的随机数 ,end需大于start 否则返回-1
* @param start
* @param end
* @return
*/
public static int getRandom(int start,int end){
if(start>end || start <0 || end <0){
return -1;
}
return (int)(Math.random()*(end-start+1))+start;
}

}
return source;
}