原理请参考算法导论
插入式排序算法实现:
- void insertion_sort(int * A, int length) {
- int i,
- key;
- for (int j = 1; j <length; j++) { // 从第二个开始判断, 保证前面有序
- key = A[j];
- i = j - 1;
- while (i>= 0 && A[i]> key) {
- A[i + 1] = A[i];
- i--;
- }
- A[i + 1] = key; // 插入
- }
- }
递归实现分治, merge 函数实现合并算法实现:
- void merge(int *A, int p, int q, int r) {//q 属于 [q, r]
- // 分治保证 L, R 数组是有序的
int n1, n2, *L, *R, i, j;
n1 = q - p + 1;//[p, q]
n2 = r - q;//(q, r]
- L = new int[n1];
- R = new int[n2];
- for (i = 0; i <n1; i++)
- L[i] = A[p + i];
- for (j = 0; j < n2; j++)
- R[j] = A[q + 1 + j];
- i = j = 0;
- for (int k = p; k <= r; k++) {
- if (j == n2)// 任意一边选完了, 直接进去
- A[k] = L[i++];
- else if (i == n1)
- A[k] = R[j++];
- else {
- if (L[i] < R[j])
- A[k] = L[i++];
- else
- A[k] = R[j++];
- }
- }
- delete[] L;
- delete[] R;
- }
- void merge_sort(int *A, int p, int r) {//p=0, r=n-1
- if (p < r) {
- // 递归实现分治, 和二叉树一样, p<r 自动实现过滤没有用的节点
- merge_sort(A, p, (p + r) / 2);
- merge_sort(A, (p + r) / 2 + 1, r);
- merge(A, p, (p + r) / 2, r);// 此函数实现合并
- }
- }
冒泡算法实现:
- void bubble_sort(int *A, int length) {
- int mid;
- for (int i = 0; i < length; i++) {
- for (int j = length - 1; j> i; j--)
- if (A[j] < A[j - 1]) {// 双双相比
- mid = A[j];
- A[j] = A[j - 1];
- A[j - 1] = mid;
- }
- }
- }
所有代码均经过测试, 结果正确.
来源: http://www.bubuko.com/infodetail-2562996.html