11 thuật toán sắp xếp cơ bản trên mảng- Lập trình C++ cơ bản.

Hi all, "mình là lính mới" nhưng cũng mong được chia sẻ kiến thức của mình với những bạn được coi là "lính mới hơn". bắt đầu luôn nhé!
   Việc sắp xếp dữ liệu là công việc "gặp thường xuyên" của các lập trình viên, có nhiều cách để sắp xếp dữ liệu thông qua các hàm trong thư viện chuẩn, nhưng theo mình thì lập trình viên không nên LƯỜI, hãy cứ code cho dù đó là thứ cơ bản, thứ mà bạn có thể search google một phát là ra. code nhiều sẽ giúp bạn nâng cao tư duy lập trình. Nhưng không phải ai cũng có đủ khả năng để nghĩ ra cách cài đặt thuật toán, vì vậy hôm nay mình xin chia sẻ với các bạn  11 thuật toán sắp xếp, nhưng ở đây chỉ là sắp xếp trên mảng, theo thứ tư tăng dần, hi vọng thông qua đây các bạn sẽ biết thêm những cách "Bá đạo" mà "cha ông" ta ngày xưa truyền lại để sắp xếp :)), ở đây mình chỉ share code thôi, việc tìm hiểu cách chạy của từng thuật toán các bạn tự tìm hiểu, cái này chắc trên lớp các bạn học hết rồi :)
Note: trong bài viết không có shaker sort vì mình nghĩ nó chẳng khác gì bubble sort, mà cài đặt lại dài  ==>bỏ qua.

1. //(1)InterchangeSort

void InterchangeSort(int *A, int n)

