网站上线如何做压力测试济南网站推广
排序,是对给定的一组数,按照某种逻辑关系,进行位置上的移动。由于排序至少需要将所有数过一遍(正常情况下,非特殊数组),因此排序的时间复杂度一定不能小于O(N)。
归并排序:通过将一个大数据组分割成一个个小数据组,对小数据组排序,排好序后再整体排序。
时间复杂度为O(NlogN),空间复杂度为O(N),其算法最好、最坏情况下时间复杂度均为O(NlogN),是一种十分高效的排序算法,本质上是一种以空间换时间的算法。
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=(left+right)/2;merge(a, tmp, left, mid);merge(a, tmp, mid + 1, right);_merge(a, tmp, left,mid,mid+1, 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之外的数都有可能会越界,因此需要判断。当begin2>=n的时候,即第二个数不存在,因此不需要归并。当end2>=n的时候,即第二个存在,但大小无法到gap个,此时缩小end2的大小,使得第二组的数据个数为end2-begin2+1个,再与第一组数进行归并。
稳定性:
所谓稳定性,就是指原本相同的数据的相对位置关系,在排序后不发生变化。
常见的排序有冒泡排序、直接插入排序、希尔排序、堆排序、快速排序、归并排序、选择排序。
其中稳定的有冒泡排序、直接插入排序、归并排序
不稳定:
1.希尔排序:原因是在预排序的时候可能同样的数据在不同的组进行排序,导致相对位置变化
2.堆排序:原因是堆排序时要把根节点的元素与最后一个元素互换,导致数据之间的相对位置变化。
3:选择排序:原因是找到最大、最小的元素,将当前最左、最右测的元素与其互换的时候可能会使得位置发生改变。
4:快速排序:每次将最左侧的元素放到最终位置时,可能会导致相对位置改变。