最近在准备秋招的期间遇到了很多排序算法时间复杂度、空间复杂度、稳定性相关的题目，那就做个大致的总结吧。

排序算法
			
时间复杂度（平均）
			
时间复杂度（最坏）
			
时间复杂度（最好）
			
空间复杂度
			
稳定性
		
直接插入排序
			
O(n²）
			
O(n²）
			
O(n)
			
O(1)
			
稳定
		
希尔排序
			
O(nlog2n)
			
O(n²）
			
O(n)
			
O(1)
			
不稳定
		
直接选择排序
			
O(n²）
			
O(n²）
			
O(n²）
			
O(1)
			
不稳定
		
堆排序
			
O(nlog2n)
			
O(nlog2n)
			
O(nlog2n)
			
O(1)
			
不稳定
		
冒泡排序
			
O(n²）
			
O(n²）
			
O(n)
			
O(1)
			
稳定
		
快速排序
			
O(nlog2n)
			
O(n²）
			
O(nlog2n)
			
O(nlog2n)
			
不稳定
		
归并排序
			
O(nlog2n)
			
O(nlog2n)
			
O(nlog2n)
			
O(n)
			
稳定
		
 

文章目录
算法效率度量
时间复杂度
master公式
常用排序算法及其时间复杂度
冒泡排序(bubblesort)：$O(N^{2})$
选择排序：$O(N^{2})$
插入排序：$O(N^{2})$
归并排序：$O(Nlog{N})$
总结

算法效率度量
1.时间复杂度O(n)

原则：

常数1代替所有加法中的常数
只保留最高阶数项(且不要前面的系数)
O(1)<O(log n)<O(n)<O(n logn)<O(n^2)

2.空间复杂度

常用空间换时间
时间复杂度
时间复杂度：算法性能指标（本质常数时间操作的个数）；先看指标再看系数；先看高阶项再看低阶项
常数时间操作：例如位操作、算术运算等。
master公式
$T(N)=aT(N/b)+O(N^{d})$

其中a表示子过程发生次数，b表示子过程样本量，

$log^{a}_{b}&gt;d \rightarrow$复杂度为$O(N^{log^{a}_{b}})$

$log^{a}_{b}=d \rightarrow$复杂度为$O(N^{dlog^{N}})$

$log^{a}_{b}&gt;d \rightarrow$复杂度为$O(N^{d})$
常用排序算法及其时间复杂度
冒泡排序(bubblesort)：$O(N^{2})$
选择排序：$O(N^{2})$
插入排序：$O(N^{2})$
时间复杂度与数据状况有关，最好$O(N)$最差$O(N^{2})$。但算法性能一律按最差考虑，即插入排序时间复杂度为$O(N^{2})$
归并排序：$O(Nlog{N})$
分治思想
总结

    

        
常用排序算法
时间复杂度
 
空间复杂度
稳定性
    
    

        
平均情况
 
最好情况
 
最坏情况
 
辅助存储
    
    

        
交换排序
        
冒泡排序
 
 O(n*n)
 
 O(n)
 
 O(n*n)
 
 O(1)
 
 稳定
    
     

        
快速排序
 O(n*logn)
 
 O(n*logn)
 
 O(n*n)
 
 O(n*logn)
 
 不稳定
    
    

        
插入排序
        
直接插入
 
 O(n*n)
 
 O(n)
 
 O(n*n)
 
 O(1)
 
 稳定
    
     

        
shell排序
 O(n*n)
 
 O(n)
 
 O(n*n)
 
 O(1)
 
 不稳定
    
    

        
选择排序
        
直接选择
 
 O(n*n)
 
 O(n*n)
 
 O(n*n)
 
        
 O(1)
 
 不稳定
    
     

        
堆排序
 O(n*logn)
 
 O(n*logn)
 
 O(n*logn)
         
 O(1)
 
 不稳定
    
         

        
归并排序
 O(n*logn)
 
 O(n*logn)
 
 O(n*logn)
         
 O(n)
 
 稳定
    
   

摘自维基百科： http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95#.E7.A8.B3.E5.AE.9A.E6.80.A7






在计算机科学所使用的排序算法通常被分类为：
计算的时间复杂度（最差、平均、和最好性能），依据列表（list）的大小(n)。一般而言，好的性能是O(n log n)，且坏的性能是O(n2)。对于一个排序理想的性能是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(n logn)。
存储器使用量（以及其他电脑资源的使用）
稳定性：稳定排序算法会让原本有相等键值的纪录维持相对次序。也就是如果一个排序算法是稳定的，当有两个相等键值的纪录R和S，且在原本的列表中R出现在S之前，在排序过的列表中R也将会是在S之前。
依据排序的方法：插入、交换、选择、合并等等。

稳定性

当相等的元素是无法分辨的，比如像是整数，稳定性并不是一个问题。然而，假设以下的数对将要以他们的第一个数字来排序。
(4, 1)  (3, 1)  (3, 7)（5, 6）


在这个状况下，有可能产生两种不同的结果，一个是让相等键值的纪录维持相对的次序，而另外一个则没有：
(3, 1)  (3, 7)  (4, 1)  (5, 6)  （維持次序）
(3, 7)  (3, 1)  (4, 1)  (5, 6)  （次序被改變）


不稳定排序算法可能会在相等的键值中改变纪录的相对次序，但是稳定排序算法从来不会如此。不稳定排序算法可以被特别地实现为稳定。作这件事情的一个方式是人工扩充键值的比较，如此在其他方面相同键值的两个对象间之比较，（比如上面的比较中加入第二个标准：第二个键值的大小）就会被决定使用在原先数据次序中的条目，当作一个同分决赛。然而，要记住这种次序通常牵涉到额外的空间负担。

排序算法列表

在这个表格中，n是要被排序的纪录数量以及k是不同键值的数量。

稳定的排序
冒泡排序（bubble
 sort）— O(n2)
鸡尾酒排序（cocktail
 sort）—O(n2)
插入排序（insertion
 sort）—O(n2)
桶排序（bucket
 sort）—O(n);需要O(k)额外空间
计数排序（counting
 sort）—O(n+k);需要O(n+k)额外空间
归并排序（merge
 sort）—O(n log n);需要O(n)额外空间
原地归并排序—
 O(n2)
二叉排序树排序（binary
 tree sort）— O(n log n)期望时间; O(n2)最坏时间;需要O(n)额外空间
鸽巢排序（pigeonhole
 sort）—O(n+k);需要O(k)额外空间
基数排序（radix
 sort）—O(n·k);需要O(n)额外空间
侏儒排序（gnome
 sort）— O(n2)
图书馆排序（library
 sort）— 时间复杂度通常是O(n log n),需要(1+ε)n额外空间

不稳定的排序
选择排序（selection
 sort）—O(n2)
希尔排序（shell
 sort）—O(n log2 n)如果使用最佳的现在版本
Clover排序算法（Clover
 sort）—O(n)期望时间，O（n^2/2）最坏情况
梳排序—
 O(n log n)
堆排序（heap
 sort）—O(n log n)
平滑排序（smooth
 sort）— O(n log n)
快速排序（quick
 sort）—O(n log n)期望时间, O(n2)最坏情况;对于大的、乱数列表一般相信是最快的已知排序
内省排序（introsort）—O(n log n)
耐心排序（patience
 sort）—O(n log n + k)最坏情况时间，需要额外的O(n + k)空间，也需要找到最长的递增子序列（longest
 increasing subsequence）

不实用的排序
Bogo排序—
 O(n × n!)，最坏的情况下期望时间为无穷。
Stupid排序—O(n3);递归版本需要O(n2)额外存储器
珠排序（bead
 sort）— O(n) or O(√n),但需要特别的硬件
煎饼排序—O(n),但需要特别的硬件
臭皮匠排序（stooge
 sort）算法简单，但需要约n^2.7的时间

平均时间复杂度

平均时间复杂度由高到低为：
冒泡排序O(n2)
选择排序O(n2)
插入排序O(n2)
希尔排序O(n1.25)
堆排序O(n log n)
归并排序O(n log n)
快速排序O(n log n)
基数排序O(n)

说明：虽然完全逆序的情况下，快速排序会降到选择排序的速度，不过从概率角度来说（参考信息学理论，和概率学），不对算法做编程上优化时，快速排序的平均速度比堆排序要快一些。




名称

数据对象

稳定性

时间复杂度

空间复杂度

描述

平均

最坏
冒泡排序
数组



（无序区，有序区）。从无序区通过交换找出最大元素放到有序区前端。
选择排序
数组




（有序区，无序区）。在无序区里找一个最小的元素跟在有序区的后面。对数组：比较得多，换得少。
链表

插入排序
数组、链表



（有序区，无序区）。把无序区的第一个元素插入到有序区的合适的位置。对数组：比较得少，换得多。
堆排序
数组



（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。
归并排序
数组



，如果不是从下到上
把数据分为两段，从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
链表

快速排序
数组




（小数，枢纽元，大数）。
希尔排序
数组




每一轮按照事先决定的间隔进行插入排序，间隔会依次缩小，最后一次一定要是1。
 
 
计数排序
数组、链表



统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。
桶排序
数组、链表



将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
基数排序
数组、链表



 
一种多关键字的排序算法，可用桶排序实现。

均按从小到大排列
k代表数值中的"数位"个数
n代表数据规模
m代表数据的最大值减最小值

 
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

*    recurrence is log2(n).Just as below:

*

*    step1: [1.........................................................n]    // n

*    step2: [1......................m1] [m1.......................n]    // n/2 + n/2

*    step3: [1.....m2] [m2.....m1]  [m1....m3]  [m3......n]    // n/4 + n/4 + n/4 + n/4

*    .......

*    stepX: [1,2][3,4]................................................

*

*    and funny is that: for step N, if we want to part those arrays into sub-array, we need the number of basic operation is :

*        N*(n/N)

*    that's means: 

*        f(n) = n*log2(n)

*    and

*        T(n) = O( f(n)) = O( n*log2(n) )

*

*/

    3.3 Space complexity
/**

*    At least two points are deserve to consider. 

*        Point.1 : Normally, we need more auxiliary space when n increase.

*        Point.2 : the recursion of function may be need more space.

*

*    In my situation, the auxiliary space of Point.1 is n. For Point.2, Assume that the cost is A for ecah function call, the totally number of call is


*        2^0 + 2^1 + 2^2 + .....2^log2(n)

*

*    then, the cost of point.2 is

*

*              A*[1 + 2^1 + 2^2 + ....2^log2(n) ]

*            =A*[1 + 2^1 + 2^2 + ....+ n]

*            =A*[2*n-1] < A*2*n

*

*    combine two parts:

*            S(n) = O( B*n) = O(n)

*/

/*

*    References

*        wikipedia-Quicksort <http://en.wikipedia.org/wiki/Quicksort>

*/

4. Merge sort
/****

*    Merge Sort

*    The common view is that: compare with famous Quicksort and Heapsort, it is slightly worse in sort a array.  but it provide a excellent performance in sort a link list,

*    which is difficult to Quicksort and Heapsort. on the other side, Mergesort is a stable sort, unlike standard in-place quicksort and heapsort. It's core principle is "divide

*    and conquer".

*

*    conceptually, Mergesort work as fellow:

*        step1: divide the array into n sublists.That means every sublist is only contain of 1 element.

*        step2: repeatedly merge all sublists to create new sorted sublist untill there is only 1 sublist remaining.

*

*    just like this:

*    step1:    [0] [1] [2] [3] [4] [5] [6] [7]

*    step2:    [0...1] [2...3]  [4...5] [6...7]

*    step3:    [0............3]  [4..............7]

*    step4:  [0..................................7]

*

*    If you need more information, there will be a good place.

*        http://en.wikipedia.org/wiki/Merge_sort

* 

*    then , examine the core source code:

*/
    4.1 core code
bool MergeSort::sort(void)
{
    ......
    int width = 1;
    while( width < (this->right - this->left + 1) )
    {
        this->subsort( width);	//sort sublists
        width *= 2;
    }
    .....
}

bool MergeSort::subsort( int width)
{
    .....
    INDEX	cur = this->left;
    while( cur + width <= this->right)
    {
        //sort two sublists into a new sorted list.
        this->sort2Arr( cur, width, cur + width, MIN( width, this->right-cur-width+1));
        cur += 2*width;
    }
    memcpy( this->array,  this->array_back, (this->right - this->left + 1)*sizeof(int));
    .....
}

 
    4.2 Time complexity
/**

*    Time complexity

*

*    Now, let me see a interesting thing before check it's Time frequency. Image this, there are two  arrays ,both of them are progressive increase. they are contain of n and

*    m elements respectively.

*

*    [1.............n] [1..........m]

*

*    How many times is necessary to merge them into a new sorted array?

* 

*       --  at least:  MIN( n,m);

*            at most:  m+n;

*

*            For example:

*                [ 1, 2, 3] [4,5,6,7]

*            and 

*                [1,2,3,7] [4,5,6]

*

*

*    Based on the conclusions above, we could know that : at worst situation, if we want to sort n elements by the way of Mergesort,  the times of compare operation is n.

*

*    So, Time frequency is n*log2(n)

*    and

*        T(n) = O( f(n)) = O( n*log2(n) )

* 

*/
 
    4.3 Space complexity
/**

*    Space complexity

*        In my example, a additional array was used to auxiliary operation.

*        obviously, the space complexity is :

*                S(n) = O(n);

*

*        but that is at worst situation. It could be optimized.

*

*/

5. Heap sort
/****

* Heap Sort

*  This is another famous sort algorithm. Need to say: it's very cool. Although sometimes it is slower in practice on most machine than  well-implemented quicksort, it's

*have the advantage of a more favorable worst-case O( n*log(n)) runtime. unfortunately, it is not a stable sort.

*/
/*

* Before explain heapsort, some questions are necessary to know:

* 1). How can we store a binary tree into a array ?

*

*  --if we number all nodes of a tree , based on 1, you will find a rule. To a node n, it must have the fellowing relationship:

*   parent    : floor(n/2)

*   left chil   : 2*n

*   right chil : 2*n + 1

*

*   This feature gives us a chance to save a tree into a array.

*

* 2). What is max heapify ?

*  --For a binary tree, if all of parent nodes greater than or equal to those corresponding child nodes, the root node must be the largest node in this tree. In other words,

*   we can get  the largest one between some nodes by arrange those number into a max binary tree. By the way, if binary tree can do that, then heap can, too.

*/


/*

* The Heapsort algorithm can be divided into two parts.

*  step 1: build a max binary tree.

*

*  step 2: remove the largest node( the root of the tree) ,and then update the tree repeatedly untill all of nodes has been get out.

*

*/

 
    5.1 core code
bool HeapSort::sort(void)
{	
/*
*	As we all know, some of nodes haven't child node.
*	For skip those nodes, we need to find the last parent node.
*	
*	but How can we do that?
*
*	--the answer is the last child node.
*/
	INDEX	nInd = 0;
	nInd = this->fun.GetParentInd( this->right );
	
/*
*	Adjust nodes from bottom to top.Function MaxHeapify() 
*	will arrange a node and its's sublayer nodes to 
*	a max binary tree. 
*/
	while( nInd>=0)
	{
		// @(this->right) is the number of nodes.
		this->MaxHeapify( nInd, this->right);
		nInd--;
	}

/*
*	moving the largest one between all of nodes into a array,
*	and tidy the remaining. Repeat this process untill 
*	we get all of nodes.
*/
	nInd = this->right;
	while( nInd>0 )
	{
		this->Swap( 0, nInd);		
		nInd --;
		this->MaxHeapify( 0, nInd);
	}

	return true;
}

bool HeapSort::MaxHeapify( INDEX nInd, INDEX right)
{
	INDEX	max = this->GetBigNodeInd( nInd, right);

	while( max!=nInd)
	{
		this->Swap( max, nInd);
		nInd = max;
		max = this->GetBigNodeInd( nInd, right);
	}
	
	return true;
}

/*

* About @MaxHeapify(), there are many problems need to solve. This article is worth to reading:

*  http://shmilyaw-hotmail-com.iteye.com/blog/1775868

* 

*/

    5.2 Time complexity
/**

*    sorry, I have no idea.

*/

    5.3 Space complexity
/**

* space complexity 

*

* It is simple to compute the space complexity.

*  S(n) = O(1);

* because it use a constant space.

*/
/*

* The totally example source code is here:

*

* (It maybe some fault, I will glad to your advices)

*/


/**

* References:

*

*  heap sort分析和总结 <http://shmilyaw-hotmail-com.iteye.com/blog/1775868>

*  heapsort   <http://en.wikipedia.org/wiki/Heapsort>

*

*/