1. {
2. int i, j;
3. for (i = 0; i < n - 1; i++)
4. {
5. for (j = i+1; j < n; j++)
6. {
7. if (A[i]>A[j])
8. {
9. swap(A[i], A[j]);
10. }
11. }
12. }
13. }
14. //(2)SelectionSort
15. void SelectionSort(int *A, int n)
16. {
17. int j, i, Min;
18. for (i = 0; i < n + 1; i++)
19. {
20. Min = i;
21. for (j = i + 1; j < n; j++)
22. {
23. if (A[Min]>A[j])
24. {
25. Min= j;
26. }
27. }
28. if (Min!=i)
29. swap(A[i], A[Min]);
30. }
31. }
32. //(3)BubbleSort
33. void BubbleSort(int *A, int n)
34. {
35. int i, j;
36. for (i = 0; i < n - 1; i++)
37. {
38. for (j = n - 1; j>i; j--)
39. {
40. if (A[j] < A[j - 1])
41. {
42. swap(A[j-1], A[j]);
43. }
44. }
45. }
46. }
47. //(4)InsertionSort
48. void InsertionSort(int *A, int n)
49. {
50. int i, pos;
51. int x;
52. for (i = 1; i < n; i++)
53. {
54. pos = i - 1, x = A[i];
55. while ((A[pos]>x) && (pos >= 0))
56. {
57. A[pos + 1] = A[pos];
58. pos--;
59. }
60. A[pos + 1] = x;
61. }
62. }
63. //(5)BinaryInsertionSort
64. void BinaryInsertionSort(int *A, int n)
65. {
66. int left, right, mid, i,j;
67. int x;
68. for (i = 1; i < n; i++)
69. {
70. left = 0, right = i - 1, x = A[i];
71. while (left <= right)
72. {
73. mid = (left + right) / 2;
74. if (A[mid] < x)
75. {
76. left = mid + 1;
77. }
78. else
79. {
80. right = mid - 1;
81. }
82. }
83. for (j = i - 1; j >= left; j--)
84. {
85. A[j + 1] = A[j];
86. }
87. A[left] = x;
88. }
89. }
90. //(6)QuickSort
91. void QuickSort(int *A, int left, int right)
92. {
93. int i = left, j = right;
94. int x = A[(left + right) / 2];
95. while (i < j)
96. {
97. while (A[i] < x)i++;
98. while (A[j]>x)j--;
99. if (i <= j)
100. {
101. swap(A[i], A[j]);
102. i++;
103. j--;
104. }
105. }
106. if (i < right)
107. {
108. QuickSort(A, i, right);
109. }
110. if (j>left)
111. {
112. QuickSort(A, left, j);
113. }
114. }
115. //(7)ShellSort
116. void ShellSort(int *A, int n)
117. {
118. //sap xep bang cach chia nua buoc nhay den khi bang 1
119. int length, pos, i, x;
120. for (length = n / 2; length > 0; length = length / 2)
121. {
122. for (i = length; i < n; i++)
123. {
124. pos = i - length, x = A[i];
125. while ((pos >= 0) && (A[pos]>x))
126. {
127. A[pos + length] = A[pos];
128. pos -= length;
129. }
130. A[pos + length] = x;
131. }
132. }
133. }
134. //(9)HeapSort
135. void shift(int *&A, int left, int right)
136. {
137. int i = left;
138. int j = 2 * i + 1;
139. while(j <= right)
140. {
141. if ((j < right) && (A[j] < A[j + 1])) j++;
142. if (A[i] < A[j])
143. {
144. swap(A[i], A[j]);
145. i = j;
146. j = i * 2 + 1;
147. }
148. else
149. {
150. return;
151. }
152. }
153. }
154. void createHeap(int *A, int n)
155. {
156. int i = n / 2 - 1;
157. while (i >= 0)
158. {
159. shift(A, i, n - 1);
160. i--;
161. }
162. }
163. void HeapSort(int *A, int n)
164. {
165. createHeap(A, n);
166. int r = n - 1;
167. while (r)
168. {
169. swap(A[0], A[r]);
170. r--;
171. if (r>0)
172. shift(A, 0, r);
173. }
174. }
175. //10)Merge Sort
176. void merge(int* array, int left, int mid, int right) {
177.  
178. int *temp1=new int[mid - left + 1];
179. int *temp2=new int[right - mid];
180. int index_array = left;
181.  
182. for (int i = 0; i < mid - left + 1; i++)
183. temp1[i] = array[index_array++];
184.  
185. for (int i = 0; i < right - mid; i++)
186. temp2[i] = array[index_array++];
187.  
188. int index_temp1 = 0, index_temp2 = 0;
189. index_array = left;
190.  
191. while (index_temp1 <= mid - left && index_temp2 < right - mid)
192. {
193. if (temp1[index_temp1] < temp2[index_temp2])
194. {
195. array[index_array] = temp1[index_temp1];
196. index_temp1++;
197. }
198. else
199. {
200. array[index_array] = temp2[index_temp2];
201. index_temp2++;
202. }
203. index_array++;
204. }
205. while (index_temp1 <= mid - left)
206. {
207. array[index_array] = temp1[index_temp1];
208. index_array++;
209. index_temp1++;
210. }
211. while (index_temp2 < right - mid)
212. {
213. array[index_array] = temp2[index_temp2];
214. index_array++;
215. index_temp2++;
216. }
217. }
218. void Merge_sort(int* array, int left, int right) {
219.  
220. int mid = (right + left) / 2;
221. if (left < right) {
222.  
223. Merge_sort(array, left, mid);
224. Merge_sort(array, mid + 1, right);
225. merge(array, left, mid, right);
226. }
227. }
228. //11)Radix Sort
229. void RadixSort(int *a, int n){
230. int i;
231. long long maxExp = 1;
232. for (i = 0; i != n; i++){
233. while (a[i] / maxExp != 0)
234. maxExp *= 10;
235. }
236. long long exp = 1;
237. int *tmpBuffer = new int[n];
238. while (maxExp / exp != 0){
239. int decimalBucket[10] = { 0 };
240. for (i = 0; i != n; i++)
241. decimalBucket[a[i] / exp % 10]++;
242. for (i = 1; i != 10; i++)
243. decimalBucket[i] += decimalBucket[i - 1];
244. for (i = n - 1; i != -1; i--)
245. tmpBuffer[--decimalBucket[a[i] / exp % 10]] = a[i];
246. for (i = 0; i != n; i++)
247. a[i] = tmpBuffer[i];
248. exp *= 10;
249. }
250. }