《插入排序的改进（Improved insertion sort）.doc》由会员分享，可在线阅读，更多相关《插入排序的改进（Improved insertion sort）.doc（34页珍藏版）》请在三一文库上搜索。
1、插入排序的改进（Improved insertion sort）Insert sortInsertion sorting is a sequence of data formed by inserting several (typically N-1) wheels.Each rotation inserts new data elements into the existing (incomplete) sequence, so that the original sequence is expanded. The first round contains only a sequence o
2、f data elements before insertion.The operations involved in inserting sorting are primarily to find the insertion location of the new element (check) and to insert the new element into that location. As a result, efforts to reduce time complexity also focus on checking and inserting.1 direct inserti
3、on sort#includeUsing namespace std;Ifstream fin (count4.in);OFSTREAM fout (count.out);(main)int, N, a200001, I, J, t=clock ();Finna1;For (i=2; iai;For (j=i; j1; j-)If (ajaj-1) swap (aj, aj-1);Else / / break;Fout (clock () -t /1000.0endl;For (i=1; i=n; i+)Foutai;Foutendl (clock () -t /1000.0;Just loo
4、k at the swap (aj, aj-1) of a sentence and ignore the comment line, this code is like bubble method, remove the comment line / /, more easily understand the for cycle J is inserted into ai from a1 to ai-1 ordered the original column, but also significantly speed.2, with the lookout to find, use the
5、loop exchange for insertionWe know that switching two subscript variables is more time-consuming, and switching from a large range of consecutive switches to a loop exchange will reduce the amount of data movement. To consider yourself as a surveillance post, you can also limit the scope of the cycl
6、e of judgment and the size of key words as a judgment, which saves some judgment.#includeUsing namespace std;Ifstream fin (count4.in);OFSTREAM fout (count.out);(main)int, N, m, a200001, I, J, K, t=clock ();Finna1;For (i=2; iai;For (j=1; ajj; k-) ak=ak-1;Aj=m;Fout (clock () -t /1000.0endl;For (i=1; i
7、=n; i+)Foutai;Foutendl (clock () -t /1000.0;With these two improvements, the speed may be doubled.3 merge cycles, reduce judgments, and swap loopsExample: NOIP improves combination and fruitTwo, combined fruit (fruit.pas / DPR / C / CPP)problem descriptionIn an orchard, many have already knocked dow
8、n all the fruit, and they are divided into different heaps according to the different kinds of fruit. Many decided to heap all the fruit together.Each time the merger, many can combine two piles of fruit together, and the strength consumed is equal to the sum of the weight of the two piles of fruit.
9、 As you can see, all the fruit has been left in the pile after the n-1 merger. When combined with fruit, the total amount of physical exertion is equal to the sum of the energy consumed by each combination.As much effort has been made to move the fruit home, much effort is needed to conserve energy
10、when combined with fruit. Assume that each fruit weight is 1, and the number of species known to fruit and the number of each type of fruit, your task is to design a combined order of programs, so a lot of physical least cost and physical output of the minimum cost value.For example, there are 3 kin
11、ds of fruit, the number is 1, 2, 9. You can combine the 1 and 2 heaps first, the new heap number is 3, and the energy consumption is 3. Next, the new heap was merged with the original third, and the new heap was 12, consuming 12 of the physical effort. So much labor costs =3+12=15. It can be proved
12、that 15 is the minimum physical exertion value.input fileThe input file fruit.in contains two rows, and the first line is an integer n (1 = n=10000) indicating the number of fruits. The second line contains n integers, separated by spaces. The first I integer AI (1 = ai=20000) is the number of the f
13、irst I species.output fileThe output file fruit.out contains a row that contains only one integer, that is, the minimum physical cost. Enter data to make sure this value is less than 231.sample inputThree129sample outputFifteendata sizeFor 30% of the data, ensure that there is n=1000:For 50% of the
14、data, ensure that there is n=5000;For all data, be sure to have n=10000.This problem with Huffman algorithm, each time to find two piles of least fruit for merger. You can sort first,This is equivalent to deleting two of the fewest fruits and combining them into a new pile of fruit. And then insert
15、the pile of new fruit into a sequence. Repeat this operation until all fruit is in a heap.Reference code#include Using namespace std;Int a10001=2147483647;Void insert (int, x, int, y)While (axn;For (int i=1; iai;Insert (i-1, ai);For (int i=n-1; i0; i-)S+=ai+=ai+1;Insert (i-1, ai);Couts;System (pause
16、);Return 0;4, two way insertionThe above 3 descriptions are descriptions of the magnitude of the squared calculations. As with the two way of sorting, the amount of computation is bound to decrease if we also do two - way processing for the sort of order lookups.Class exercise: programming completes
17、 two - way insertion, ascending sort. I input the amount of data N and M boundary value, the second row is N to be sorted data. For data that is smaller than the demarcation value, the original insertion sort, instead of less than the boundary value, is inserted backward from the an to the a1.The bo
18、undary value here, if you divide the N data exactly, will get the best two - way processing effect, but the distribution is not enough and the average effect will be discounted. Please evaluate the amount of computation that divides the 100 data into the following three patterns:505030701090Can you
19、describe the two - way insertion sort by the most average allocation? Lets take the COUNT competition as an example,NOIP improve group 2007First question: count statisticsEnter a number n (n=200000) and n natural numbers (each number is not more than 1.5*109), please count the number of these natura
20、l numbers appear, in small order output from small to large. Enter data to ensure that the number of different does not exceed 10000.Sample input:EightTwoFourTwoFourFiveOne hundredTwoOne hundredSample output:2342511002The following describes the two way insertion using a bidirectional chain#include
21、#include Using namespace std;Ifstream fin (count.in);OFSTREAM fout (count.out);Struct nodeInt, Data, Count;Node, *previous, *next;Void ins (node, *q, int, x)Node *p=new node;P-Data=x;P-Count=1;P-previous=q;Q-next-previous=p;P-next=q-next;Q-next=p;Return;Int, main ()Int, clockt=clock ();Node, l, m, R
22、, *z, *t;Z=&m;Int, x, N, I, b=0;Finnm.Data;M.Count=1;L.Data=-1;R.Data=1500000001;L.next=r.previous=z;M.previous=&l;M.next=&r;For (i=1; ix;If (x=z-Data)Z-Count+;Else if (xData)t=z;Do t=t-previous;While (xData);If (x=t-Data)T-Count+;ElseIns (T, X);B-;Elset=z;Do t=t-next;While (xt-Data);If (x=t-Data)T-
23、Count+;ElseIns (t-previous, X);B+;If (bprevious;B=0;Else if (b1)Z=z-next;B=0;T=l.next;While (T, =&r)FoutDataCountnext;Cout (clock () -clockt /1000.0;System (pause);Return 0;5. Insert a secondary hash with a chain to resolve COUNTIf the data range in COUNT is changed from the upper limit of 0x1.5*109
24、 to 1.5*107, the self mapped Hashi is a good choice:#includeUsing namespace std;Ifstream fin (count.in);OFSTREAM fout (count.out);int 15000000 ；main() int n，a，I，T = clock()；鳍 n；为（i = 0；i ；+（+）对于（i = 1；i 0）四我” B 我 endl；四（clock() - T）/ 1000；面对大范围的数据，自映射哈希法的地址空间就不够了，压缩地址空间很可能造成地址冲突，采用链地址法就是解决地址冲突的常用方法之
25、一。#包括 n；节点p，* q；对于（i = 0；i p 下一个数据下一页；如果（下）！= 0和p 下一步数据=温度）下面 计数+ +；其他的q =新节点；下一步；p =下一个q；q =数据=温度；q =计数= 1；对于（i = 0；i 150000；i + +）如果（下一步）！= 0）下一步；而（P！= 0）四数据”算 endl；下一页；系统（暂停）；返回0；在4和5中，插入都避免了成片搬，把”插”的代价降低到了极点，但”查”的代价仍然很大。为了降低”查”的代价，可以考虑折半查找。6折半查找的插入排序仍然以计数为例，下面的折半插入描述时间复杂度较低。#包括#包括 1） =（l + R）/ 2
26、；如果（x X；y = se（0，d，x）；如果（a = y）计数+ +；其他的 memcpy（+ y + 2，+ y + 1，T *（D-Y）；+；一个 y + 1 ；a y + 1 。计数= 1；对于（i = 1；i；d；i +）四一个我。数据”一个我数 endl；返回exit_success；能否在线性结构”查”优化到log2（N）同时”插”也优化到O（1）呢？为什么？7在直接交换的插入排序的基础上进行多路和多轮的改进-希尔排序原来（5 2 7 4 1 3 8 6）看成（5）（2）（7）（4）（1）（3）（8）（6）第一轮子序列下标差4:12745386第二轮下标差2:12537486第
27、三轮下标差1：（12345678）用它解决计数的参考代码#包括文件使用名称空间；ifstream CIN（“伯爵。”）；ofstream cout（“伯爵。”）；int 200001 ；国际main()n，m，i，j，t；CIN；mn；为（i = 0；i 0）对于（i = m；i = M & & T为了；J = m）a jm ；对于（m = i = 1；i = n；i + +）如果（一个我 = =一）米+；其他的cout 一 ”我 endl；m1；返回0；The time complexity is O (n*log2 (n). The final round of the whole pro
28、cess is the process of this section 1, instead of switching from direct to circular.Why does it increase the amount of time before a higher time complexity process and reduce the time complexity? What is the relation between the anti - order of large span and the anti - span of small span?The space
29、complexity of this algorithm is N, and it also has high practicability.8 use find two fork tree for insertion sortThe search cost is close to log2 (n) when searching the basic uniform of the two fork tree, and the cost of inserting is O (1). The algorithm can also be used to solve the COUNT problem
30、by inserting sorting, and the following two recursive description reference codes are givenFirst, the insertion function with the return value#includeUsing namespace std;Typedef struct ttInt, data, sum;Struct, TT, *l, *r;node;Node* ins (node, *t, int, x)If (t=NULL)T=new node;T-data=x;T-sum=1;T-l=t-r
31、=NULL;Return t;Else if (t-data) x)T-l=ins (t-l, X);Return t;Else if (t-data) r=ins (t-r, X);Return t;Else(t-sum + +);Return t;Void output (node* T)If (T, =NULL)Output (t-l);Coutdata) (t-sum) r);Int, main ()Int, N, I, x;Cinn;Node *tree;Tree=NULL;For (i=0; ix;Tree=ins (tree, X);Output (tree);System (p
32、ause);Return 0;Then the insertion function with no return value#include#includeUsing namespace std;Ifstream fin (count3.in);Typedef struct ttInt, data, sum;Struct, TT, *l, *r;node;Void ins (node, *t, int, x)If (*t) =NULL)(*t) =new node;(*t) -data=x;(*t) -sum=1;(*t) -l=NULL;(*t) -r=NULL;Else if (*t)
33、-data) x)Ins (& (*t), -l), X);Else if (*t) -data) r), X);Else(*t).Sum + +);Void output (node* T)If (T, =NULL)Output (t-l);Coutdata) (t-sum) r);Int, main ()Int, N, I, x;Finn;Node *tree;Tree=NULL;For (i=0; ix;Ins (&tree, X);Output (tree);System (pause);Return 0;In class practice, the insertion function and the ordered traversal function of the last algorithm are described in a non recursive wayPreviewReview C+ bit processing, and further familiar with the list of commonly used operationsMultiple keyword sortingMerge sortHashing technique of hashing