Skip to content

Commit 94c58f0

Browse files
SheyQSheyQ
authored
Add files via upload
1 parent 68399d2 commit 94c58f0

10 files changed

Lines changed: 419 additions & 0 deletions

File tree

‎Algorithm/binarysearch.cpp‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
template<class T>
2+
int binarysearch(T* arr, int length, int target)
3+
{
4+
int left = 0, right = length - 1;
5+
int mid = 0;
6+
if (length == 0) return -1;
7+
while (left <= right)
8+
{
9+
//mid=(left+right)/2;
10+
//防止溢出
11+
mid = left + (right - left) / 2;
12+
if (target > arr[mid])
13+
{
14+
left = mid + 1;
15+
}
16+
else if (target < arr[mid])
17+
{
18+
right = mid - 1;
19+
}
20+
else
21+
return mid;
22+
}
23+
return -1;
24+
}

‎Algorithm/bubblesort.cpp‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
#include<algorithm>
2+
#include<iostream>
3+
template<class T>
4+
void bubblesort(T* arr, int length)
5+
{
6+
if (length <= 1) return;
7+
for (int i = 0; i < length; ++i)
8+
{
9+
for (int j = length - 1; j > i; --j)
10+
{
11+
if (arr[j] < arr[j - 1])
12+
std::swap(arr[j], arr[j - 1]);
13+
}
14+
}
15+
}
16+
17+
int main(int argc, char const *argv[])
18+
{
19+
//1 2 2 3 3 5 5 7 8
20+
int arr[] = {8, 5, 3, 2, 1, 5, 7, 2, 3};
21+
bubblesort(arr, 9);
22+
for (auto i : arr)
23+
{
24+
std::cout << i << " ";
25+
}
26+
return 0;
27+
}

‎Algorithm/heap.cpp‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
#include"heap.h"
2+
void Heap::siftdown(int pos, compare comp)
3+
{
4+
while (!isLeaf(pos))
5+
{
6+
int temp, temppos;
7+
if (rightchild(pos) < heapsize && !comp(_vec[leftchild(pos)] , _vec[rightchild(pos)]))
8+
{
9+
temppos = rightchild(pos);
10+
temp = _vec[temppos];
11+
}
12+
else
13+
{
14+
temppos = leftchild(pos);
15+
temp = _vec[temppos];
16+
}
17+
if (!comp(_vec[pos] , temp))
18+
{
19+
swap(_vec[pos], _vec[temppos]);
20+
pos = temppos;
21+
}
22+
else return;
23+
}
24+
}
25+
26+
void Heap::insert(int value)
27+
{
28+
int curr = heapsize++;
29+
_vec.push_back(value);
30+
while (curr != 0)
31+
{
32+
if (_vec[curr] < _vec[parent(curr)])
33+
{
34+
swap(_vec[curr], _vec[parent(curr)]);
35+
curr = parent(curr);
36+
}
37+
else break;
38+
}
39+
}
40+
41+
int Heap::remove(int pos)
42+
{
43+
if (pos == heapsize - 1)
44+
{
45+
_vec.pop_back();
46+
heapsize--;
47+
}
48+
else
49+
{
50+
swap(_vec[pos], _vec[--heapsize]);
51+
_vec.pop_back();
52+
while (pos != 0 && _vec[pos] < _vec[parent(pos)])
53+
{
54+
swap(_vec[pos], _vec[parent(pos)]);
55+
pos = parent(pos);
56+
}
57+
if (heapsize != 0) siftdown(pos, comp);
58+
}
59+
return _vec[heapsize];
60+
}
61+
62+
int Heap::removeroot()
63+
{
64+
if (heapsize == 0) return -1;
65+
int res = _vec[0];
66+
swap(_vec[0], _vec[--heapsize]);
67+
_vec.pop_back();
68+
if (heapsize != 0) siftdown(0, comp);
69+
return res;
70+
}
71+
72+
73+
// int main(int argc, char const *argv[])
74+
// {
75+
// //test
76+
// Heap MinHeapByList{1, 2, 4, 3, 4, 6, 8, 1, 6, 4, 2};
77+
// Heap MaxHeapByList({1, 2, 4, 3, 4, 6, 8, 1, 6, 4, 2}, greater<int>());
78+
// vector<int> vec{3, 3, 6, 6, 7, 3, 5, 7, 1, 6};
79+
// Heap MinHeapByvector(vec);
80+
// Heap MaxHeapByvector(vec, greater<int>());
81+
// MinHeapByList.printHeap();
82+
// MaxHeapByList.printHeap();
83+
// MinHeapByvector.printHeap();
84+
// MaxHeapByvector.printHeap();
85+
// cout << MinHeapByvector.remove(1) << MaxHeapByvector.remove(1) << MinHeapByList.remove(1) << MaxHeapByList.remove(1);
86+
// return 0;
87+
// }

