typedef int ElemType;

void BubbleSort( ElemType A[], int N )
{
    int i, j;
    ElemType Tmp;
    for( i = 0; i < N - 1; i++)
        for( j = 0; j < N - 1 - i; j++)
        {
            if( A[ j ] > A[ j + 1] )
            {
                Tmp = A[ j ];
                A[ j ] = A[ j + 1];
                A[ j + 1] = Tmp;
            }
        }
}

typedef int ElemType;

void InsertionSort( ElemType A[], int N )
{
    int j, P;

    ElemType Tmp;
    for( P = 1; P < N; P++ )
    {
        Tmp = A[ P ];
        for( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- )
            A[ j ] = A[ j - 1 ];
        A[ j ] = Tmp;
    }
}
```  


---

# 希尔排序：(Shell Sort)
希尔排序是插入排序的一种更高效的改进版本，通过比较相距一定距离的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止，所以希尔排序有时也叫缩小增量排序。  

增量是希尔排序的重要部分，只要最终增量为1任何增量序列（*increment sequence*）都可以工作。算法最开始以一定的增量进行排序。然后会继续以一定增量进行排序，最终算法以增量为1进行排序。当增量为1时，算法变为插入排序，这就保证了数据一定会被排序。  

## 算法原理：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量`d2<d1`重复上述的分组和排序，直至所取的增量`dt=1(dt<dt-l<…<d2<d1)`，即所有记录放在同一组中进行直接插入排序为止。  

增量的选择有很多，并且关乎算法的效率。增量序列的一种流行选择是使用Shell建议的序列，`d1 = [ N / 2]`和`d(t) = [ d(t-1)/2 ]`。  

已知的最好步长串行是由Sedgewick提出的 `(1, 5, 19, 41, 109,...)`，该串行的项来自 `9 * 4^i - 9 * 2^i + 1` 和 `4^i - 3 * 2^i + 1` 这两个算式，这项研究也表明“比较在希尔排序中是最主要的操作，而不是交换。”用这样步长串行的希尔排序比插入排序和堆排序都要快，甚至在小数组中比快速排序还快，但是在涉及大量数据时希尔排序还是比快速排序慢。  

## 算法分析：
#### 优劣

希尔排序是基于插入排序的一种算法，在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n²)，而Hibbard增量的希尔排序的时间复杂度为O(n^3/2)，但是现今仍然没有人能找出希尔排序的精确下界。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。但是比O(n²)复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。   

#### 时间性能

1. 增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
- 最后一个增量必须为1；
- 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。  

2． Shell排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n值较小时，n和的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0()差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。  

因此，希尔排序在效率上较直接插入排序有较大的改进。  

## 算法稳定性：
由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。  

## 算法实现：
```C
typedef int ElemType;

void Shellsort( ElemType A[], int N )
{
    int i, j, Increment;
    ElemType Tmp;

    for( Increment = N / 2; Increment > 0; Increment /= 2 )
        for( i = Increment; i < N; i++ )
        {
            Tmp = A[ i ];
            for( j = i; j >= Increment; j -= Increment )
                if( Tmp < A[ j - Increment ] )
                    A[ j ] = A[ j - Increment];
                else
                    break;
            A[ j ] = Tmp;
        }
}

typedef int ElemType;

void Selectsort( ElemType A[], int N )
{
    int i, j, loc;
    ElemType min, Tmp;

    for( i = 0; i < N; i++)
    {
        min = A[ i ];
        for( j = i; j < N; j++)
        {
            if( A[ j ] <= min )
            {
                min = A[ j ];
                loc = j;
            }
        }
        Tmp = A[ i ];
        A[ i ] = A[ loc ];
        A[ loc ] = Tmp;
    }
}

#define LeftChild(i) (2*(i)+1)
typedef int ElemType;

void PercDown( ElemType A[], int i, int N )
{
    int Child;
    ElemType Tmp;

    for( Tmp = A[ i ]; LeftChild( i ) < N; i = Child )
    {
        Child = LeftChild( i );
        if( Child != N - 1 && A[ Child + 1 ] > A[ Child ])
            Child++;
        if( Tmp < A[ Child ])
            A[ i ] = A[ Child ];
        else
            break;
    }
    A[ i ] = Tmp;
}

void Heapsort( ElemType A[], int N )
{
    int i;
    ElemType Tmp;
    for( i = N / 2; i >= 0; i-- )
        PercDown( A, i, N);
    for( i = N - 1; i > 0; i-- )
    {
        Tmp = A[ 0 ];
        A[ 0 ] = A[ i ];
        A[ i ] = Tmp;
        PercDown( A, 0, i );
    }
}