别看这个简单也基础，但是真的面试的时候会让你写，纸上手写，嗯
快排
代码语言：javascript复制private static void quickSort(int[] test, int start, int end) {
//quick sort的主程序
if(start < end){
int q = partition(test, start, end);
quickSort(test, start, q-1);
quickSort(test, q 1, end);
}
}
private static int partition(int[] test, int start, int end) {
//完成一次划分
//主元选择test[end]
int pivot = test[end];
int i = start - 1;
for(int j = start; j < end; j ){
if(test[j] <= pivot){
i ;
//交换test[i]和test[j]
int t = test[i];
test[i] = test[j];
test[j] = t;
}
}
//i 1的位置即是pivot的位置
//交换test[i 1]和pivot
int t1 = test[i 1];
test[i 1] = test[end];
test[end] = t1;
return i 1;
}堆排序
代码语言：javascript复制public static void heapSort(int[] test){
//建堆
buildHeap(test);
for(int heapSize = test.length - 1; heapSize >= 1; heapSize--){
//交换test[heapSize]和test[0]的位置
int t = test[0];
test[0] = test[heapSize];
test[heapSize] = t;
//维护堆的性质
maxHeapify(test, heapSize, 0);
}
}
private static void maxHeapify(int[] test, int heapSize, int i) {
//维护堆的性质
int left = 2 * i 1;
int right = 2 * i 2;
//找出三者最大的
int largest;
if(left < heapSize && test[left] > test[i]){
largest = left;
}else{
largest = i;
}
if(right < heapSize && test[right] > test[largest]){
largest = right;
}
if(i != largest){
//交换test[i]和test[largest]
int t = test[i];
test[i] = test[largest];
test[largest] = t;
//递归
maxHeapify(test, heapSize, largest);
}
}
private static void buildHeap(int[] test) {
//建堆
for(int i = test.length / 2; i >= 0; i--){
maxHeapify(test, test.length, i);
}
}main函数:
代码语言：javascript复制int test = {2,3,1,1,5,6,7,7,8,4,9,11};
//quickSort(test, 0, test.length-1);
heapSort(test);
for(int x : test){
System.out.print(x " ");
} 
