商务网站建设模块,手机高端设计网站建设,江门网站推广技巧服务,邮箱网址大全号码大全排序#xff0c;是对给定的一组数#xff0c;按照某种逻辑关系#xff0c;进行位置上的移动。由于排序至少需要将所有数过一遍#xff08;正常情况下#xff0c;非特殊数组#xff09;#xff0c;因此排序的时间复杂度一定不能小于O#xff08;N#xff09;。
归并排…排序是对给定的一组数按照某种逻辑关系进行位置上的移动。由于排序至少需要将所有数过一遍正常情况下非特殊数组因此排序的时间复杂度一定不能小于ON。
归并排序通过将一个大数据组分割成一个个小数据组对小数据组排序排好序后再整体排序。
时间复杂度为ONlogN空间复杂度为ON其算法最好、最坏情况下时间复杂度均为ONlogN是一种十分高效的排序算法本质上是一种以空间换时间的算法。
void _merge(int* a, int* tmp, int left1, int right1, int left2, int right2)
{ int left left1;int right right2;int cur left1;while (left1 right1 left2 right2){if (a[left1] a[left2]){tmp[cur] a[left1];}else{tmp[cur] a[left2];}}while (left1 right1){tmp[cur] a[left1];}while (left2 right2){tmp[cur] a[left2];}while (left right){a[left] tmp[left];left;}}void merge(int* a, int* tmp, int left, int right)
{if (left right){return;}int mid(leftright)/2;merge(a, tmp, left, mid);merge(a, tmp, mid 1, right);_merge(a, tmp, left,mid,mid1, right);}// 归并排序递归实现
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc);exit(-1);}merge(a, tmp, 0, n-1);free(tmp);}// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc);exit(-1);}int gap 1;while (gap n){for (int i 0; i n; i 2*gap){int left1 i;int right1 i gap - 1;int left2 i gap;int right2 i 2 * gap - 1;if (right1 n-1){break;}if (right2 n){right2 n - 1;}_merge(a, tmp, left1, right1, left2, right2);}gap * 2;}free(tmp);
}
对于递归的算法就是单纯的不断分割直到只有一个数无法再分割然后在往回不断归并结构上类似二叉树的后序遍历。
对于非递归的算法由于其在逻辑上需要不断进行归并、不断扩大每次归并的数据个数因此很难通过栈的方式模拟实现而是选择了用gap当做当前每次归并时一组数的个数而这里最需要注意的就是数组越界问题即除了begin1之外的数都有可能会越界因此需要判断。当begin2n的时候即第二个数不存在因此不需要归并。当end2n的时候即第二个存在但大小无法到gap个此时缩小end2的大小使得第二组的数据个数为end2-begin21个再与第一组数进行归并。 稳定性
所谓稳定性就是指原本相同的数据的相对位置关系在排序后不发生变化。
常见的排序有冒泡排序、直接插入排序、希尔排序、堆排序、快速排序、归并排序、选择排序。
其中稳定的有冒泡排序、直接插入排序、归并排序
不稳定
1.希尔排序原因是在预排序的时候可能同样的数据在不同的组进行排序导致相对位置变化
2.堆排序原因是堆排序时要把根节点的元素与最后一个元素互换导致数据之间的相对位置变化。
3选择排序原因是找到最大、最小的元素将当前最左、最右测的元素与其互换的时候可能会使得位置发生改变。
4快速排序每次将最左侧的元素放到最终位置时可能会导致相对位置改变。
