基于模板类的排序算法(希尔排序,归并排序)

2016-12-01

版权声明:本文为作者原创文章,可以随意转载,但必须在明确位置表明出处!!!

希尔排序

  • 算法的基本思想:

    希尔排序是直接插入排序算法的一种更高效的改进版本,希尔排序采用增量缩小的方式来排序,每次分组按增量值来分组,然后对分完组的数列进行排序,知道增量逐渐减少为1是,待排序列排序结束。

  • 算法原理:

  1. 确定一个增量为数组长度的一半nLoop
  2. 按照增量nLoop进行分组
  3. 对分组后的数据进行排序
  4. 缩小增量为nLoop的一半
  5. 重复上述步骤知道nLoop为1排序结束。
  • 时间复杂度:

    最坏时间复杂度为O(n^2),最好时间复杂度为O(n),平均复杂度为O(n^1.3)

  • 稳定性:

    希尔排序是不稳定排序

算法实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template<class T>
void Algorithm<T>::shellSort(T *array, int nLength, int (*fCompare)(const T*, const T*))
{
if(0 == *array || nLength <= 0) return;
for(int nLoop = nLength / 2; nLoop >= 1; nLoop /= 2)
{
//对增量为nLoop的数据元素进行排序
for(int index = nLoop; index < nLength; index ++)
{
for(int nSwapIndex = index - nLoop; nSwapIndex >= 0; nSwapIndex -= nLoop)
{
if(fCompare(&array[nSwapIndex], &array[index]) > 0)
{
T temp = array[nSwapIndex];
array[nSwapIndex] = array[index];
array[index] = temp;
}
}
}
}
}

归并排序

  • 算法的基本思想:

    归并算法的核心思想就是先分解在合并,先对分解后的元素进行排序,然后再合并成一个有序序列。
  • 算法原理:

  1. 申请一个辅助空间,这个空间于原数组大小一致,该控件用来存放合并后的序列。
  2. 设定两个辅助索引,分别指向待合并序列的起始位置。
  3. 比较两个索引位置的值,选择相对小的元素放到辅助空间中。并将该索引下标向后移动。
  4. 重复步骤3知道某一指针超出该要合并队列的队尾。
  5. 将另序列所有的元素直接复制到队尾。
  • 时间复杂度:

    最坏时间复杂度为O(nlog2n),最好时间复杂度为O(nlog2n),平均复杂度为O(nlog2n)

  • 稳定性:

    归并排序是稳定排序

  • 算法实现:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    template<class T>
    void Algorithm<T>::mergeSort(T *array, T *tempArray, int nFirst, int nLast, int (*fCompare)(const T*, const T*))
    {
    if(0 == *array || (nFirst - nLast) > 0 || nFirst < 0 || nLast < 0 ) return;
    int nMidIndex = 0;
    if(nFirst < nLast)
    {
    nMidIndex = (nFirst + nLast) / 2;
    mergeSort(array, tempArray, nFirst, nMidIndex, fCompare);//对分解后的左边序列进行排序
    mergeSort(array, tempArray, nMidIndex + 1, nLast, fCompare);//对分解后的右边序列进行排序
    merge(array, tempArray, nFirst, nMidIndex, nLast, fCompare);//合并序列
    }
    }
    template<class T>
    void Algorithm<T>::merge(T *array, T *tempArray, int nFirst, int nMid, int nLast, int (*fCompare)(const T*, const T*))
    {
    int nStartIndex = nFirst;
    int nMidIndex = nMid + 1;
    int index = nFirst;
    while(nStartIndex != nMid + 1 && nMidIndex != nLast + 1)
    {
    if(fCompare(&array[nStartIndex], &array[nMidIndex]) > 0)
    {
    tempArray[index ++] = array[nMidIndex ++];
    }
    else
    {
    tempArray[index ++] = array[nStartIndex ++];
    }
    }
    while(nStartIndex != nMid + 1)
    {
    tempArray[index ++] = array[nStartIndex ++];
    }
    while(nMidIndex != nLast + 1)
    {
    tempArray[index ++] = array[nMidIndex ++];
    }
    for(nStartIndex = nFirst; nStartIndex <= nLast; nStartIndex ++)
    {
    array[nStartIndex] = tempArray[nStartIndex];
    }
    }

项目文件地址:https://github.com/Gavinxyj/Algorithm


推荐我的微信公众号:爱做饭的老谢


上一篇:基于模板类的排序算法(快速排序,插入排序)
下一篇:FTP网络协议C++实现