企业网站开发需要多钱,北京网站建设公司分享网站改版注意事项,找人做seo要给网站程序,正规的建网站公司目录
归并排序
归并排序的时间复杂度 排序的稳定性
排序总结 归并排序 归并排序大家只需要掌握其递归方法即可#xff0c;非递归方法由于在某些特殊场景下边界难控制#xff0c;我们一般很少使用非递归实现归并排序。那么归并排序的递归方法我们究竟是怎样实现呢#xff…目录
归并排序
归并排序的时间复杂度 排序的稳定性
排序总结 归并排序 归并排序大家只需要掌握其递归方法即可非递归方法由于在某些特殊场景下边界难控制我们一般很少使用非递归实现归并排序。那么归并排序的递归方法我们究竟是怎样实现呢 大家先想象一下这样一种场景如果现在有两个数我们要将这两个数排成升序怎样呢很简单我们只需要将两个数进行一次大小的比较即可比较完之后小的元素放在前面大的元素放在后面其实这就是很简单的一次归并排序两个素比较之后交换使得两个元素变得有序的场景我们就称作一次归并。 我们再次深入分析如果有两个元素这两个元素可以直接比较且比较之后两个数就变得有序以此类推如果们要对4个元素进行归并排序按照此逻辑将两两分成一组然后这两组进行一次比较比较完成之后这4个元素应该就变有序了但是事实真是这样吗通过示意图为大家讲解 为什么两个元素互相比较就可以变得有序呢 这是因为当一个数组中只有一个数时我们就可以称这个数组是有序的当数组中有两个元素时我们可以将这两个数每一个数都看成一个数组此时这两个数组都是有序的两个有序的数组元素之间依次比较肯定会将最终的整个数组变得有序所以我们要使四个数组变得有序可以将数组分成左右两个数组当我们使左右两个数组有序时再将左右两个数组的元素依次进行比较这样最终四个数组成的数组就会有序。以此归并排序的递归思路就出来了 通过四个元素的数组为大家图示讲解归并排序的思想 归并排序的思想我们要对一个数组进行归并排序使它变得有序我们就得先将这个数组分成左右两部分相对左边这部分数组进行归并排序然后再对右边这部分数组进行归并排序左右两边的数组排好序之后对左右两个数组的元素进行一次比较我们也成对左右两个数组的元素进行归并然后整个数组的归并排序就完成了。
归并排序的整体代码
void _MergeSort(int* a, int left, int right, int* tmp)
{if (left right)return;int mid (right left) / 2;_MergeSort(a, left, mid, tmp);_MergeSort(a, mid 1, right, tmp);int begin1 left, begin2 mid 1;int end1 mid, end2 right;int i left;//左右数组有序之后就需要左右数组进行归并while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}//左右两个数组当一个数组归并完时一个数组可能还没有归并完将没有归并完的这个数组的元素依次赋值给中间数组while (begin1 end1){tmp[i] a[begin1];}while (begin1 end1){tmp[i] a[begin2];}for (int j 0; j right 1; j){a[j] tmp[j];}
}
void MergeSort(int* a, int size)
{int* tmp (int*)malloc(sizeof(int) * size);if (tmp NULL){printf(malloc fail);exit(-1);}_MergeSort(a, 0, size - 1, tmp);free(tmp);tmp NULL;
}
int main()
{int arr[] {99,88,66,77,55,44,33,22,11 };MergeSort(arr,sizeof(arr)/sizeof(int));for (int i 0; i sizeof(arr) / sizeof(int); i){printf(%d , arr[i]);}return 0;
}
运行截图 归并排序的时间复杂度 时间复杂度O(N*logN) 稳定性:稳定 排序的稳定性 什么是排序的稳定性呢 其实就是在未排序之前数组中有两个相同的元素有顺序如果在排序之后这两个元素的顺序没有发生变化则称这个排序是稳定的如果排序之后顺序发生了变化我们就称这个排序算法是不稳定的。 排序总结 直接插入排序最好的情况下就是一个有序数组插入的元素只用跟前面数组的最后一个元素比较最好复杂度为O(N)。最坏的情况就是一个逆序数组每个要插入的元素都要和前面的数组元素比较一下就是等差数列求和O(N^2) 希尔排序时间复杂度不好计算大概是O(N^1.3) 选择排序没有最好和最坏编译器不知道所以每个元素都和最小的元素比较一次一趟排序确定了一元素的位置剩下的元素下一趟继续进行比较时间复杂度为等差数列求和O(N^2) 堆排序没有最好和最坏因为都是从一个大堆或者小堆进行调整为O(N*logN) 冒泡排序有序时我们有优化一趟比较下来没有发生交换所以终止后面的排序但是第一趟的相邻两个元素都发生了比较比较了N次所以最好时间复杂度为O(N),最坏逆序等差数列求和O(N^2) 快速排序最好每次找到的key都在中间所以刚好是一个满二叉树高度为logN每层比较N次总共比较N*logN次所以最好为O(N*logN) 最坏一个有序数组每次找的key都在最左边总共N层比较等差数列求和次所以最坏为O(N^2) 归并排序最好最坏都是O(N*logN) 只有快速排序和归并排序他们俩才会消耗额外额空间因为递归要频繁的消耗栈帧且快排非递归实现时运用了栈的数据结构。 好了到此常见的排序算法我们已经全部学写完成了排序算法是面试中的重点大家一定要掌握。
好了本期的内容到此结束^_^
