九种排序算法

一、插入排序
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
（1）算法适用于少量数据的排序，
（2）时间复杂度为O(n^2)。
（3）是稳定的排序方法。
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
————分为直接插入排序法和折半插入（二分插入）
1、直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

void InsertSort(int* array, int size)//插入排序
{
    int i = 1;
    for (; i < size; ++i)
    {
        int key = array[i];
        int end = i - 1;

        //查找待插入元素的位置
        while (end >= 0 && key < array[end])//升序
        {
            array[end + 1] = array[end];
            --end;
        }
        array[end + 1] = key;
    }
}

2、折半插入排序（二分插入排序）

void InsertSort_OP(int* array, int size)//插入排序—利用二分法优化
{
    int i = 1;
    for (; i < size; ++i)
    {
        int key = array[i];
        int begin = 0;
        int end = i - 1;
        int mid = -1;
        //通过二分查找找待插入元素的位置
        while (begin <= end)
        {
            mid = begin + ((end - begin) >> 1);
            if (key >= array[mid])
                begin = mid + 1;
            else
                end = mid - 1;
        }
        //搬移元素
        end = i - 1;
        while (end >= begin)
        {
            array[end + 1] = array[end];
            --end;
        }
        array[begin] = key;
    }
}

二、希尔排序
希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

void ShellSort(int* array, int size)//希尔排序
{
    int i = 1;
    int gap = size;//间隔
    while (gap > 1)
    {
        gap = gap / 3 + 1;
        for (; i < size; ++i)
        {
            int key = array[i];
            int end = i - gap;
            //查找待插入元素的位置
            while (end >= 0 && key < array[end])
            {
                array[end + gap] = array[end];
                end -= gap;
            }
            array[end + gap] = key;
        }
    }
}

三、选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
选择排序是不稳定的排序方法（比如序列[5，5，3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

1、方法一
void SelectSort(int* array, int size)//选择排序
{
    int i = 0;
    int j = 0;
    int maxPos = 0; 
    

今天的文章九种排序算法分享到此就结束了，感谢您的阅读。