数据结构:插入排序
1.插入排序
此排序如打扑克牌一样;每次抓牌,把扑克从前向后扒拉;找到合适的位置插入进去—所以叫插入排序;
时间复杂度:O(N^2)
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };//数据太多就不好写了
for (int i = 1; i < 10; i++) {
int n = i;
for (; n > 0; n--) {
if (arr[n] < arr[n - 1]) swap(arr[n], arr[n - 1]);
else break;
}
}
for (auto x : arr)
cout << x << endl;
return 0;
2.希尔排序
时间复杂度:O(N^1.3)
希尔排序是插入排序的优化;在完全逆序的情况下,就是将最大的数,排向最后一个数,只不过是从插入排序的一个一个比较,向后挪动;变成了一个大增量的向后挪动;减少了比较的次数;
思想:此思想属于个人思考;用于推演提出算法的人的思想历程;不一定对,但值得一看;
数组:arr[10] = { 9,8,7,6,5,4,3}; //进行升序排序;
间距:d=5;//间距d先取5,再取4,3,2,1;
d=5时,是9与4比较大小,于是乎,就得知了9与4的位置是相对的,4在9的前面;
d进行缩小,再推演:如果3与4进行比较,3在4的前面,那么3也肯定在9的前面;但是3与9不一定会通过间距直接进行比较;而是通过4与9的关系进行了间接比较;
通过不断的缩短间距d,数字之间进行相对位置的比较,从而进行正确的排序;
但是,缺陷所在就是:d的变化过大,会使两个数的相对位置无法确定,造成排序不准确;
缺陷:
由于是控制增量的变化来进行大小比较来排序;以升序为例,数值大的一端总是比数值小的一端更快的排好;若增量的变化的数值若过大,排序的结果,也不会如想象中的结果;
希尔排序是一个非常不稳定的排序——因为他是由增量控制的;
{ int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int n = sizeof(arr)/sizeof(int), gap = n;
while (gap > 1) {
gap = gap / 3 + 1; //gap=gap-1; //由于增量的控制过大,会导致结果完全不同//数据量越大,越无序;gap控制的越好的时候,希尔排序还是很能打的
//时间复杂度:大约在O(N的1.3次方的样子);当n无限大的时候还会减小;
for (int i = 0; i < n - gap; i++) {
if (arr[i] > arr[i + gap]) {
swap(arr[i], arr[i + gap]);
}
}
}
for (auto x : arr) {
cout << x << endl;
}
return 0;}
原文地址:https://blog.csdn.net/qincjun/article/details/142832472
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!