《插入排序的改进（Improved insertion sort）》由会员分享，可在线阅读，更多相关《插入排序的改进（Improved insertion sort）（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 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;F
