7大排序算法实现程序（快速排序，冒泡排序，选择排序，归并排序，插入排序，希尔排序，堆排序）

/*归并排序算法*/ // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(nlogn) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ O(n) // 稳定性 ------------ 稳定 #include <stdio.h> #include <limits.h> // 包含极限值的头文件，这里用到了无穷大INT_MAX int L[10]; // 两个子数组定义成全局变量（辅助存储空间,大小正比于元素的个数） int R[10]; void merge(int A[], int left, int middle, int right)// 合并两个已排好序的数组A[left...middle]和A[middle+1...right] { int i,j,k; int n1 = middle - left + 1; // 两个数组的大小 int n2 = right - middle; for (i = 0; i < n1; i++) // 把两部分分别拷贝到两个数组中 L[i] = A[left + i]; for (j = 0; j < n2; j++) R[j] = A[middle + j + 1]; L[n1] = INT_MAX; // 使用无穷大作为哨兵值放在子数组的末尾 R[n2] = INT_MAX; // 这样可以免去检查某个子数组是否已读完的步骤 i = 0; j = 0; for (k = left; k <= right; k++) // 依次比较两个子数组中的值，每次取出更小的那一个放入原数组 { if (L[i] <= R[j]) { A[k] = L[i]; i++; } else { A[k] = R[j]; j++; } } } void mergesort_recursion(int A[], int left, int right) // 递归实现的归并排序(自顶向下) { int middle = (left + right) / 2; if (left < right) // 当待排序的序列长度为1时(left == right)，递归“开始回升” { mergesort_recursion(A, left, middle); mergesort_recursion(A, middle + 1, right); merge(A, left, middle, right); } } void mergesort_iteration(int A[], int left, int right) // 非递归(迭代)实现的归并排序(自底向上) { int size; int low, middle, high; // 子数组索引,前一个为A[low...middle],后一个子数组为A[middle+1...high] for (size = 1; size <= right - left; size *= 2) // 子数组的大小初始为1,每轮翻倍 { low = left; while (low + size - 1 <= right - 1 )// 后一个子数组存在(需要归并) { middle = low + size - 1; high = middle + size; if(high > right)// 后一个子数组大小不足size high = right; merge(A, low, middle, high); //合并 low = high + 1; //前一个子数组索引向后移动 } } } int main() { int i; int A1[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; // 从小到大归并排序 int A2[] = { 6, 5, 3, 1, 8, 7, 2, 4 }; int n1 = sizeof(A1) / sizeof(int); int n2 = sizeof(A2) / sizeof(int); mergesort_recursion(A1, 0, n1 - 1); // 递归实现 mergesort_iteration(A2, 0, n2 - 1); // 非递归实现 printf("递归实现的归并排序结果："); for (i = 0; i < n1; i++) { printf("%d ",A1[i]); } printf("\n"); printf("非递归实现的归并排序结果："); for (i = 0; i < n2; i++) { printf("%d ", A2[i]); } printf("\n"); return 0; }