数据结构与算法（十一） 排序算法一

int nArray[] = { 8,5,3,2,7 };如下一个数组，现对其进行从小到大排序

选择排序

选择排序：将小的依次放在前面
具象化如下：

void swap(int *nSValue,int *nDValue) 交换函数 
{
    int nTempValue = 0;
    nTempValue = *nSValue;
    *nSValue = *nDValue;
    *nDValue = nTempValue;
}
void selectSort(int *pArr, int nCount) 选择排序 将大的放在后面
{
    for (size_t i = 0; i < nCount - 1; i++) 遍历4次即可
    {
        int nMix = pArr[i]; 设置最小值临时变量 
        for (size_t j = i; j <  j++)  当i=0时，会打印不变，课后思考
        {
            if (pArr[j] < nMix)
            {
                swap(&pArr[j], &nMix);
            }
        }
        if (nMix != pArr[i])
        {
            swap(&pArr[i], &nMix);
        }
    }
}

冒泡排序

冒泡排序 默认第一个元素已排序，其他未排序，将已排序元素从前之后依次比对插入合适位置
具象化如下：

void bubbleSort(int *pArr, int nCount)
{
    for (size_t i = 0; i < nCount -1; i++)
    {
        for (size_t j = 0; j < nCount - 1 - i; j++) 
        {
            if (pArr[j] > pArr[j + 1])
            {
                swap(&pArr[j], &pArr[j + 1]);
            }
        }
    }
}

插入排序

插入排序：默认第一个元素已排序，其他未排序，将已排序元素从前之后依次比对插入合适位置
具象化如下：

void InsertioSort(int *pArr, int nCount) 
{
    for (size_t i = 1; i < nCount; i++)
    {
        int nValue = pArr[i];
        int nIndex = i - 1;
        while (nIndex >=0&&pArr[nIndex] > nValue)
        {
            pArr[nIndex + 1] = pArr[nIndex];
            nIndex--;
        }
        pArr[nIndex + 1] = nValue;
    }
}

希尔排序

void ShellSort(int *pArr, int nCount) 
{
    int nInterval = 1;
    while (nInterval < nCount)
    {
        nInterval = 3 * nInterval + 1;
    }
    while (nInterval > 0)  如下同插入排序
    {
        for (size_t i = nInterval; i < nCount; i++)
        {
            int nValue = pArr[i];
            int nIndex = i - nInterval;
            while (nIndex >= 0 && pArr[nIndex] > nValue)
            {
                pArr[nIndex + nInterval] = pArr[nIndex];
                nIndex = nIndex - nInterval;
            }
            pArr[nIndex + nInterval] = nValue;
        }
        nInterval = nInterval / 3;
    }
}

void print(int *pArr,int nCount) 打印数组
{
    for (size_t i = 0; i < nCount; i++)
    {
        std::cout << pArr[i] << "\t";
    }
    std::cout << std::endl;
}