408天勤第八章排序课内代码合集

所谓的课内代码就是指，非课后习题代码，是给出的要背诵的代码，一共有：选择排序、插入排序、冒泡排序、归并排序、堆排序、快速排序。并给出测试样例。

冒泡排序

void BubbleSort(int a[],int n){
    
    int i,j,flag;
    int tmp;
    for(i=n-1;i>=0;i--){
    
        flag = 0;
        for(j = 1;j<=i;j++){
    
            if(a[j-1]>a[j]){
    
                tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
                flag = 1;
            }

        }
        if(flag == 0)
            return ;
    }
}

调用的是

BubbleSort(a,6);//6是指0-5

选择排序

void InsertSort(int a[],int n){
    
    int i,j;
    int tmp;
    for(i=0;i<n;i++){
    
        tmp = a[i];
        j = i-1;
        while(j>=0 && tmp<a[j]){
    
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = tmp;
    }
}

调用的是

InsertSort(a,5);

快速排序

void QuickSort(int a[],int low,int high){
    
    int tmp;
    int i = low,j = high;
    if(low<high){
    
        tmp = a[low];
        while(i<j){
    
            while(j>i && a[j] >= tmp) j--;
            if(i<j){
    
                a[i] = a[j];
                ++i;
            }
            while(i<j && a[i] < tmp) ++i;
            if(i<j){
    
                a[j] = a[i];
                --j;
            }
        }
        a[i] = tmp;
        QuickSort(a,low,i-1);
        QuickSort(a,i+1,high);

    }
}

调用的是

QuickSort(a,0,6);

选择排序

void SelectSort(int a[],int n){
    
    int i,j,k;
    int tmp;
    for(i=0;i<n;i++){
    
        k = i;
        for(j=i+1;j<n;j++)
            if(a[k] > a[j])
                k = j;
        tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;
    }
}

调用的是

SelectSort(a,5);

堆排序

void Sift(int a[],int low,int high){
    
    int i = low,j = 2*i;
    int tmp = a[i];
    while(j<=high){
    
        if(j<high && a[j] < a[j+1])
            ++j;
        if(tmp<a[j]){
    
            a[i] =a[j];
            i = j;
            j = 2*i;
        }else
            break;
    }
    a[i] = tmp;
}
void HeapSort(int a[],int n){
    
    int i;
    int tmp;
    for(i=n/2;i>=1;i--)
        Sift(a,i,n);
    for(i=n;i>=2;--i){
    
        tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;
        Sift(a,1,i-1);
    }
}

调用的是

HeapSort(a,6);

归并排序

void Merge( int A[], int TmpA[], int L, int R, int RightEnd )
{
     /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp;
    int i;

    LeftEnd = R - 1; /* 左边终点位置 */
    Tmp = L;         /* 有序序列的起始位置 */
    NumElements = RightEnd - L + 1;

    while( L <= LeftEnd && R <= RightEnd ) {
    
        if ( A[L] <= A[R] )
            TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
        else
            TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
    }

    while( L <= LeftEnd )
        TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
    while( R <= RightEnd )
        TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */

    for( i = 0; i < NumElements; i++, RightEnd -- )
        A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void MergeSort(int a[],int low,int high){
    
    if(low<high){
    
        if(low<high){
    
            int mid = (low+high)/2;
            MergeSort(a,low,mid);
            MergeSort(a,mid+1,high);
            int b[6];
            Merge(a,b,low,mid,high);
        }
    }
}

调用的是

MergeSort(a,0,6);

完整测试代码

#include<iostream>
using namespace std;
void Print(int a[],int n){
    
    for(int i =0;i<n;i++)
        cout << a[i] << " ";
    cout << endl;
}
void BubbleSort(int a[],int n){
    
    int i,j,flag;
    int tmp;
    for(i=n-1;i>=0;i--){
    
        flag = 0;
        for(j = 1;j<=i;j++){
    
            if(a[j-1]>a[j]){
    
                tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
                flag = 1;
            }

        }
        if(flag == 0)
            return ;
    }
}
void InsertSort(int a[],int n){
    
    int i,j;
    int tmp;
    for(i=0;i<n;i++){
    
        tmp = a[i];
        j = i-1;
        while(j>=0 && tmp<a[j]){
    
            a[j+1] = a[j];
            --j;
        }
        a[j+1] = tmp;
    }
}
void QuickSort(int a[],int low,int high){
    
    int tmp;
    int i = low,j = high;
    if(low<high){
    
        tmp = a[low];
        while(i<j){
    
            while(j>i && a[j] >= tmp) j--;
            if(i<j){
    
                a[i] = a[j];
                ++i;
            }
            while(i<j && a[i] < tmp) ++i;
            if(i<j){
    
                a[j] = a[i];
                --j;
            }
        }
        a[i] = tmp;
        QuickSort(a,low,i-1);
        QuickSort(a,i+1,high);

    }
}
void SelectSort(int a[],int n){
    
    int i,j,k;
    int tmp;
    for(i=0;i<n;i++){
    
        k = i;
        for(j=i+1;j<n;j++)
            if(a[k] > a[j])
                k = j;
        tmp = a[i];
        a[i] = a[k];
        a[k] = tmp;
    }
}
void Sift(int a[],int low,int high){
    
    int i = low,j = 2*i;
    int tmp = a[i];
    while(j<=high){
    
        if(j<high && a[j] < a[j+1])
            ++j;
        if(tmp<a[j]){
    
            a[i] =a[j];
            i = j;
            j = 2*i;
        }else
            break;
    }
    a[i] = tmp;
}
void HeapSort(int a[],int n){
    
    int i;
    int tmp;
    for(i=n/2;i>=1;i--)
        Sift(a,i,n);
    for(i=n;i>=2;--i){
    
        tmp = a[1];
        a[1] = a[i];
        a[i] = tmp;
        Sift(a,1,i-1);
    }
}
void Merge( int A[], int TmpA[], int L, int R, int RightEnd )
{
     /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp;
    int i;

    LeftEnd = R - 1; /* 左边终点位置 */
    Tmp = L;         /* 有序序列的起始位置 */
    NumElements = RightEnd - L + 1;

    while( L <= LeftEnd && R <= RightEnd ) {
    
        if ( A[L] <= A[R] )
            TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
        else
            TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
    }

    while( L <= LeftEnd )
        TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
    while( R <= RightEnd )
        TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */

    for( i = 0; i < NumElements; i++, RightEnd -- )
        A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void MergeSort(int a[],int low,int high){
    
    if(low<high){
    
        if(low<high){
    
            int mid = (low+high)/2;
            MergeSort(a,low,mid);
            MergeSort(a,mid+1,high);
            int b[6];
            Merge(a,b,low,mid,high);
        }
    }
}
int main(){
    
	int a[6] = {
    0,6,9,1,4,3};
    Print(a,6);
    MergeSort(a,0,6);
    Print(a,6);

    return 0;
}