交换和归并排序

1.1冒泡排序

void BubbleSort(int* a, int n) {
for (int i = 0; i < n; i++) {
int mark = 0;
for (int j = 0; j < n-1-i; j++) {
if (a[j] > a[j + 1]) {
Swap(&a[j], &a[j + 1]);
mark = 1;
}
}
if (mark == 0) {
break;
}
}
}

冒泡排序是一种简单的排序算法，其基本思想是通过比较相邻的元素并交换位置，使较大的元素逐渐“浮”到数组的末尾，而较小的元素则逐渐“沉”到数组的开始。具体步骤如下：

1. 从数组的第一个元素开始，依次比较相邻的两个元素。如果前一个元素大于后一个元素，就将它们交换位置。
2. 继续向后依次比较相邻的元素，重复上述操作，直到到达数组的倒数第二个元素。
3. 重复执行上述操作，每次比较会将当前未排序部分的最大元素移动到末尾。
4. 重复2和3的步骤，直到整个数组有序。

冒泡排序的时间复杂度为O(n^2)，其中n为数组的长度。尽管冒泡排序的时间复杂度较高，但它是一种稳定的排序算法，适用于小规模数据的排序操作。

我们来测试一下：

1.2快速排序

void QuickSort1(int* a, int left, int right) {
 //前后指针，cur，prev先走 cur碰到比keyi大的数据就++，小的数就停下，prev++,然后交换，最后keyi与prev交换
if (left>=right) {
return;
}
//小区间优化，数据较小时采用插入排序可减少90%的递归消耗
if (right - left+1 <= 10) {//这里的加一是因为right为数组的下标，例如有10个数 right为9 left为0 
InsertSort(a + left, right - left + 1);//这里的a+left为插入的初始位置，每次的初始位置肯可能不同
}
else {


int keyi = left;
int prev = left; int cur = left + 1;
while (cur <= right) {
if (a[cur] <= a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
++cur;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
QuickSort1(a, left, keyi - 1);
QuickSort1(a, keyi + 1, right);
}
}

在快速排序中我们的key的选择，堆整个排序的效率起着很大的作用，我们只要让其几乎每次都不是最小或者最大即可。

在这里就出现了随机数取key和三数取中的方法。

随机数选key:

// 100 200 注意这里的left不一定为0
//选[left right]区间的随机数与第一个数据交换做key.
srand(time(0));
int randi = rand() % (right - left+1 );//这里的加一是为了刚好达到该区间，例如rand()%100的区间为0~99 .
randi += left;//randi+left后才会达到该区间
Swap(&a[left],&a[randi]);

三数取中：

//拿到三数数值中间的数，这样就可以避免选key的时候，选到最小或最大值
int GetMidi(int* a, int left, int right) {
int midi = (right - left) / 2;
if (a[left] > a[right]) {
if (a[right] < a[midi]) {
return midi;
}
else if (a[left] < a[midi]) {
return left;
}
else
return right;
}
//a[left] < a[right]
else
{
if (a[right] < a[midi]) {
return right;
}
else if (a[left] > a[midi]) {
return left;
}
else
return midi;
}
}

快速排序基于分治的思想，通过将序列分割成较小的子序列来解决问题。在每一趟排序中，通过在序列中移动元素，将基准元素放置到最终排序位置的同时，也将序列划分为两个子序列。递归地应用快速排序可以使得整个序列有序。

快速排序的时间复杂度为O(nlogn)（最坏情况下为O(n^2)），其中n为序列的长度。快速排序是一种不稳定的排序算法。

2.1归并排序

//归并排序：将数组不断分成一个数据后开始递归回去合并
//时间复杂度：O(N*logN)
void _MergeSort(int* a, int begin, int end, int *tmp) {
if (begin == end) {
return;
}
int mid = begin+(end - begin) / 2;
//[begin ,mid ] [mid+1, end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid + 1, end, tmp);
//归并
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin; 
//依次比较，取小的尾插tmp数组
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 (begin2 <= end2) {
tmp[i++] = a[begin2++];
}
memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n) {
int *tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL) {
perror("malloc fail");
return;
}
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
 }

归并排序（Merge Sort）是一种基于分治法的排序算法，它的基本思想是将待排序序列分成若干个子序列，分别进行排序，然后再将已排序的子序列合并成一个有序的序列，从而达到整个序列有序的目的。

具体步骤如下：

1. 将待排序序列不断二分，直到每个子序列只有一个元素为止。
2. 对每个子序列进行排序，可以通过递归地调用归并排序来实现。
3. 将排好序的子序列进行合并，形成一个有序的序列。

在归并排序中，合并操作是关键步骤。合并操作需要额外的空间来存储已排序的子序列，因此归并排序需要辅助的空间来存储合并结果。

归并排序的时间复杂度为O(nlogn)，其中n为序列的长度。归并排序是一种稳定的排序算法，因为在合并操作中，相等的元素在合并的过程中不会改变它们的相对位置。

归并排序是一种经典的排序算法，它不仅时间复杂度较低，而且稳定性好，适合各种规模的数据排序。

原文地址：https://blog.csdn.net/c23856/article/details/140577947

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！