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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <stdio.h>
#include <stdlib.h>
static void dump(int *items, int n)
{
printf("[");
for (int i = 0; i < n; ++i)
printf("%d,", items[i]);
printf("]\n");
}
static void _merge(int *items, int min, int mid, int max) {
int length = (max-min) + 1;
int tmp[length];
int j = min, k = mid;
for (int i = 0; i < length; i++) {
if (j < mid && k <= max)
if (items[j] < items[k])
tmp[i] = items[j++];
else
tmp[i] = items[k++];
else
if (j >= mid)
tmp[i] = items[k++];
else
tmp[i] = items[j++];
}
for (int i = 0; i < length; i++)
items[min+i] = tmp[i];
}
static void _merge_sort(int *items, int min, int max) {
if (min >= max)
return;
int mid = min + (max - min) / 2;
_merge_sort(items, min, mid);
_merge_sort(items, mid + 1, max);
_merge(items, min, mid + 1, max);
}
static int partition(int *items, int min, int max) {
int pivot = items[max];
int index = min - 1;
int tmp;
for (int j = min; j < max; j++) {
if (items[j] < pivot) {
index++;
tmp = items[index];
items[index] = items[j];
items[j] = tmp;
}
}
tmp = items[index+1];
items[index+1] = items[max];
items[max] = tmp;
return index + 1;
}
static void _quick_sort(int *items, int min, int max) {
if (min >= max)
return;
int index = partition(items, min, max);
_quick_sort(items, min, index - 1);
_quick_sort(items, index + 1, max);
}
void merge_sort(int *items, int length) {
if (!items || length <= 0)
return;
_merge_sort(items, 0, length - 1);
}
void quick_sort(int *items, int length) {
if (!items || length <= 0)
return;
_quick_sort(items, 0, length - 1);
}
|
