# 快排和堆排序

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;
}

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函数:

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+" ");
}

89 篇文章41 人订阅

0 条评论

## 相关文章

1965

2807

### 工人的请愿书（树形DP）- UVA 12186

A couple of years ago, a new world wide crisis started, leaving many people with...

1094

### Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)(A.暴力，B.优先队列，C．dp乱搞)

A. Carrot Cakes time limit per test：1 second memory limit per test：256 megabytes...

3257

651

### 1708: [Usaco2007 Oct]Money奶牛的硬币

1708: [Usaco2007 Oct]Money奶牛的硬币 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 5...

2577

### HDU6370：Werewolf 推理+拓扑排序 2018第六场杭电多校

"The Werewolves" is a popular card game among young people.In the basic game, th...

652

2247

1965

### 【学习经验】Java中常用英文

【学习经验】Java中常用英文 第一章： public['pʌblik] 公共的,公用的 static['stætik] 静的;静态的...

35110