目录
前言
一、代码实现
二、算法的时空复杂度
1.时间复杂度:
2.空间复杂度:
前言
以下算法为二路归并排序。
通俗地讲就是:将需要排序的元素分为两部分,再对这两部分进行归并成一个有序的段。
建议:1.学习算法最重要的是理解算法的每一步,而不是记住算法。
2.建议读者学习算法的时候,自己手动一步一步地运行算法。
一、代码实现
下面是使用C语言实现归并排序的简单示例代码:
#include <stdio.h>
#include <stdlib.h>// 合并两个有序数组
void merge(int arr[], int left, int middle, int right) {int i, j, k;int n1 = middle - left + 1;int n2 = right - middle;// 创建临时数组int L[n1], R[n2];// 将数据复制到临时数组 L[] 和 R[]for (i = 0; i < n1; i++)L[i] = arr[left + i];for (j = 0; j < n2; j++)R[j] = arr[middle + 1 + j];// 合并临时数组到 arr[left..right]i = 0;j = 0;k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}// 将剩余元素复制到 arr[]while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}
}// 归并排序
void mergeSort(int arr[], int left, int right) {if (left < right) {// 计算中间位置int middle = left + (right - left) / 2;// 递归地对左右两部分进行排序mergeSort(arr, left, middle);mergeSort(arr, middle + 1, right);// 合并已排序的两部分merge(arr, left, middle, right);}
}// 打印数组元素
void printArray(int A[], int size) {for (int i = 0; i < size; i++)printf("%d ", A[i]);printf("\n");
}// 主程序
int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);printf("给定数组:\n");printArray(arr, arr_size);// 调用归并排序函数mergeSort(arr, 0, arr_size - 1);printf("\n排序后的数组:\n");printArray(arr, arr_size);return 0;
}
这个程序首先定义了一个用于合并两个有序数组的函数 merge
,然后实现了归并排序的主要逻辑 mergeSort
。最后,在 main
函数中创建一个示例数组,调用 mergeSort
进行排序,并打印排序后的结果。
二、算法的时空复杂度
1.时间复杂度:
最好情况: O(n log n) - 在每次划分时,数组都被均匀地分割为两部分。
最坏情况: O(n^2) - 当数组已经有序或基本有序(比如全部元素相等),每次划分都只能减小一项,导致递归树变得很深。
平均情况: O(n log n) - 在平均情况下,快速排序表现非常好。这是因为每次划分都将数组分为两半,递归树的深度大约为 log n。
2.空间复杂度:
快速排序是一种原地排序算法,不需要额外的空间来存储临时数据。它使用递归来实现分治,但递归调用的栈空间占用是 O(log n) 的。