2.1 插入排序
#include <stdio.h>
#include <stdlib.h>
#define TRACE_SUBSTEPS 1
void func2_1() {
int A[] = {5, 2, 4, 6, 1, 3, 10, 3, 5};
int key = 0;
int j = 0, i = 0, k = 0;
//============print sub title===============
printf("2.1 Insertion-Sort\n\n");
//============print old Array===============
printf("Old Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
if (sizeof(A)/sizeof(int) <= 1) {
goto l_done;
}
//==================INSERTION-SORT==============
for (j = 1; j < sizeof(A)/sizeof(int); j++) {
key = A[j];
i = j - 1;
while(i >= 0 && A[i] > key) {
A[i+1] = A[i];
i = i - 1;
}
A[i + 1] = key;
#if TRACE_SUBSTEPS
printf("\tj=%d, and result:\n\t\tA[] = ", j);
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
#endif //TRACE_SUBSTEPS
}
l_done:
//============print sorted ARRAY=================
printf("Sorted Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
}
注意： 伪代码里数组下标是从1开始数的。
运行结果:
================第2章 算法基础==============
2.1 Insertion-Sort
Old Array: A[] = {5, 2, 4, 6, 1, 3, 10, 3, 5}
j=1, and result:
A[] = {2, 5, 4, 6, 1, 3, 10, 3, 5}
j=2, and result:
A[] = {2, 4, 5, 6, 1, 3, 10, 3, 5}
j=3, and result:
A[] = {2, 4, 5, 6, 1, 3, 10, 3, 5}
j=4, and result:
A[] = {1, 2, 4, 5, 6, 3, 10, 3, 5}
j=5, and result:
A[] = {1, 2, 3, 4, 5, 6, 10, 3, 5}
j=6, and result:
A[] = {1, 2, 3, 4, 5, 6, 10, 3, 5}
j=7, and result:
A[] = {1, 2, 3, 3, 4, 5, 6, 10, 5}
j=8, and result:
A[] = {1, 2, 3, 3, 4, 5, 5, 6, 10}
Sorted Array: A[] = {1, 2, 3, 3, 4, 5, 5, 6, 10}
请按任意键继续. . .
习题:2.1-2
#include <stdio.h>
#include <stdlib.h>
#define TRACE_SUBSTEPS 1
void func2_1_1() {
int A[] = {5, 2, 4, 6, 1, 3, 10, 3, 5};
int key = 0;
int j = 0, i = 0, k = 0;
//============print sub title===============
printf("2.1-1 Insertion-Sort\n\n");
//============print old Array===============
printf("Old Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
if (sizeof(A)/sizeof(int) <= 1) {
goto l_done;
}
//==================INSERTION-SORT==============
for (j = (sizeof(A)/sizeof(int) - 2); j >= 0; j--) {
key = A[j];
i = j + 1;
while(i< (sizeof(A)/sizeof(int)) && A[i] > key) {
A[i-1] = A[i];
i++;
}
A[i-1] = key;
#if TRACE_SUBSTEPS
printf("\tj=%d, and result:\n\t\tA[] = ", j);
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
#endif //TRACE_SUBSTEPS
}
l_done:
//============print sorted ARRAY=================
printf("Sorted Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
}
运行结果:
================第2章 算法基础==============
2.1-1 Insertion-Sort
Old Array: A[] = {5, 2, 4, 6, 1, 3, 10, 3, 5}
j=7, and result:
A[] = {5, 2, 4, 6, 1, 3, 10, 5, 3}
j=6, and result:
A[] = {5, 2, 4, 6, 1, 3, 10, 5, 3}
j=5, and result:
A[] = {5, 2, 4, 6, 1, 10, 5, 3, 3}
j=4, and result:
A[] = {5, 2, 4, 6, 10, 5, 3, 3, 1}
j=3, and result:
A[] = {5, 2, 4, 10, 6, 5, 3, 3, 1}
j=2, and result:
A[] = {5, 2, 10, 6, 5, 4, 3, 3, 1}
j=1, and result:
A[] = {5, 10, 6, 5, 4, 3, 3, 2, 1}
j=0, and result:
A[] = {10, 6, 5, 5, 4, 3, 3, 2, 1}
Sorted Array: A[] = {10, 6, 5, 5, 4, 3, 3, 2, 1}
请按任意键继续. . .
2.2-2 选择排序
#include <stdio.h>
#include <stdlib.h>
#define TRACE_SUBSTEPS 1
void func2_2_2() {
int A[] = {5, 2, 4, 6, 1, 3, 10, 3, 11};
int j = 0, i = 0, z = 0, k = 0;
int tmp = 0;
//============print sub title===============
printf("2.2-2 Selection-Sort\n\n");
//============print old Array===============
//FIXME: A has 1 member.
printf("Old Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
if (sizeof(A)/sizeof(int) <= 1) {
goto l_done;
}
//=============SELECTION-SHORT=================
for (j = 0; j < (sizeof(A)/sizeof(int) - 1); ++j) {
i = j + 1;
z = j;
for(; i < (sizeof(A)/sizeof(int)); ++i) {
if (A[z] > A[i]) {
z = i;
}
}
if ( k != j) {
tmp = A[j];
A[j] = A[z];
A[z] = tmp;
}
#if TRACE_SUBSTEPS
//FIXME: A has 1 member.
printf("\tj=%d, and result:\n\t\tA[] = ", j);
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
#endif //TRACE_SUBSTEPS
}
l_done:
//============print sorted ARRAY=================
//FIXME: A has 1 member.
printf("Sorted Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
}
运行结果:
================第2章 算法基础==============
2.2-2 Selection-Sort
Old Array: A[] = {5, 2, 4, 6, 1, 3, 10, 3, 11}
j=0, and result:
A[] = {1, 2, 4, 6, 5, 3, 10, 3, 11}
j=1, and result:
A[] = {1, 2, 4, 6, 5, 3, 10, 3, 11}
j=2, and result:
A[] = {1, 2, 3, 6, 5, 4, 10, 3, 11}
j=3, and result:
A[] = {1, 2, 3, 3, 5, 4, 10, 6, 11}
j=4, and result:
A[] = {1, 2, 3, 3, 4, 5, 10, 6, 11}
j=5, and result:
A[] = {1, 2, 3, 3, 4, 5, 10, 6, 11}
j=6, and result:
A[] = {1, 2, 3, 3, 4, 5, 6, 10, 11}
j=7, and result:
A[] = {1, 2, 3, 3, 4, 5, 6, 10, 11}
Sorted Array: A[] = {1, 2, 3, 3, 4, 5, 6, 10, 11}
请按任意键继续. . .
2.3 归并排序(分治法)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define TRACE_SUBSTEPS 1
#define MAX_VALUE INT_MAX
static void merge(int *A, int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int *L = (int *)malloc((n1 + 1) * sizeof(int));
int *R = (int *)malloc((n2 + 1) * sizeof(int));
int i = 0, j = 0, k = 0;
if (L == NULL || R == NULL) {
printf("Error: Out of memery!\n");
goto l_ret;
}
//Here, don't use memcpy function.
for (i = 0; i < n1; i++) {
L[i] = A[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = A[q + 1 + j];
}
L[n1] = MAX_VALUE;
R[n2] = MAX_VALUE;
i = 0; j = 0;
for ( k = p; k <= r; k++) {
if (L[i] < R[j]) {
A[k] = L[i];
i++;
} else {
A[k] = R[j];
j++;
}
}
l_ret:
if (L)
free(L);
if (R)
free(R);
}
static void merge_sort(int *A, int p, int r) {
int q = 0;
if (p < r) {
q = (p + r)/2;
merge_sort(A, p, q);
merge_sort(A, q + 1, r);
merge(A, p, q, r);
}
}
void func2_3() {
int A[] = {5, 2, 4, 6, 1, 3, 10, 3, 11};
int k = 0;
//============print sub title===============
printf("2.3 Divide&Conquer-Sort\n\n");
//============print old Array===============
//FIXME: A has 1 member.
printf("Old Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
merge_sort(A, 0, sizeof(A)/sizeof(int) - 1);
//============print sorted ARRAY=================
//FIXME: A has 1 member.
printf("Sorted Array: A[] = ");
for (k = 0; k < sizeof(A)/sizeof(int); k++) {
if (k == 0) {
printf("{%d,", A[k]);
} else if ( k == (sizeof(A)/sizeof(int) - 1)) {
printf(" %d}\n", A[k]);
} else {
printf(" %d,", A[k]);
}
}
}
运行结果:
================第2章 算法基础==============
2.3 Divide&Conquer-Sort
Old Array: A[] = {5, 2, 4, 6, 1, 3, 10, 3, 11}
Sorted Array: A[] = {1, 2, 3, 3, 4, 5, 6, 10, 11}
请按任意键继续. . .