‎Algorithm/heap.h‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
#include<iostream>
2+
#include<vector>
3+
#include<algorithm>
4+
#include<utility>
5+
#include<functional>
6+
using namespace std;
7+
8+
class Heap
9+
{
10+
11+
typedef function<bool(int, int)> compare;
12+
13+
private:
14+
vector<int> _vec;
15+
int heapsize;
16+
compare comp;
17+
public:
18+
Heap() = delete;
19+
~Heap() = default;
20+
21+
//default minheap
22+
//c++11 construct with list
23+
//such as Heap{4,3,2,1}
24+
Heap(initializer_list<int> list, compare c = less<int>()): _vec(list.begin(), list.end()), heapsize(list.size()), comp(c)
25+
{
26+
for (int i = heapsize / 2 - 1; i >= 0; --i)
27+
siftdown(i, comp);
28+
}
29+
30+
//construct with vector
31+
Heap(vector<int> vec, compare c = less<int>()): _vec(vec.begin(), vec.end()), heapsize(vec.size()), comp(c)
32+
{
33+
for (int i = heapsize / 2 - 1; i >= 0; --i)
34+
siftdown(i, comp);
35+
}
36+
void siftdown(int pos, compare comp);
37+
void insert(int value);
38+
int remove(int pos);
39+
int removeroot();
40+
41+
int size()
42+
{
43+
return heapsize;
44+
}
45+
46+
bool isLeaf(int pos) const
47+
{
48+
return pos >= heapsize / 2 && pos < heapsize;
49+
}
50+
51+
int parent(int pos) const
52+
{
53+
return (pos - 1) / 2;
54+
}
55+
56+
int leftchild(int pos) const
57+
{
58+
return pos * 2 + 1;
59+
}
60+
61+
int rightchild(int pos) const
62+
{
63+
return pos * 2 + 2;
64+
}
65+
66+
void printHeap()
67+
{
68+
for (int i = 0; i < heapsize; i++)
69+
{
70+
cout << _vec[i] << " ";
71+
}
72+
cout << endl;
73+
}
74+
};

‎Algorithm/heapsort.cpp‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
#include"heap.h"
2+
3+
typedef function<bool(int, int)> compare;
4+
5+
void heapsort(vector<int>& vec, compare comp = less<int>()) //只接受vector容器,默认从小到大排序
6+
{
7+
Heap myheap(vec, comp);
8+
vec.clear();
9+
while (myheap.size() > 0)
10+
{
11+
vec.push_back(myheap.removeroot());
12+
}
13+
}
14+
15+
int main(int argc, char const *argv[])
16+
{
17+
//1 2 2 3 3 5 5 7 8
18+
vector<int> myvec = {8, 5, 3, 2, 1, 5, 7, 2, 3};
19+
heapsort(myvec);
20+
for (auto i : myvec)
21+
{
22+
std::cout << i << " ";
23+
}
24+
std::cout << endl;
25+
26+
//8 7 5 5 3 3 2 2 1
27+
heapsort(myvec, greater<int>());
28+
for (auto i : myvec)
29+
{
30+
std::cout << i << " ";
31+
}
32+
std::cout << endl;
33+
return 0;
34+
}

