赞
踩
- 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
- 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
有些排序算法无论如何都不能保证它是稳定的,那么它就是不稳定的
但有些排序算法我们加以控制就可以保证他是稳定的,那么它就是稳定的- 内部排序:数据元素全部放在内存中的排序。
- 外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
详细博客链接:插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)//整趟排序的循环
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)//让循环停止的条件有两个,一个是end<0,另一个是a[end] <= tmp
{
if (a[end] > tmp)
{
a[end + 1] = a[end];//往后挪元素
end--;
}
else
{
break;//有序的情况下这里提前break退出循环
}
}
a[end + 1] = tmp;//上面循环停止时在end+1的位置赋值为tmp即可
}
}
时间复杂度(最坏):约为O( n 1.3 n^{1.3} n1.3)
空间复杂度:O(1)
稳定性:稳定
初始数据集的排列顺序对算法的性能有无影响:有影响。
解释:希尔是对插入排序的优化,这种优化是在无序的序列中才有明显的效果,如果序列接近有序,反而是插入最优。
详细博客链接:选择排序
详细博客链接:(C语言)数据结构——冒泡排序和快速排序(超详解)
博客链接:归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{
if (begin == end)
return;
int mid = (end + begin) / 2;
// [begin, mid] [mid+1, end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
// 取小的尾插
// [begin, mid] [mid+1, end]
int begin1 = begin, end1 = mid;
int begin2 = mid+1, end2 = end;
int i = begin;
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, (end-begin+1)*sizeof(int));
}
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;
}
总结:
end
有哪里看不懂可以随时向博主提问
有错误的地方欢迎各位老铁批评指正。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。