上车吗？大兄弟
最近几天重新温习一下这些经典的算法，看完之后觉得应该总结（zhuang bi）一下,也许会有需要的童鞋，
如果你喜欢，请给动动你的小手点个关注，喜欢，或者收藏，反正不会怀孕，万一以后有用呢？
废话不多说，直接上干货：
冒泡排序
一. 算法描述
冒泡排序：依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推则将最大的数"滚动"到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。
以下面5个无序的数据为例：
40 8 15 18 12 （文中仅细化了第一趟的比较过程）
第1趟: 8 15 18 12 40
第2趟: 8 15 12 18 40
第3趟: 8 12 15 18 40
第4趟: 8 12 15 18 40
二. 算法分析
平均时间复杂度：O(n2)
空间复杂度：O(1) (用于交换)
稳定性：稳定
三. 算法实现
//交换data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
int temp = *data1;
*data1 = *data2;
*data2 = temp;
}
/********************************************************
*函数名称：BubbleSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 冒泡排序
*********************************************************/
void BubbleSort(int* pDataArray, int iDataNum)
{
for (int i = 0; i < iDataNum - 1; i++) //走iDataNum-1趟
for (int j = 0; j < iDataNum - i - 1; j++)
if (pDataArray[j] > pDataArray[j + 1])
DataSwap(&pDataArray[j], &pDataArray[j + 1]);
}
四. 算法优化
还可以对冒泡排序算法进行简单的优化，用一个标记来记录在一趟的比较过程中是否存在交换，如果不存在交换则整个数组已经有序退出排序过程，反之则继续进行下一趟的比较。
/********************************************************
*函数名称：BubbleSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 冒泡排序
*********************************************************/
void BubbleSort(int* pDataArray, int iDataNum)
{
BOOL flag = FALSE; //记录是否存在交换
for (int i = 0; i < iDataNum - 1; i++) //走iDataNum-1趟
{
flag = FALSE;
for (int j = 0; j < iDataNum - i - 1; j++)
if (pDataArray[j] > pDataArray[j + 1])
{
flag = TRUE;
DataSwap(&pDataArray[j], &pDataArray[j + 1]);
}
if (!flag) //上一趟比较中不存在交换，则退出排序
break;
}
}
选择排序
一. 算法描述
选择排序：比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值与第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。
以下面5个无序的数据为例：
56 12 80 91 20（文中仅细化了第一趟的选择过程）
第1趟：12 56 80 91 20
第2趟：12 20 80 91 56
第3趟：12 20 56 91 80
第4趟：12 20 56 80 91
二. 算法分析
平均时间复杂度：O(n2)
空间复杂度：O(1) (用于交换和记录索引)
稳定性：不稳定 （比如序列【5， 5， 3】第一趟就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）
三. 算法实现
//交换data1和data2所指向的整形
void DataSwap(int* data1, int* data2)
{
int temp = *data1;
*data1 = *data2;
*data2 = temp;
}
/********************************************************
*函数名称：SelectionSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 选择排序
*********************************************************/
void SelectionSort(int* pDataArray, int iDataNum)
{
for (int i = 0; i < iDataNum - 1; i++) //从第一个位置开始
{
int index = i;
for (int j = i + 1; j < iDataNum; j++) //寻找最小的数据索引
if (pDataArray[j] < pDataArray[index])
index = j;
if (index != i) //如果最小数位置变化则交换
DataSwap(&pDataArray[index], &pDataArray[i]);
}
}
插入排序
一. 算法描述
插入排序：插入即表示将一个新的数据插入到一个有序数组中，并继续保持有序。例如有一个长度为N的无序数组，进行N-1次的插入即能完成排序；第一次，数组第1个数认为是有序的数组，将数组第二个元素插入仅有1个有序的数组中；第二次，数组前两个元素组成有序的数组，将数组第三个元素插入由两个元素构成的有序数组中......第N-1次，数组前N-1个元素组成有序的数组，将数组的第N个元素插入由N-1个元素构成的有序数组中，则完成了整个插入排序。
以下面5个无序的数据为例：
65 27 59 64 58 （文中仅细化了第四次插入过程）
第1次插入: 27 65 59 64 58
第2次插入: 27 59 65 64 58
第3次插入: 27 59 64 65 58
第4次插入: 27 58 59 64 65
二. 算法分析
平均时间复杂度：O(n2)
空间复杂度：O(1) (用于记录需要插入的数据)
稳定性：稳定
三. 算法实现
从前向后查找的插入排序：
/********************************************************
*函数名称：InsertSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 插入排序
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int j = 0;
while (j < i && pDataArray[j] <= pDataArray[i]) //寻找插入的位置
j++;
if (j < i) //i位置之前，有比pDataArray[i]大的数，则进行挪动和插入
{
int k = i;
int temp = pDataArray[i];
while (k > j) //挪动位置
{
pDataArray[k] = pDataArray[k-1];
k--;
}
pDataArray[k] = temp; //插入
}
}
}
但我发现从后面查找插入的方式，代码复杂程度较低：
/********************************************************
*函数名称：InsertSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 插入排序
*********************************************************/
void InsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int j = i - 1;
int temp = pDataArray[i]; //记录要插入的数据
while (j >= 0 && pDataArray[j] > temp) //从后向前，找到比其小的数的位置
{
pDataArray[j+1] = pDataArray[j]; //向后挪动
j--;
}
if (j != i - 1) //存在比其小的数
pDataArray[j+1] = temp;
}
}
四. 算法优化
插入排序中，总是先寻找插入位置，然后在实行挪动和插入过程；寻找插入位置采用顺序查找的方式（从前向后或者从后向前），既然需要插入的数组已经是有序的，那么可以采用二分查找方法来寻找插入位置，提高算法效率，但算法的时间复杂度仍为O(n2)。
//查找数值iData在长度为iLen的pDataArray数组中的插入位置
int FindInsertIndex(int *pDataArray, int iLen, int iData)
{
int iBegin = 0;
int iEnd = iLen - 1;
int index = -1; //记录插入位置
while (iBegin <= iEnd)
{
index = (iBegin + iEnd) / 2;
if (pDataArray[index] > iData)
iEnd = index - 1;
else
iBegin = index + 1;
}
if (pDataArray[index] <= iData)
index++;
return index;
}
/********************************************************
*函数名称：BinaryInsertSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 二分查找插入排序
*********************************************************/
void BinaryInsertSort(int* pDataArray, int iDataNum)
{
for (int i = 1; i < iDataNum; i++) //从第2个数据开始插入
{
int index = FindInsertIndex(pDataArray, i, pDataArray[i]); //二分寻找插入的位置
if (i != index) //插入位置不为i，才挪动、插入
{
int j = i;
int temp = pDataArray[i];
while (j > index) //挪动位置
{
pDataArray[j] = pDataArray[j-1];
j--;
}
pDataArray[j] = temp; //插入
}
}
}
快速排序
一. 算法描述
快速排序：快速排序采用分治法进行排序，首先是分割，选取数组中的任意一个元素value（默认选用第一个），将数组划分为两段，前一段小于value，后一段大于value；然后再分别对前半段和后半段进行递归快速排序。其实现细节如下图所示：
二. 算法分析
平均时间复杂度：O(nlog2n)
空间复杂度：O(n)
稳定性：不稳定
三. 算法实现
/********************************************************
*函数名称：Split
*参数说明：pDataArray 无序数组；
* iBegin为pDataArray需要快速排序的起始位置
* iEnd为pDataArray需要快速排序的结束位置
*函数返回：分割后的分割数位置
*说明： 以iBegin处的数值value作为分割数，
使其前半段小于value，后半段大于value
*********************************************************/
int Split(int *pDataArray,int iBegin,int iEnd)
{
int pData = pDataArray[iBegin]; //将iBegin处的值作为划分值
while (iBegin < iEnd) //循环分割数组，使其前半段小于pData，后半段大于pData
{
while (iEnd > iBegin && pDataArray[iEnd] >= pData) //从后向前寻找小于pData的数据位置
iEnd--;
if (iEnd != iBegin)
{
pDataArray[iBegin] = pDataArray[iEnd]; //将小于pData数据存放到数组前方
iBegin++;
while (iBegin < iEnd && pDataArray[iBegin] <= pData)
iBegin++;
if (iBegin != iEnd)
{
pDataArray[iEnd] = pDataArray[iBegin]; //将大于pData数据存放到数组后方
iEnd--;
}
}
}
pDataArray[iEnd] = pData; //此时iBegin=iEnd，此处存储分割数据pData
return iEnd;
}
/********************************************************
*函数名称：QSort
*参数说明：pDataArray 无序数组；
* iBegin为pDataArray需要快速排序的起始位置
* iEnd为pDataArray需要快速排序的结束位置
*说明： 快速排序递归函数
*********************************************************/
void QSort(int* pDataArray, int iBegin, int iEnd)
{
if (iBegin < iEnd)
{
int pos = Split(pDataArray, iBegin, iEnd); //获得分割后的位置
QSort(pDataArray, iBegin, pos - 1); //对分割后的前半段递归快排
QSort(pDataArray, pos + 1, iEnd); //对分割后的后半段递归快排
}
}
/********************************************************
*函数名称：QuickSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 快速排序
*********************************************************/
void QuickSort(int* pDataArray, int iDataNum)
{
QSort(pDataArray, 0, iDataNum - 1);
}
四. 算法优化
快排选用数组第一个元素作为分割元素，如果是一个已经基本有序的数组，那么时间复杂度将会提升到O(n2)；可以从数组中随机选择一个元素作为划分数据，这样即使针对基本有序的数据来说，效率同样达到(nlog2n)，优化后分割函数如下所示：
int Split(int *pDataArray,int iBegin,int iEnd)
{
int rIndex = rand() % (iEnd - iBegin + 1); //随机获得偏移位置
int pData = pDataArray[iBegin + rIndex]; //将iBegin+rIndex处的值作为划分值
while (iBegin < iEnd) //循环分割数组，使其前半段小于pData，后半段大于pData
{
while (iEnd > iBegin && pDataArray[iEnd] >= pData) //从后向前寻找小于pData的数据位置
iEnd--;
if (iEnd != iBegin)
{
pDataArray[iBegin] = pDataArray[iEnd]; //将小于pData数据存放到数组前方
iBegin++;
while (iBegin < iEnd && pDataArray[iBegin] <= pData)
iBegin++;
if (iBegin != iEnd)
{
pDataArray[iEnd] = pDataArray[iBegin]; //将大于pData数据存放到数组后方
iEnd--;
}
}
}
pDataArray[iEnd] = pData; //此时iBegin=iEnd，此处存储分割数据pData
return iEnd;
}
希尔排序
一. 算法描述
希尔排序：将无序数组分割为若干个子序列，子序列不是逐段分割的，而是相隔特定的增量的子序列，对各个子序列进行插入排序；然后再选择一个更小的增量，再将数组分割为多个子序列进行排序......最后选择增量为1，即使用直接插入排序，使最终数组成为有序。
增量的选择：在每趟的排序过程都有一个增量，至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序)；根据增量序列的选取其时间复杂度也会有变化，这个不少论文进行了研究，在此处就不再深究；本文采用首选增量为n/2,以此递推，每次增量为原先的1/2，直到增量为1；
下图详细讲解了一次希尔排序的过程：
二. 算法分析
平均时间复杂度：希尔排序的时间复杂度和其增量序列有关系，这涉及到数学上尚未解决的难题；不过在某些序列中复杂度可以为O(n1.3);
空间复杂度：O(1)
稳定性：不稳定
三. 算法实现
/********************************************************
*函数名称：ShellInsert
*参数说明：pDataArray 无序数组；
* d 增量大小
* iDataNum为无序数据个数
*说明： 希尔按增量d的插入排序
*********************************************************/
void ShellInsert(int* pDataArray, int d, int iDataNum)
{
for (int i = d; i < iDataNum; i += 1) //从第2个数据开始插入
{
int j = i - d;
int temp = pDataArray[i]; //记录要插入的数据
while (j >= 0 && pDataArray[j] > temp) //从后向前，找到比其小的数的位置
{
pDataArray[j+d] = pDataArray[j]; //向后挪动
j -= d;
}
if (j != i - d) //存在比其小的数
pDataArray[j+d] = temp;
}
}
/********************************************************
*函数名称：ShellSort
*参数说明：pDataArray 无序数组；
* iDataNum为无序数据个数
*说明： 希尔排序
*********************************************************/
void ShellSort(int* pDataArray, int iDataNum)
{
int d = iDataNum / 2; //初始增量设为数组长度的一半
while(d >= 1)
{
ShellInsert(pDataArray, d, iDataNum);
d = d / 2; //每次增量变为上次的二分之一
}
}
END
嗨~我是夏尼采，一个有梦想的IT男
每周输出3篇有用的文章，目标是签约简书。
如果文章对您有帮助，希望能点个赞或者关注我。
您的关注和点赞是对我最大的鼓励，感谢您的阅读
网友评论