插入和选择排序

1.1直接插入排序

void InsertSort(int* a, int n) {
for (int i = 1; i < n - 1; i++) {//i的范围要注意的，防止指针越界
int end = i;
int tmp = a[end + 1];
while (end>=0) {
if (tmp< a[end]) {
a[end + 1] = a[end];//小于就挪动，虽然会覆盖后面空间的值，但是我们用tmp已经保存下来了
}
else {
break;
}
end--;
}
a[end + 1] = tmp;
}
}

这串代码的运算逻辑就是当我们插入的数据比前项大时就直接插入，如果比前项小，那么前项就往后挪动，直到找到比其小或者end小于0时插入。注意我们往后挪动时会覆盖后项数据，所以我们要创建临时变量来保存该数据。

我们来测试一下：

这里的printarry是打印函数，也就是一个用循环打印数据。我们来计算一下它的时间复杂度：我们知道时间复杂度是计算最坏的情况，在这里的最坏情况为逆序，因为逆序的时候每次插入都需要执行前面数的数量，那么我们假设其有N个数，那么总执行量就为：1+2+3...+N-1  即为(N^2)/2。所以其时间复杂度为O（N^2） 。当数据为顺序有序和接近有序时，时间复杂度就为O(N)。

1.2希尔排序

希尔排序是在插入排序的基础上，效率更高的排序，其实就是在插入排序的基础上加上了与预排序的操作。

//优化，我们在选择gap的时候需要考虑：当gap越大时大的跳到后面越快，小的跳到前面越快，但是越不接近有序
//gap一直等于3吗?
//我们可以进行多次预排序
void ShellSort(int* a, int n) {
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;
//gap /= 2;//这样可以保证最后一此一定gap为1，省去调用插入排序
//最好使用gap=gap/3+1
for (int i = 0; i < n - gap; i++) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (tmp < a[end]) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
}

在这里gap就是分组的间隙，我们这样写不但满足了最后一趟排序gap=1,也进行了gap的调整。

这里gap=gap/3+1，是有些大佬研究发现这样调整效率会更高。

我们来测试一下：

时间复杂度：N^1.3，比N*logN要大一些。

2.1选择排序

void SelectSort(int* a, int n) {
int begin = 0, end = n - 1;
//遍历一遍选出最大和最小的数
int mini = begin, maxi = begin;
while (begin < end) {

for (int i = begin+1 ; i <= end; i++) {
if (a[i] < a[mini]) {
mini = i;
}
if (a[i] > a[maxi]) {
maxi = i;
}
}
Swap(&a[begin], &a[mini]);
if (begin == maxi) {
maxi = mini;//为了应对Max和begin相等的情况
}
Swap(&a[end], &a[maxi]);
begin++;
end--;

}

}

上述代码的思想为每次循环都选出最大和最小，并将其交换至前后。

我们来测试一下：

时间复杂度;O(N^2).

2.2堆排序

void HeapSort(int* a, int size) {
for (int i = (size - 2) / 2; i >= 0; i--) {
AdjustDown(a, size, i);

}
int end = size - 1;
while (end > 0) {
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);//因为调转后我们只需要从根开始调整即可。
--end;//通过调整end的大小，来控制
}
}//时间复杂度为O(N*logN)

这里我们采用向下调整的方式创建堆，然后我们通过首尾交换，然后调整来达到排序的目的，当然·要注意升序的话我们要建大堆，降序建小堆。

时间复杂度：O(N*logN),我们设该树高为h，那么树的所有节点为N=2^h-1个，我们的时间复杂度要换成与数量有关的式子，所以时间复杂度为O(N*logN).

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

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