本程序包含一个插入排序算法和一个归并排序算法，用c++实现，算法来自《算法导论》第10页，仅供自己备份
// InsertionSort_P10_1.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> using namespace std; #define MAX 10000 int l[100], k[100]; int main() { void insertionSort(int *, int); void mergeSort(int *, int, int); int a[10] = {34, 56, 74, 34, 56, 12, 35, 98, 33, 88}; int c[10] = { 34, 56, 74, 34, 56, 12, 35, 98, 33, 88 }; /* 插入排序算法 */ insertionSort(a, (int) size(a)); for (int i = 0; i < (int) size(a); i++) { cout << a[i] << "\t"; } cout << "结束" << endl; /* 归并排序算法 */ mergeSort(c, 0, (int) size(c)); for (int i = 0; i < (int)size(c); i++) { cout << c[i] << "\t"; } cout << "结束" << endl; return 0; } void insertionSort(int *a, int n) { int key; for (int i = 1; i < n; i++) { key = a[i]; int j = i - 1; while (j >= 0 && a[j] > key) { a[j + 1] = a[j]; j--; } a[j + 1] = key; } } void mergeSort(int *a, int p, int r) { void merge(int *, int, int, int); if (p < r - 1) { int q = (p + r) / 2; mergeSort(a, p, q); mergeSort(a, q, r); merge(a, p, q, r); } } void merge(int *a, int p, int q, int r) { void printArray(int *, int n1, int n2); int i; for (i = p; i < q; i++) { l[i - p] = a[i]; } l[i-p] = MAX; for (i = q; i < r; i++) { k[i - q] = a[i]; } k[i-q] = MAX; int il = 0, ik = 0; for (i = p; i < r; i++) { //cout << "第 " << (i - p) << " 次循环：" << endl; //cout << "\tl:\t"; printArray(l, il, q - p + 1); cout << endl; //cout << "\tk:\t"; printArray(k, ik, r - q + 1); cout << endl; //cout << "\ta:\t"; printArray(a, p, r); cout << endl; if (l[il] <= k[ik]) { a[i] = l[il]; il++; } else { a[i] = k[ik]; ik++; } } } void printArray(int *a, int n1, int n2) { for (int i = n1; i < n2; i++) { cout << a[i] << "\t"; } }