手机网站管理系统,页面模板 公众号,网站上面的内容里面放照片怎么做的,湖北省建设厅的网站1.插入排序
此排序如打扑克牌一样#xff1b;每次抓牌#xff0c;把扑克从前向后扒拉#xff1b;找到合适的位置插入进去—所以叫插入排序#xff1b;
时间复杂度#xff1a;O#xff08;N^2#xff09; int arr[10] { 9,8,7,6,5,4,3,2,1,0 };//数据太多就不好写了 …1.插入排序
此排序如打扑克牌一样每次抓牌把扑克从前向后扒拉找到合适的位置插入进去—所以叫插入排序
时间复杂度ON^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.希尔排序
时间复杂度ON^1.3
希尔排序是插入排序的优化在完全逆序的情况下就是将最大的数排向最后一个数只不过是从插入排序的一个一个比较向后挪动变成了一个大增量的向后挪动减少了比较的次数
思想此思想属于个人思考用于推演提出算法的人的思想历程不一定对但值得一看 数组arr[10] { 9,8,7,6,5,4,3}; //进行升序排序 间距d5//间距d先取5再取4321 d5时是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; //gapgap-1; //由于增量的控制过大会导致结果完全不同 //数据量越大越无序gap控制的越好的时候希尔排序还是很能打的 //时间复杂度大约在ON的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;}