‎Algorithm/insertsort.cpp‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
#include<algorithm>
2+
#include<iostream>
3+
template<class T>
4+
void insertsort(T* arr, int length)
5+
{
6+
for (int i = 1; i < length; i++)
7+
{
8+
for (int j = i; j > 0; j--)
9+
{
10+
if (arr[j] < arr[j - 1])
11+
std::swap(arr[j], arr[j - 1]);
12+
else
13+
break;
14+
}
15+
}
16+
}
17+
18+
int main(int argc, char const *argv[])
19+
{
20+
//1 2 2 3 3 5 5 7 8
21+
int arr[] = {8, 5, 3, 2, 1, 5, 7, 2, 3};
22+
insertsort(arr, 9);
23+
for (auto i : arr)
24+
{
25+
std::cout << i << " ";
26+
}
27+
return 0;
28+
}

‎Algorithm/mergesort.cpp‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
#include<iostream>
2+
#include<algorithm>
3+
4+
template<class T>
5+
void mergesort(T* arr, T* temp, int start, int end)
6+
{
7+
int mid = (start + end) / 2;
8+
if (start == end) return;
9+
mergesort(arr, temp, start, mid);
10+
mergesort(arr, temp, mid + 1, end);
11+
for (int i = start; i <= end; ++i)
12+
{
13+
temp[i] = arr[i];
14+
}
15+
int i1 = start, i2 = mid + 1;
16+
for (int i = start; i <= end; i++)
17+
{
18+
if (i1 == mid + 1)
19+
{
20+
arr[i] = temp[i2++];
21+
}
22+
else if (i2 == end + 1)
23+
{
24+
arr[i] = temp[i1++];
25+
}
26+
else if (temp[i1] < temp[i2])
27+
{
28+
arr[i] = temp[i1++];
29+
}
30+
else
31+
{
32+
arr[i] = temp[i2++];
33+
}
34+
}
35+
}
36+
37+
int main(int argc, char const *argv[])
38+
{
39+
//1 2 2 3 3 5 5 7 8
40+
int arr[] = {8, 5, 3, 2, 1, 5, 7, 2, 3};
41+
int temp[9] = {0};
42+
mergesort(arr, temp, 0, 8);
43+
for (auto i : arr)
44+
{
45+
std::cout << i << " ";
46+
}
47+
return 0;
48+
}

‎Algorithm/quicksort.cpp‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
#include<algorithm>
2+
#include<iostream>
3+
4+
template<class T>
5+
void quicksort(T* arr, int start, int end)
6+
{
7+
if (start >= end) return;
8+
int i = start + 1, j = end, pivot = arr[start]; //轴值的选择多种多样，最稳当的方式是三点中值法(Median-of-Three)，这里简单的选择数组第一个值arr[start]为轴值
9+
while (i < j)
10+
{
11+
while (j != 0 && arr[j] > pivot) j--;
12+
while (i != j && arr[i] < pivot) i++;
13+
if (i < j)
14+
std::swap(arr[i++], arr[j--]);
15+
}
16+
std::swap(arr[j], arr[start]);
17+
quicksort(arr, start, j - 1);
18+
quicksort(arr, j + 1, end);
19+
}
20+
21+
int main(int argc, char const *argv[])
22+
{
23+
//1 2 2 3 3 5 5 7 8
24+
int arr[] = {8, 5, 3, 2, 1, 5, 7, 2, 3};
25+
quicksort(arr, 0, 8);
26+
for (auto i : arr)
27+
{
28+
std::cout << i << " ";
29+
}
30+
return 0;
31+
}

0 commit comments

Comments
 (0)