408 day attendance Chapter 8 sorting in class code collection

The so-called in class code refers to , Non after class exercise code , Is the given code to recite , Altogether ： Selection sort 、 Insertion sort 、 Bubble sort 、 Merge sort 、 Heap sort 、 Quick sort . And give a test example .

Bubble sort

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 ;
    }
}

It's called

BubbleSort(a,6);//6 Refer to 0-5

Selection sort

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;
    }
}

It's called

InsertSort(a,5);

Quick sort

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);

    }
}

It's called

QuickSort(a,0,6);

Selection sort

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;
    }
}

It's called

SelectSort(a,5);

Heap sort

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);
    }
}

It's called

HeapSort(a,6);

Merge sort

void Merge( int A[], int TmpA[], int L, int R, int RightEnd )
{
     /*  Will be orderly A[L]~A[R-1] and A[R]~A[RightEnd] To merge into an ordered sequence  */
    int LeftEnd, NumElements, Tmp;
    int i;

    LeftEnd = R - 1; /*  Left end position  */
    Tmp = L;         /*  Starting position of ordered sequence  */
    NumElements = RightEnd - L + 1;

    while( L <= LeftEnd && R <= RightEnd ) {
    
        if ( A[L] <= A[R] )
            TmpA[Tmp++] = A[L++]; /*  Copy left element to TmpA */
        else
            TmpA[Tmp++] = A[R++]; /*  Copy right element to TmpA */
    }

    while( L <= LeftEnd )
        TmpA[Tmp++] = A[L++]; /*  Copy the rest on the left  */
    while( R <= RightEnd )
        TmpA[Tmp++] = A[R++]; /*  Copy directly the rest on the right  */

    for( i = 0; i < NumElements; i++, RightEnd -- )
        A[RightEnd] = TmpA[RightEnd]; /*  Will be orderly TmpA[] Copy back 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);
        }
    }
}

It's called

MergeSort(a,0,6);

Complete test code

#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 )
{
     /*  Will be orderly A[L]~A[R-1] and A[R]~A[RightEnd] To merge into an ordered sequence  */
    int LeftEnd, NumElements, Tmp;
    int i;

    LeftEnd = R - 1; /*  Left end position  */
    Tmp = L;         /*  Starting position of ordered sequence  */
    NumElements = RightEnd - L + 1;

    while( L <= LeftEnd && R <= RightEnd ) {
    
        if ( A[L] <= A[R] )
            TmpA[Tmp++] = A[L++]; /*  Copy left element to TmpA */
        else
            TmpA[Tmp++] = A[R++]; /*  Copy right element to TmpA */
    }

    while( L <= LeftEnd )
        TmpA[Tmp++] = A[L++]; /*  Copy the rest on the left  */
    while( R <= RightEnd )
        TmpA[Tmp++] = A[R++]; /*  Copy directly the rest on the right  */

    for( i = 0; i < NumElements; i++, RightEnd -- )
        A[RightEnd] = TmpA[RightEnd]; /*  Will be orderly TmpA[] Copy back 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;
}