1，实现random_shuffle：random_shuffle是STL中的一个模板算法，作用是随机重排列一对random access iterator之间的元素。基本思想是：假设序列有n个元素，先从所有元素中选一个放到位置1（即与位置1的元素交换），然后再从剩下的n-1个元素中选择一个放到位置2，以此类推。
2，qsort：partition之后双向递归。
qsort的实现：
View Code
1
#include
<
string
.h
>
/*
memcpy
*/
2
3
#define
SWAP_ELEM(pl, pr, size) do {\
4
char
temp[size];
/*
C99
*/
\
5
memcpy(temp, pl, size); \
6
memcpy(pl, pr, size); \
7
memcpy(pr, temp, size); \
8
}
while
(
0
)
9
10
char
*
partition(
char
*
pl,
char
*
pr, size_t size,
int
pivot_index,
11
int
(
*
compare_func)(
const
void
*
,
const
void
*
))
12
{
13
char
*
pivot;
14
char
*
next_less;
//
pointer to the next slot for elements
15
//
with value less than the pivot.
16
17
//
1, swap the pivot element to the last slot.
18
pivot
=
pl
+
size
*
pivot_index;
19
SWAP_ELEM(pr, pivot, size);
20
pivot
=
pr;
21
//
2, move elements with value less than pivot to the front of the sequence.
22
next_less
=
pl;
23
while
(pl
<
pr) {
24
if
(compare_func(pl, pivot)
<
0
) {
25
SWAP_ELEM(pl, next_less, size);
26
next_less
+=
size;
27
}
28
pl
+=
size;
29
}
30
//
3, swap the pivot to its place
31
SWAP_ELEM(next_less, pivot, size);
32
return
next_less;
33
}
34
35
void
do_my_qsort(
char
*
pl,
char
*
pr, size_t size,
36
int
(
*
compare_func)(
const
void
*
,
const
void
*
))
37
{
38
if
(pr
<=
pl) {
//
0 or 1 element
39
return
;
40
}
41
42
if
(pr
-
pl
==
size) {
//
2 elements
43
if
(compare_func(pl, pr)
>
0
)
44
SWAP_ELEM(pl, pr, size);
45
return
;
46
}
47
48
//
more than 2 elements, divide & conquer.
49
//
1, partition the sequence, pivot is chosen to be the leftmost element.
50
char
*
new_pivot
=
partition(pl, pr, size,
0
, compare_func);
51
//
2, recursively enter two subsequences.
52
do_my_qsort(pl, new_pivot
-
size, size, compare_func);
53
do_my_qsort(new_pivot
+
size, pr, size, compare_func);
54
}
55
56
/*
Implementation of libc-qsort.
*/
57
void
my_qsort(
void
*
base
, size_t nmemb, size_t size,
58
int
(
*
compare_func)(
const
void
*
,
const
void
*
))
59
{
60
char
*
pbase
=
base
;
61
char
*
plast
=
base
+
nmemb
*
size
-
size;
//
start addr of the last element.
62
63
do_my_qsort(pbase, plast, size, compare_func);
64
}
65
66
#undef
SWAP_ELEM
qsort的测试：
View Code
1
#include
<
stdio.h
>
2
#include
<
stdlib.h
>
3
#include
<
string
.h
>
4
#include
<
time.h
>
5
#include
<
assert.h
>
6
7
void
my_qsort(
void
*
base
, size_t nmemb, size_t size,
8
int
(
*
compare_func)(
const
void
*
,
const
void
*
));
9
10
#define
MAX_N 27
11
int
arr[MAX_N];
12
13
void
print_arr(
void
)
14
{
15
int
i;
16
17
for
(i
=
0
; i
<
MAX_N; i
++
)
18
printf(
"
%d
"
, arr[i]);
19
printf(
"
\n
"
);
20
}
21
22
/*
A simplified version of the STL algorithm random_shuffle
*/
23
void
my_random_shuffle(
int
*
arr,
int
n)
24
{
25
int
i;
26
27
srand(time(
0
));
28
for
(i
=
1
; i
<
n; i
++
) {
29
int
selected_index
=
rand()
%
(i
+
1
);
//
OK, forgive my using rand(),
30
//
which is of limited random digits.
31
int
temp
=
arr[selected_index];
//
swap to current position.
32
arr[selected_index]
=
arr[i];
33
arr[i]
=
temp;
34
}
35
/*
equivalent to:
36
for (i = n - 1; i > 0; i--) {
37
int selected_index = rand() % (i + 1); // select a random element.
38
int temp = arr[selected_index]; // swap to current position.
39
arr[selected_index] = arr[i];
40
arr[i] = temp;
41
}
42
*/
43
}
44
45
int
comp(
const
void
*
lhs,
const
void
*
rhs)
46
{
47
return
*
(
int
*
)lhs
-
*
(
int
*
)rhs;
48
}
49
50
int
main(
int
argc,
char
*
argv[])
51
{
52
int
i;
53
54
for
(i
=
0
; i
<
MAX_N; i
++
)
55
arr[i]
=
MAX_N
-
1
-
i;
56
//
case #1, sequence of 1 element
57
printf(
"
case #1: \n
"
);
58
my_qsort(arr,
1
,
sizeof
(arr[
0
]), comp);
59
print_arr();
60
//
case #2, sequence of 2 elements
61
printf(
"
case #2: \n
"
);
62
my_qsort(arr,
2
,
sizeof
(arr[
0
]), comp);
63
print_arr();
64
//
case #3, sequence of 3 elements
65
printf(
"
case #3: \n
"
);
66
my_qsort(arr,
3
,
sizeof
(arr[
0
]), comp);
67
print_arr();
68
69
//
case #4, all 0's
70
printf(
"
case #4: \n
"
);
71
for
(i
=
0
; i
<
MAX_N; i
++
)
72
arr[i]
=
0
;
73
my_qsort(arr, MAX_N,
sizeof
(arr[
0
]), comp);
74
print_arr();
75
76
//
case #5, ascent sequence.
77
printf(
"
case #5: \n
"
);
78
for
(i
=
0
; i
<
MAX_N; i
++
)
79
arr[i]
=
i;
80
my_qsort(arr, MAX_N,
sizeof
(arr[
0
]), comp);
81
print_arr();
82
83
//
case #6, descent sequence.
84
printf(
"
case #6: \n
"
);
85
for
(i
=
0
; i
<
MAX_N; i
++
)
86
arr[i]
=
MAX_N
-
1
-
i;
87
my_qsort(arr, MAX_N,
sizeof
(arr[
0
]), comp);
88
print_arr();
89
90
//
case #7, random permutated sequence.
91
printf(
"
case #7: \n
"
);
92
for
(i
=
0
; i
<
MAX_N; i
++
)
93
arr[i]
=
i;
94
my_random_shuffle(arr, MAX_N);
95
print_arr();
96
//
qsort(arr, MAX_N, sizeof(arr[0]), comp);
97
//
print_arr();
98
my_qsort(arr, MAX_N,
sizeof
(arr[
0
]), comp);
99
print_arr();
100
101
return
0
;
102
}
