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

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;
}