以体会思想为目的，进行c++算法基本练习。
涉及二分法，迭代器移动，快排。
|
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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
#include <iostream>#include <string>using
namespace
std;
/*二分法找元素，核心思想是二分判断*/int
find_element_in_array(int
*a,int
length,int
element)
{ int
begin, end, mid;
begin = 0;
end = length-1;
mid = (end + begin) / 2;
while
(begin < end && a[mid] != element)
{
if
(a[mid] > element)
{
//cout <<a[mid]<< endl;
end = mid-1;
}
if
(a[mid] < element)
{
//cout << a[mid] << endl;
begin = mid+1;
}
mid = (end + begin) / 2;
}
if
(element == a[mid])
{
cout << "element : "
<< element << " a[mid] : "
<< a[mid] << endl;
}
else
{
cout << "not found "
<< element<<endl;
}
return
0;
}void
main_find_element_in_array()
{ int
array1[10] = { 1, 5, 23, 33, 45, 57, 59, 76, 87, 93 };
find_element_in_array(array1, 10, 59);
}/*第一种，以空间换时间，开辟一个新空间，利用尾迭代器递减，遍历一次size（）*/void
string_reverse_one(const
string str)
{ string temp="";
auto
end = str.cend();
for
(auto
s : str)
{
temp += *(--end);
}
cout << temp << endl;
}void
main_string_reverse_one()
{ string s = "my name is kobe";
string_reverse_one(s);
}/*第二种，字符串翻转的核显思想是，利用迭代器，通过交换头尾迭代器的值，这样只需遍历size（）/2*/void
string_reverse_two(string &str)
{ auto
begin = str.begin();
auto
end = str.end() - 1;
if
(str.size() % 2 != 0)
{
while
(begin != end)
{
auto
t = *end;
*end = *begin;
*begin = t;
begin++;
end--;
}
}
if
(str.size() % 2 == 0)
{
int
cout = 0;
while
(cout != (str.size()/2))
{
auto
t = *end;
*end = *begin;
*begin = t;
begin++;
end--;
cout++;
}
}
}void
main_string_reverse_two()
{ string s = "my name is kobe!";
string_reverse_two(s);
cout << s << endl;
}/*快排的核心思想是，找到当前列表的第一个元素应该在的位置！然后递归剩下位置的数据*/void
swap(int
*a, int
low, int
high)
{ int
temp;
temp = a[low];
a[low] = a[high];
a[high] = temp;
}int
Partition(int
*a, int
low, int
high)
{ int
pivotkey = a[low];
while
(low < high)
{
while
(low < high && a[high] >= pivotkey)
high--;
swap(a, low, high);
while
(low < high && a[low] <= pivotkey)
low++;
swap(a, low, high);
}
return
low;
}void
Qsort(int
*a, int
low, int
high)
{ int
pivot;
if
(low < high)
{
pivot = Partition(a, low, high);
Qsort(a, low, pivot-1);
Qsort(a, pivot+1, high);
}
}void
quick_sort(int
*a, int
length)
{ length = length - 1;
Qsort(a, 0, length);
}void
main_quick_sort()
{ int
array1[10] = { 12, 5, 53, 83, 45, 7, 69, 56, 87, 93 };
quick_sort(array1,10);
for
(int
i : array1)
{
if
(i!=0)
cout << i << ‘ ‘;
}
}void
main()
{ cout << "二分法查找"
<< endl;
main_find_element_in_array();
cout << "翻转字符串方法1"
<< endl;
main_string_reverse_one();
cout << "翻转字符串方法2"
<< endl;
main_string_reverse_two();
cout << "快排排序"
<< endl;
main_quick_sort();
} |