1 //============================================================================
2 // Name : suanfa.cpp
3 // Author : dream
4 // Version :
5 // Copyright : powered by YeQiangWei
6 // Description : Hello World in C++, Ansi-style
7 //============================================================================
8
9 #include <iostream>
10 using namespace std;
11 /*默認都安升序排列*/
12 class Algorithm {
13 public:
14 /*分治法*/
15 void merge_sort(int* a, int p, int r);
16 void merge(int* a, int p, int q, int r);
17 /**選擇排序*/
18 void select_sort(int* a, int length);
19 /*插入排序*/
20 void insert_sort(int* a, int length);
21 /*冒泡排序*/
22 void bubble_sort(int* a, int length);
23 };
24 void Algorithm::bubble_sort(int* a, int length) {
25 for (int i = 1; i < length; i++) {
26 for (int j = 0; j <= i; j++) {
27 if (a[i] < a[j]) {
28 int key = a[j];
29 a[j] = a[i];
30 a[i] = key;
31 }
32 }
33
34 }
35 }
36 void Algorithm::insert_sort(int* a, int length) {
37 cout << length << endl;
38 for (int i = 1; i < length; i++) {
39 int j = i - 1;
40 int key = a[i];
41 while (j >= 0 && key < a[j]) {
42 a[j + 1] = a[j];
43 j--;
44 }
45 a[j + 1] = key;
46 }
47 }
48 void Algorithm::merge(int* a, int p, int q, int r) {
49 int n1 = q - p + 1;
50 int n2 = r - q;
51 int* L = new int[n1 + 1];
52 int* R = new int[n2 + 1];
53 for (int m = 0; m < n1; m++) {
54 L[m] = a[p + m];
55 }
56 for (int n = 0; n < n2; n++) {
57 R[n] = a[q + n + 1];
58 }
59 int i = 0;
60 int j = 0;
61 for (int k = p; k <= r; k++) {
62 if (L[i] <= R[j]) {
63 a[k] = L[i];
64 i++;
65 } else {
66 a[k] = R[j];
67 j++;
68 }
69 }
70 }
71
72 void Algorithm::merge_sort(int* a, int p, int r) {
73
74 int q = 0;
75 //cout << "這里其實還是執(zhí)行了的" << q << endl;
76 if (p < r) {
77 q = (p + r) / 2;
78 merge_sort(a, p, q);
79 merge_sort(a, q + 1, r);
80 merge(a, p, q, r);
81 }
82 }
83
84 void Algorithm::select_sort(int* a, int length) {
85 if (NULL == a)
86 return;
87 cout << length << endl;
88 for (int i = 0; i < length; i++) {
89 for (int j = i; j < length; j++) {
90 if (a[i] > a[j]) {
91 cout << "a[]=" << a[i] << endl;
92 int key = a[i];
93 a[i] = a[j];
94 a[j] = key;
95 }
96 }
97 }
98 }
99
100 int main() {
101 int a[] = { 3, 5, 7, 9, 4, 8, 2, 1 };
102 int length = sizeof(a) / sizeof(a[0]);
103 Algorithm al;
104 al.bubble_sort(a, length);
105 for (size_t i = 0; i < (sizeof(a) / sizeof(a[0])); i++) {
106 cout << a[i] << " ";
107 }
108 return 0;
109 }
110
111
112