抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

input : 8, 5, 4, 9, 2, 3, 6

1. heapSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void heapify(int a[], int i, int size) { // 堆化的维持需要用递归
int ls = 2*i, rs = 2*i + 1;
int large = i;
if(ls <= size && a[ls] > a[i]) {
large = ls;
}
if(rs <= size && a[rs] > a[large]) {
large = rs;
}
if(large != i) {
swap(a[i], a[large]);
heapify(a, large, size);
}
}
void buildHeap(int a[], int size) {
for(int i = size/2; i >= 1; i--) {
heapify(a, i, size);
}
}
void heapSort(int a[], int size) {
buildHeap(a, size);
int len = size;
for(int i = len; i >= 2; i--) {
swap(a[i], a[1]);
len--;
heapify(a, 1, len);
}
}

2. quickSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quickSort(int a[], int left, int right) {
if(left < right) { // exit. good idea!
int l = left, r = right, x = a[l];
while(1) {
while(l < r && a[r] >= x) r--;
while(l < r && a[l] <= x) l++;
if(l >= r) break;
swap(a[r], a[l]);
}
swap(a[left], a[l]);
quickSort(a, left, l-1);
quickSort(a, l+1, right);
}
}

3. mergeSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void mergeSort(int a[], int l, int r) { //  8, 5, 4, 9, 2, 3, 6
if(l >= r) return; // exit.
int mid = (l+r) / 2; // overflow <-> l + (r-l)/2
mergeSort(a, l, mid);
mergeSort(a, mid+1, r);
int *arr = new int[r-l+1];
int k = 0;
int i = l, j = mid + 1;
while(i <= mid && j <= r) {
if(a[i] <= a[j]) {
arr[k++] = a[i++];
}
else {
arr[k++] = a[j++]; // ans += (mid-i+1);
}
}
while(i <= mid) arr[k++] = a[i++];
while(j <= r) arr[k++] = a[j++];
for(int i = l; i <= r; i++) {
a[i] = arr[i-l];
}
delete []arr;
}

4. insertSort

1
2
3
4
5
6
7
8
9
10
void insertSort(int a[], int len) {
int j;
for(int i = 1; i < len; i++) {// 新抓的每张扑克牌
int temp = a[i];
for(j = i-1; a[j] > temp && j >= 0; j--) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}

5. bubbleSort

1
2
3
4
5
6
7
void bubbleSort(int a[], int len) {
for(int i = 1; i < len; i++) {
for(int j = 0; j < len-i; j++) {
if(a[j] > a[j+1]) swap(a[j], a[j+1]);
}
}
}

6. selectSort

1
2
3
4
5
6
7
8
9
10
void selectSort(int a[], int len) {
int i, j, k;
for(i = 0; i < len-1; i++) {
k = i;
for(j = i+1; j < len; j++) {
if(a[j] < a[k]) k = j;
}
swap(a[i], a[k]); // 将第i位小的数放入i位置
}
}