1、冒泡排序

冒泡排序是一种简单的排序方法，算法如下：
1. 首先将所有待排序的数字放入工作列表中。
2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
3. 重复2号步骤(倒数的数字加1。例如：第一次到倒数第二个数字，第二次到倒数第三个数字，依此类推...)，直至再也不能交换。
用C语言实现如下：

int BubbleSort(int *a, int b)    //a是待排序的整型数组，b是待排序数组的元素个数
{
   int i,j,temp;
    for(j=0;j<n-1;j++)
        for(i=0;i<n-1-j;i++)
        {
            if(a[i]>a[i+1])//数组元素大小按升序排列
            {
                temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
            }
        }
｝

最差时间复杂度 O(n²)
最优时间复杂度 O(n)
平均时间复杂度 O(n²)
最差空间复杂度 O(n) total, O(1) auxiliary
.
2、插入排序

插入排序也是一种简单排序方法，算法如下：
1. 从第一个元素开始，认为该元素已经是排好序的。
2. 取下一个元素，在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素，则将该元素往右移动一个位置。
4. 重复步骤3，直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
用C实现如下：

int InsertSort(int *a, int b){
    int i,j;
    int temp;
    for(i = 0; i<</SPAN> b; i++){
         temp = a[i];
         for(j = i-1; j>=0; j--){
            if(a[j] > temp)
                a[j+1] = a[j]; //将元素往右移动
            else{
                a[j+1]=temp;
                break;
            }
        }
    }
｝

最差时间复杂度 O(n²)
最优时间复杂度 O(n)
平均时间复杂度 O(n²)
最差空间复杂度 O(n) total, O(1) auxiliary
.

3、选择排序

选择排序的思想如下：
1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。（具体过程为:先设arr[i]为最小，逐一比较，若遇到比之小的则交换）
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n－1算法结束，否则回到第3步
用C语言实现如下：

int SelectSort(int *a, int b){
    int i,j;
    int flag; //用于记录哪个元素最小
    int temp;
    for(i = 0; i<</SPAN> b; i++){
        flag = i;
        for(j = i+1; j a[j]){
                flag = j;
            } //选出从i开始最小的元素
        }
        temp = a[flag];
        a[flag] = a[i];
        a[i] = temp;  //交换元素
    }
｝

最差时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
最差空间复杂度 О(n) total, O(1) auxiliary

以上三种排序的时间复杂度都是O(n²)。

4、快速排序

（a）一趟排序的过程：

（b）排序的全过程

实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。
快速排序的基本算法是：
1. 从数列中挑出一个元素，称为 "基准"（pivot），
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
用C语言实现如下：

void swap(int *a, int *b)
{
    int t=*a; *a=*b; *b=t;
}
int QuickSort(int *a, int b){
    int i, j;
    int base;
    if(b>1){
        base = a[0]; //设第一个元素为基准
        i = 1; j = b-1;
        while(i<</SPAN>j){
            if(a[i]<</SPAN>base)
                i++;
            else
                swap(&a[i],&a[j--]);//如果i位置的数大于基准，则往后移               
        }
        if(a[i]<</SPAN>base){ //将基准插入到中间
            swap(&a[0], &a[i]);
            QuickSort(a, i+1);
            QuickSort(&a[i+1], b-i-1);
        }
        else{
            swap(&a[0], &a[i+1]);
            QuickSort(a, i);
            QuictSort(&a[i],b-i);
        }
    }
}

快速排序的时间复杂度是O(nlogn)，但是最坏情况下复杂度是O(n²)。
最差时间复杂度 Θ(n²)
最优时间复杂度 Θ(nlogn)
平均时间复杂度 Θ(nlogn) comparisons
最差空间复杂度 根据实现的方式不同而不同

5、希尔排序是不稳定的。

算法思想简单描述：

在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点，
并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为
增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除
多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现
了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中
记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量
对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
一组，排序完成。

下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量，
以后每次减半，直到增量为1。

希尔排序是不稳定的。

输入：数组名称（也就是数组首地址）、数组中元素个数

void shell_sort(int *x, int n)
{
     int h, j, k, t;
    for (h=n/2; h>0; h=h/2) /*控制增量*/
    {
       for (j=h; j<n; j++) /*这个实际上就是上面的直接插入排序*/
       {
           t = *(x+j);
           for (k=j-h; (k>=0 && t<*(x+k)); k-=h)
            {
               *(x+k+h) = *(x+k);
            }
           *(x+k+h) = t;
       }
    }
}

6、堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数

算法思想简单描述：

堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)
时称之为堆。在这里只讨论满足前者条件的堆。

由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以
很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数
实现排序的函数。

堆排序是不稳定的。算法时间复杂度O(nlog2n)。

功能：渗透建堆
输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始

void sift(int *x, int n, int s)
{
    int t, k, j;
    t = *(x+s); /*暂存开始元素*/
    k = s;   /*开始元素下标*/
    j = 2*k + 1; /*右子树元素下标*/
    while (j<n)
    {
       if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/
       {
            j++;
       }
       if (t<*(x+j)) /*调整*/
       {
            *(x+k) = *(x+j);
            k = j; /*调整后，开始元素也随之调整*/
            j = 2*k + 1;
       }
       else /*没有需要调整了，已经是个堆了，退出循环。*/
       {
            break;
       }
    }
    *(x+k) = t; /*开始元素放到它正确位置*/
}

功能：堆排序
输入：数组名称（也就是数组首地址）、数组中元素个数

void heap_sort(int *x, int n)
{
    int i, k, t;
    int *p;
    for (i=n/2-1; i>=0; i--)
    {
       sift(x,n,i); /*初始建堆*/
    }
    for (k=n-1; k>=1; k--)
    {
       t = *(x+0); /*堆顶放到最后*/
       *(x+0) = *(x+k);
       *(x+k) = t;
       sift(x,k,0); /*剩下的数再建堆*/ 
    }
}

几种常见排序算法的介绍及复杂度分析

相关概念

1、稳定排序（stable sort）和非稳定排序

稳定排序是指所有相等的数经过某种排序算法操作后仍然能保持它们在排序之前的相对次序。反之就是非稳定排序。

2、内排序（internal sorting）和外排序（external sorting）

在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。

排序算法

【冒泡排序】（Bubble Sort）

冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。 

冒泡排序是稳定的。算法时间复杂度是O(n2)。 

【选择排序】（Selection Sort）

选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第 i 遍处理是将[i..n]中最小者与位置 i 交换位置。这样，经过 i 遍处理之后，前 i 个记录的位置已经是正确的了。 

选择排序是不稳定的。算法复杂度是O(n2 )。 

【插入排序】（Insertion Sort）

插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i遍处理就结束了；否则交换L与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。

直接插入排序是稳定的。算法时间复杂度是O(n2) 

【堆排序】（Heap Sort）

堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 

堆排序是不稳定的。算法时间复杂度O(nlog2n)。 

【归并排序】（Merge Sort）

归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序是稳定的。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。 

【快速排序】（Quick Sort）

快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。 

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。

各排序方法对比

冒泡排序算法时间复杂度是O(n^2)

选择排序算法时间复杂度是O(n^2)

插入排序算法时间复杂度是O(n^2)

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。

堆排序算法时间复杂度是O(nlogn)

归并排序算法时间复杂度是O(nlogn)

1.基本概念 

1.1稳定排序(stable sort)和非稳定排序 

稳定排序是所有相等的数经过某种排序方法后，仍能保持它们在排序之前的相对次序，。反之，就是非稳定的排序。 

比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5， 

则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。 

1.2内排序( internal sorting )和外排序( external sorting) 
在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的存储顺序，称为内排序；在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的存放顺序排序方法称为外排序。 

1.3算法的时间复杂度和空间复杂度 

所谓算法的时间复杂度，是指执行算法所需要的计算工作量。一个算法的空间复杂度，一般是指执行这个算法所需要的内存空间。 


2.几种常见算法 

2.1冒泡排序 （Bubble Sort） 
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。 

冒泡排序是稳定的。算法时间复杂度是O(n2)。 

2.2选择排序 （Selection Sort） 
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将L[i..n]中最小者与L交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。 

选择排序是不稳定的。算法复杂度是O(n2 )。 

2.3插入排序 （Insertion Sort） 
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L和L[i-1]，如果L[i-1]≤ L，则L[1..i]已排好序，第i遍处理就结束了；否则交换L与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。图1演示了对4个元素进行插入排序的过程，共需要(a),(b),(c)三次插入。 

直接插入排序是稳定的。算法时间复杂度是O(n2) 

2.4堆排序 
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。 

堆排序是不稳定的。算法时间复杂度O(nlog n)。 

2.5归并排序 
设有两个有序（升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。 

归并排序是稳定的。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。 

2.6快速排序 
快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。 

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。

各种排序的稳定性，时间复杂度和空间复杂度总结：

排序算法总结