1. preface

/****
* This article will try to explain something about:
* --Bubble sort.
* --Quick sort.
* --Merge sort.
* --Heap sort.
* To read this, some prerequisites is necessary:
* --a survive skill in C programming language.
* --a basic skill in CPP.
* --basic knowledge about Time complexity and Space complexity.
* --a generous mind for my fault because this article is free.
*
* Actually, their basic operating principle are easy to understand, but , unfortunately, the precise explication is big problem, at least for me. Here is the contents.
* --Analysis about Bubble sort.
* --Analysis about Quick sort.
* --Analysis about Merge sort.
* --Analysis about Heap sort.
* their source code can be find in fellowing articles. As we all know, for a programmer, the source code is also a good choice.
*/

2. Bubble sort

/****
* Bubble Sort
* This is a really simple algorithm. I learn it when I began to learn C. It just compare two value successively and swap them. The core source code is as fellowing:
*/

2.1 core code

bool BubbleSort::sort(void)
{
    int i,j;
    for( i=0; i<=n; i++)
        for( j=0; j< n -i; j++)
        {
            if( this->array[ j]>this->array[ j+1])
            {
                this->swap( j, j + 1);	//swap two values
            }
        }
}

2.2 Time complexity and Space complexity

/**
* For sort algorithm, it's basic operation is swap two values.So we can compute it's sentence frequency f(n):
* f(n) = n*n = n^2
* (at worst situation)
* and it's time complexity is :
* T(n) = O( f(n)) = O(n^2)
*
*
* obviously, It's space complexity is :
* S(n) = O( g(n)) = O( C) = O(1)
* because it use only constant space whatever n change.
*/

/*
* The totally example source code is here:
*
* (It maybe some fault, I will glad to your advices)
*/

3. Quick sort

/****
* Quick Sort
* This is a famous algorithm. It was developed in 1960 , but never outdated even for now. I was face a problem about sort a million of numbers. Need to say that is a

* nightmare if use bubble sort. Then I learn Quick Sort, it provide a exciting performance. I will explain this below. The principle of quicksort is "divided and process".

* In detail,
* --step1: Pick an element from the array as pivot.
* --step2: Part all elements into two areas: left area and right area.put element that's value less than pivot's value into left area,and put other elements into right area.
* --step3: Recursively do the step above to those sub-array.
*
*
*. First at all, examine it's core source code:
*/

3.1 Core Code

static void quick_sort( int array[], INDEX left, INDEX right)
{
    if( right-left>=2)
    {//core code
        int p;
        p = pivot( array, left, right);		//step1 + step2
        quick_sort( array, left, p-1);		//step3
        quick_sort( array, p+1,  right);
    }
    else if( right -left ==1)
    {//auxiliary
        if( array[left] > array[right])
        {
            swap( array + left, array + right);
        }
    }
}

static int pivot( int array[], INDEX left, INDEX right)
{
    //get povit, one of methods
    INDEX	mInd = (left + right)/2;
    //divide array into two parts
    int	i = 0;
    int	LLen = 0, RLen = 0;
    for( i=left; i<=right; i++ )
    {
        if( i==mInd)
            continue;

        if( array[i]< array[mInd] )
        {
            Arr_back[left + LLen] = array[i];
            LLen++;
        }
        else
        {
            Arr_back[right - RLen] = array[i];
            RLen++;
        }
    }
    Arr_back[left + LLen] =  array[mInd];
    memcpy( array+left, Arr_back + left, (right-left + 1)*sizeof(int));	//use a auxiliary space
    return left + LLen;
}

3.2 Time complexity

/**
* For quicksort, the basic operation is similar to swap above. So we could compute a valid sentence frequency. If there are n elements, in average situation the depth of