public class QuickSort {
public static int[] sort(int[] array, int start, int end){
if(array.length < 1 || start < 0 || end >= array.length || start > end)
return null;
//分区(割)指示器 = 一趟快速排序之后的返回值下标
int zoneIndex = partition(array,start,end);
//对左右两部分递归调用sort方法
if(zoneIndex > start){
sort(array,start,zoneIndex-1);
}
if(zoneIndex < end){
sort(array,zoneIndex+1,end);
}
return array;
}
private static in partition(int[] attay, int start,int end){
//基准数
int pivot = (int)(start+Math.random() * (end - start=1));
int zoneIndex = start - 1;
swap(array,pivot,end);//交换基准数和尾元素
for(int i= start;i<end;i+=){
if(array[i]<array[end]){
zoneIndex +=;
if(i>zoneIndex){
swap(array,i,zoneIndex);
}
}
}
return zoneIndex;
}
public static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
5.堆排序O(nlogn)
public class HeapSort {
//声明全局遍历。用于记录数组array的长度
private static int len;
private static int[] sort(int[] array){
len = array.length;
if(len<1) return array;
//构建一个最大堆
buildMaxHeap(array);
//取出堆顶元素和尾元素交换
while(len>0){
swap(array,0,len-1);
len--;//len -- 数组不变
adjustHeap(array,i);
}
return array;
}
}
//构建一个最大堆
private static void bulidMaxHeap(int[] array){
for(int i= (len/2-1);i>=0;i--){
adjustHeap(array,i);
}
}
//调整堆
private static void adjustHeap(int[] array,int i){
int maxIndex = i;//保存最大的元素
int left = 2*i+1;//左节点
int right = 2*(i+1);//右节点
if(left<len&& array[left]>array[MaxIndex]){
maxIndex = left;
}
if(right<len&& array[right]>array[MaxIndex]){
maxIndex = right;
}
if(maxIndex != i){
swap(array,maxIndex,i);
adjustHeap(array,maxIndex)
}
}
public static void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
6.桶
1.计数排序
2.桶排序O(nlogn)
3.基数排序
总结：
