算导第二章笔记（归并排序之插入排序优化）

这一章大致介绍一些概念

循环不变式

伪代码规范（极度符合Java 规则语法）

theta 符号之类的

主要收获：归并排序 + 插入排序优化

这一点是蛮不错。 n* log（n/k） max（K） = log n

抱着不服的原则（sort至上）去试了试，结果GG：

 1 #include <iostream>
 2 #include <bits/stdc++.h>
 3 #include <time.h>
 4 using namespace std;
 5 
 6 void InsertSort(int* A, int len) {
 7     //int len = A.size();
 8     for(int i = 2; i < len; ++i) {
 9         int j = i-1;
10         int tmp = A[i];
11         while(A[j] > tmp && j >= 0) {
12             A[j+1] = A[j];
13             j--;
14         }
15         A[j+1] = tmp;
16     }
17 }
18 
19 void Merge(int* A, int L1, int R1, int L2, int R2) {
20     int Array1[R1-L1+1];
21     int Array2[R2-L2+1];
22     for(int i = L1; i <= R1; ++i) {
23         Array1[i-L1] = A[i];
24     }
25     for(int i = L2; i <= R2; ++i) {
26         Array2[i-L2] = A[i];
27     }
28     int pos1, pos2;
29     pos1 = pos2 = 0;
30     int cnt = L1;
31     while(pos1 < (R1-L1+1) && pos2 < (R2-L2+1)) {
32         if(Array1[pos1] < Array2[pos2]) A[cnt++] = Array1[pos1++];
33         else A[cnt++] = Array2[pos2++];
34     }
35     while(pos1 < (R1-L1+1)) {
36         A[cnt++] = Array1[pos1++];
37     }
38     while(pos2 < (R2-L2+1)) {
39         A[cnt++] = Array2[pos2++];
40     }
41     //cout << "Cnt: " << cnt <<endl;
42 }
43 
44 void MergeSort(int* A, int L, int R, int K) {
45     if(L < R) {
46         if(R - L >= K) {
47             int p = (L + R) >> 1;
48             MergeSort(A, L, p, K);
49             MergeSort(A, p+1, R, K);
50             Merge(A, L, p, p+1, R);
51         } else {
52             InsertSort(A, R-L+1);
53         }
54 
55     }
56 }
57 
58 
59 void MergeSort2(int* A, int L, int R) {
60     if(L < R) {
61         int p = (L + R) >> 1;
62         MergeSort2(A, L, p);
63         MergeSort2(A, p+1, R);
64         Merge(A, L, p, p+1, R);
65 
66     }
67 }
68 
69 int Array[100000000];
70 int main()
71 {
72     int size = 256 << 21; // 512MB
73     char *p = (char*)malloc(size) + size;
74     __asm__("movl %0, %%esp
" :: "r"(p));
75     //G++ stack
76     int n = 100000000;
77     for(int i = 0; i < n; ++i) {
78         int tmp = int(rand() * n) % 13131;
79         //cout << tmp <<endl;
80         Array[i] = tmp;
81     }
82 
83     clock_t Beg = clock();
84     //MergeSort(Array, 0, n-1, 25); //  28091
85     //MergeSort2(Array, 0, n-1); //     41302
86     sort(Array, Array+n);    //         31347
87     clock_t End = clock();
88     int Dis = End - Beg;
89     cout << "Time : " << Dis << endl;
90    /* for(int i = 0; i < (int)Array.size(); ++i) {
91         cout << Array[i] << " ";
92     }*/
93     puts("");
94 
95 
96 }

算导第二章笔记 （归并排序 之 插入排序优化）

算导第二章笔记（归并排序之插入排序优化）