排序

1.概念：升序 降序
2.排序算法的稳定性
3.不需要比较的排序：位图 哈希(直接定址法--找出字符串中第一个只出现一次的字符)
4.内部排序：数据可以一次性加载到内存中
外部排序：数据不能一次性加载到内存中

必须掌握：排序原理 代码 时间复杂度 空间复杂度 稳定性 应用场景

常见排序算法

插入排序: 数据量小 尽可能有序 稳定 时间复杂度0(n^2) 空间复杂度0(1)

插入排序.png

//插入排序：数据量小 尽可能有序 稳定 时间复杂度0(n^2) 空间复杂度0(1)
void InsertSort(int array[], int size)
{
    //默认已有一个数据
    for (int i = 1; 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;
    }
}

void TestInsertSort()
{
    int array[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
    InsertSort(array, sizeof(array) / sizeof(array[0]));
}

插入排序调试1.png
插入排序2.png

希尔排序:
时间0(n^1.25)or0(n1.65) 空间0(1) 不稳定：间隔元素排序，不稳定 应用场景：数据量大且杂乱。

希尔排序.png

void ShellSort(int array[], int size)
{
    int gap = 3;
    while (gap > 0)
    {
        for (int i = gap; 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;
        }
        gap--;
    }
    
}

void TestShellSort()
{

    int array[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
    InsertSort(array, sizeof(array) / sizeof(array[0]));
}

希尔排序调试1.png
希尔排序调试2.png