算法导论-排序(一)-插入排序、归并排序

内容：

1、插入排序算法伪码 T(n) = Θ(n²)

Insertion_sort(A[],n) //数组下标从1开始

for j <- 2 to n

do key <- A[j]

i <- j-1

while i>0 and A[i]>key

A[i+1] <- A[i]

i <- i-1

A[i+1]=key

2、插入排序c++实现

 1 template<typename T>
 2 void insertion_sort(vector<T> &A)
 3 {
 4     int i,j;
 5     T key;
 6     int len=A.size();
 7     for (j=1;j<len;j++)
 8     {
 9         i=j-1;
10         key=A[j];
11         while (i>=0&&A[i]>key)
12         {
13             A[i+1]=A[i];
14             i--;
15         }
16         A[i+1]=key;
17     }
18 }

View Code

3、归并排序算法伪码 T(n) = Θ(nlgn)

1) 归并总代码

Merge_sort(A[],p,r)

if p<r

q=(p+r)/2 // “分”

Merge_sort(A[],p,q) // “治”

Merge_sort(A[],q+1,r) // “治”

Merge(A[],p,q,r) // “合”

2）归并子代码

Merge(A[],p,q,r)

len1 <- q-p+1

len2 <- r-q

for i <- 1 to len1

L[i] <- A[i+p]

for j <- 1 to len2

R[j] <- A[j+q+1]

L[len1+1]=INT_MAX

R[len2+1]=INT_MAX

i <- j <- 1

for k <- p to r

if L[i]>R[J]

A[k]=R[j]

j <- j+1

else

A[k]=L[i]

i <- i+1

4、归并排序c++实现

 1 template<typename T>
 2 void merge_sort(vector<T> &A,int p,int r)
 3 {
 4     if (p<r)
 5     {
 6         int mid=(p+r)/2;
 7         merge_sort(A,p,mid);
 8         merge_sort(A,mid+1,r);
 9         merge(A,p,mid,r);
10     }
11 }

View Code

 1 template<typename T>
 2 void  merge(vector<T> &A,int p,int q,int r)
 3 {
 4     int n1=q-p+1;
 5     int n2=r-q;
 6     T *L=new T[n1+1];
 7     T *R=new T[n2+1];
 8 
 9     for (int i=0;i<n1;i++)
10         L[i]=A[i+p];
11     for (int i=0;i<n2;i++)
12         R[i]=A[i+q+1];
13 
14     L[n1]=R[n2]=INT_MAX;
15 
16     int i=0,j=0;
17     for (int k=p;k<=r;k++)
18     {
19         if (L[i]>R[j])
20         {
21             A[k]=R[j];
22             j++;
23         }
24         else
25         {
26             A[k]=L[i];
27             i++;
28         }
29     }
30 
31     delete[] L;
32     delete[] R;
33 
34 }

View Code

5、总测试程序

Sort.h

 1 #ifndef SORT_HH
 2 #define SORT_HH
 3 template<typename T >
 4 class Sort
 5 {
 6     public:
 7         void insertion_sort(vector<T> &A);
 8         void merge_sort(vector<T> &A,int p,int r);
 9         void print_element(vector<T> A);
10     private:
11         void merge(vector<T> &A,int p,int q,int r);
12 };
13 template<typename T>
14 void Sort<T>::insertion_sort(vector<T> &A)
15 {
16     int i,j;
17     T key;
18     int len=A.size();
19     for (j=1;j<len;j++)
20     {
21         i=j-1;
22         key=A[j];
23         while (i>=0&&A[i]>key)
24         {
25             A[i+1]=A[i];
26             i--;
27         }
28         A[i+1]=key;
29     }
30 }
31 
32 template<typename T>
33 void Sort<T>::merge(vector<T> &A,int p,int q,int r)
34 {
35     int n1=q-p+1;
36     int n2=r-q;
37     T *L=new T[n1+1];
38     T *R=new T[n2+1];
39 
40     for (int i=0;i<n1;i++)
41         L[i]=A[i+p];
42     for (int i=0;i<n2;i++)
43         R[i]=A[i+q+1];
44 
45     L[n1]=R[n2]=INT_MAX;
46 
47     int i=0,j=0;
48     for (int k=p;k<=r;k++)
49     {
50         if (L[i]>R[j])
51         {
52             A[k]=R[j];
53             j++;
54         }
55         else
56         {
57             A[k]=L[i];
58             i++;
59         }
60     }
61 
62     delete[] L;
63     delete[] R;
64 
65 }
66 
67 template<typename T>
68 void Sort<T>::merge_sort(vector<T> &A,int p,int r)
69 {
70     if (p<r)
71     {
72         int mid=(p+r)/2;
73         merge_sort(A,p,mid);
74         merge_sort(A,mid+1,r);
75         merge(A,p,mid,r);
76     }
77 }
78 template<typename T>
79 void Sort<T>::print_element(vector<T> A)
80 {
81     int len=A.size();
82     for (int i=0;i<len;i++)
83     {
84         std::cout<<A[i]<<" ";
85     }
86     std::cout<<std::endl;
87 }
88 #endif

View Code

sot_main.cpp

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 #include "Sort.h"
 5 int main()
 6 {
 7     Sort<int> sort1;
 8     Sort<double> sort2;
 9     
10     int a[]={3,1,4,2,78,34,465};
11     vector<int > vec_a(a,a+7);
12     double b[]={3.3,3.2,4.34,2,7.8,3.4,4.65};
13     vector<double> vec_b(b,b+7);
14     sort1.insertion_sort(vec_a);
15     sort1.print_element(vec_a);
16     sort2.merge_sort(vec_b,0,6);
17     sort2.print_element(vec_b);
18 
19     return 0;
20 }

View Code

输出：

1 2 3 4 34 78 465
2 3.2 3.3 3.4 4.34 4.65 7.8