算法-2.内排序

2. 内排序

2.1 三种代价为 Θ(n2) 排序算法

2.1.1 插入排序

※最佳时间代价 Θ(n)，平均、最差时间代价均为 Θ(n2)

 1 template<class Elem>
 2 
 3 void swap(Elem A[],int a,int b){
 4 
 5     int temp;
 6 
 7     temp=A[a];
 8 
 9     A[a]=A[b];
10 
11     A[b]=temp;
12 
13 }
14 
15  
16 
17 template<class Elem>
18 
19 void insort(Elem A[],int n){
20 
21     for(int i=0;i<n;i++)
22 
23         for(int j=i;(j>0&&A[j]<A[j-1]);j--)
24 
25             swap(A,j,j-1);
26 
27 }

2.1.2 起泡排序

※最佳、平均、最差执行时间均为 Θ(n2)

 1 template<class Elem>
 2 
 3 void bubsort(Elem A[],int n){
 4 
 5     for(int i=0;i<n;i++)
 6 
 7         for(int j=n-1;j>0;j--)
 8 
 9             if(A[j]<A[j-1])
10 
11                 swap(A,j,j-1);
12 
13 }

2.1.3 选择排序

※最佳、平均、最差执行时间均为 Θ(n2)

 1 template<class Elem>
 2 
 3 void selsort(Elem A[],int n){
 4 
 5     for(int i=0;i<n;i++){
 6 
 7         int lowindex=i;
 8 
 9         for(int j=i;j<n;j++)
10 
11             if(A[j]<A[lowindex])
12 
13                 lowindex=j;
14 
15         swap(A,i,lowindex);
16 
17     }
18 
19 }

2.2 Shell排序

※平均时间代价 Θ(n1.5)

 1 template<class Elem>
 2 
 3 void inssort2(Elem A[],int n,int incr){
 4 
 5     for(int i=incr;i<n;i+=incr)
 6 
 7         for(int j=i;(j>=incr&&(A[j]<A[j-incr]));j-=incr)
 8 
 9             swap(A,j,j-incr);
10 
11 }
12 
13  
14 
15 template<class Elem>
16 
17 void shellsort(Elem A[],int n){
18 
19     for(int i=n/2;i>2;i/=2)
20 
21         for(int j=0;j<i;j++)
22 
23             inssort2(&A[j],n-j,i);
24 
25     inssort2(A,n,1);
26 
27 }

2.3 快速排序

※平均、最优时间代价 Θ(nlogn)，最差时间代价 Θ(n2)

template<class Elem>
int findpivot(Elem A[],int i,int j){
    return (i+j)/2;
}

template<class Elem>
int partition(Elem A[],int l,int r,Elem &pivot){
    do{
        while(A[++l]<pivot);
        while((r!=0)&&(A[--r]>pivot));
        swap(A,l,r);
    }while(l<r);
    swap(A,l,r);
    return l;
}

template<class Elem>
void qsort(Elem A[],int i,int j){
    if(j<=i) return;
    int pivotindex=findpivot(A,i,j);
    swap(A,pivotindex,j);
    int k=partition(A,i-1,j,A[j]);
    swap(A,k,j);
    qsort(A,i,k-1);
    qsort(A,k+1,j);
}

2.4 归并排序

※最佳、平均、最差时间代价均为 Θ(nlogn)

 1 template<class Elem>
 2 
 3 void insort(Elem A[],int n){
 4 
 5     for(int i=0;i<n;i++)
 6 
 7         for(int j=i;(j>0&&A[j]<A[j-1]);j--)
 8 
 9             swap(A,j,j-1);
10 
11 }
12 
13  
14 
15 template<class Elem>
16 
17 void mergesort(Elem A[],Elem temp[],int left,int right){
18 
19     if((right-left)<=3){
20 
21         insort<Elem>(&A[left],right-left+1);
22 
23         return ;
24 
25     }
26 
27   
28 
29     int i,j,k,mid=(left+right)/2;
30 
31     if(left==right)
32 
33         return ;
34 
35     mergesort<Elem>(A,temp,left,mid);
36 
37     mergesort<Elem>(A,temp,mid+1,right);
38 
39     for(i=mid;i>=left;i--)
40 
41         temp[i]=A[i];
42 
43     for(j=right;j>=right-mid;j--)
44 
45         temp[j]=A[mid+right-j+1];
46 
47     for(i=left,j=right,k=left;k<=right;k++)
48 
49         if(temp[i]<temp[j])
50 
51             A[k]=temp[i++];
52 
53         else
54 
55             A[k]=temp[j--];          
56 
57 }

2.5 堆排序

※最佳、平均、最差时间代价均为 Θ(nlogn)