算法 --排序算法

本文来介绍基础的排序算法
符合这级别的算法分别有选择排序，插入排序，冒泡排序，希尔排序

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

选择排序.gif

template<typename T>
void selectionTestSort(T arr[],int n)
{
    for(int i = 0;i < n; i++)
    {
        int minIndex = i;
        for(int j=i;j<n;j++)
            if(arr[j] < arr[minIndex])
                minIndex = j;

            swap(arr[i],arr[minIndex]);
    }
}

插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

插入排序.gif

template<typename T>
void insertionTestSort(T *arr,int n)
{
    for(int i = 1;i < n;i++)
    {
        int temp = arr[i];
        int j;
        for(j = i; j>0 && arr[j-1] > temp ;j--)
            arr[j] = arr[j-1];

        arr[j] = temp;
    }
}

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。
但希尔排序是非稳定排序算法。
希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

template<typename T>
void Insert(T *arr,int gap,int i)
{
    int inserted =arr[i];
    int j;

    for(j = i-gap ; j>0 && inserted <arr[j];j-=gap)
    {
        arr[j+gap] = arr[j];

    }
        arr[j+gap] = inserted;
}


template<typename T>
void shellTestSort(T arr[],int n)
{
    for(int gap = n/2;gap > 0; gap/=2)
    {
        for(int i = gap;i<n;i++)
        {
            Insert(arr,gap,i);
        }
    }
}