首页 > 代码库 > 算法导论-排序-插入排序、归并排序
算法导论-排序-插入排序、归并排序
目录：
1、插入排序算法伪码
2、插入排序c++实现
3、归并排序算法伪码
4、归并排序c++实现
5、总测试程序
内容：
1、插入排序算法伪码
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 }
3、归并排序算法伪码
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 A[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 }
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 else25 {26 A[k]=L[i];27 i++;28 }29 }30 31 delete[] L;32 delete[] R;33 34 }
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 else56 {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
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 }
输出：
1 2 3 4 34 78 465
2 3.2 3.3 3.4 4.34 4.65 7.8
算法导论-排序-插入排序、归并排序