2018 3 17
今日总结一下C++中的排序算法：
1冒泡排序
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。（来源百度百科）
C++实现：
#include "stdafx.h"
#include <iostream>
using namespace std;
int ha[] = {,,,,,,,}; template <typename T>
void Bubble_Sort(T *pDst,const int nLen)
{
int cycle;
//外层循环，控制遍历的次数（N-1(N为待排序的数组大小)）
for (cycle=; cycle<(nLen-) ; cycle++)
{
//内层循环，每次遍历到前一次最大值之前为止
for (int i=; i < (nLen - -cycle); i++)
{
if (pDst[i] > pDst[i + ])
{
T tTemp = pDst[i];
pDst[i] = pDst[i + ];
pDst[i + ] = tTemp;
}
}
}
} int main()
{
//冒泡 Bubble_Sort<int>(ha,);
for (int i = ; i < ; i++)
{
printf("%d-",ha[i]);
getchar();
}
36 return ;
}
2 选择排序
工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。
C++实现：
//升序
template <typename T>
void Select_Sort(T *pDst, const int nLen)
{
T tTemp; //遍历nLen次，每次找到最小的值，交换
for (int i = ; i < nLen; i++)
{
for (int j = i; j < nLen; j++)
{
if (pDst[j] <pDst[i])
{
tTemp=pDst[i];
pDst[i] = pDst[j];
pDst[j] = tTemp; }
else
continue;
}
} }
int main()
{
//冒泡 //Bubble_Sort<int>(ha,8);
Select_Sort<int>(ha,);
for (int i = ; i < ; i++)
{
printf("%d-",ha[i]);
}
return ;
}
3 归并排序
将两个有序（同一种序）的数组合并为一个有序数组
（1）二路归并。二路归并的最好情况时间复杂度为：O(Min{sizof(a),sizeof(b)})
// ConsoleApplication4.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
#include "atlstr.h"
#include <iostream>
#include <vector>
using namespace std;
//////
//二路归并排序。将两个表，合并成一个表的过程称为二路归并
//如：对两个y有序的数组 进行二路归并
const int a[] = {,,};
const int b[] = {,,,,,,}; int* Merger_Sort(const int *a,const int *b,int nLen1,int nLen2)
{
int *pDst = new int[nLen1+nLen2];
int k = ;
int i = ;
int j = ;
while (i < nLen1&&j < nLen2)
{
if (a[i] <= b[j])
{
pDst[k] = a[i];
i++;
}
else
{
pDst[k] = b[j];
j++;
}
k++;
}
while (i < nLen1)
{
pDst[k] = a[i];
i++;
k++;
}
while (j < nLen2)
{
pDst[k] = b[j];
j++;
k++;
}
return pDst;
} int main()
{
int *p = NULL;
p = Merger_Sort(a,b,,);
for (int i = ; i <; i++)
{
cout << p[i];
}
delete[] p; getchar();
return ;
}
(2) 普通归并排序 ；将二路归并扩展到一般情况，将一个序列分为N组，每组都是一个有序的数组，对两两之间进行归并
// ConsoleApplication7.cpp : 定义控制台应用程序的入口点。
// #include "stdafx.h"
//二路归并的前提是两个结构的元素已经是有序的（同样的顺序）
int a[] = { ,,,, };
int b[] = { ,,,,, };
void Two_MergeSort(int *pA1, int *pA2, int nA1Len, int nA2Len, int *pOut)
{
int i = ; int j = ;
int nDstPos = ;
while (i < nA1Len&&j < nA2Len)
{
if (pA1[i] > pA2[j])
{
//找到同一顺序的元素中较小的放入pOut中
pOut[nDstPos++] = pA2[j++];
}
else
pOut[nDstPos++] = pA1[i++];
}
while (i < nA1Len)
{
pOut[nDstPos++] = pA1[i++];
}
while (j<nA2Len)
{
pOut[nDstPos++] = pA2[j++];
}
} //输入的Pos指的是坐标,可以比较一下与二路归并的区别
void General_Two_MergeSort(int *pA, int nStartPos, int nMidPos, int nEndPos, int *pOut)
{
int i = nStartPos;
int j = nMidPos + ;
int k = nEndPos;
int nDstPos = nStartPos;
printf("对区间[%d,%d]和区间[%d,%d]进行排序\n", nStartPos, nMidPos, nMidPos + , nEndPos);
while (i <= nMidPos&&j <= nEndPos)
{
if (pA[i] > pA[j])
{
pOut[nDstPos++] = pA[j++];
}
else
{
pOut[nDstPos++] = pA[i++];
}
}
while (i <= nMidPos)
{
pOut[nDstPos++] = pA[i++];
}
while (j <= nEndPos)
{
pOut[nDstPos++] = pA[j++];
}
for (int n = nStartPos; n <= nEndPos; n++)
{
pA[n] = pOut[n];
}
static int nCount = ;
printf("第%d次调用\n",++nCount);
//printf("参数分别是：StartPos:%d,MidPos:%d,EndPos:%d\n", nStartPos,nMidPos,nEndPos);
//printf("当前排序的成员有%d个，分别是：\n",nEndPos-nStartPos+1);
for (int n = nStartPos; n <= nEndPos; n++)
{
printf("%d ",pOut[n]);
}
printf("\n");
printf("\n");
printf("\n");
} //推广到更普通的归并排序
//归并排序的核心是将一串数字中的数字分成两组，先对分成的每一组进行深度归并，最后再对初始的两组进行归并
void Merge_Sort(int *pA, int nLow, int nHigh, int *pOut)
{
if (nLow < nHigh)
{
int nMid = (nLow + nHigh) / ;
//左边递归，直到只含有一个元素
Merge_Sort(pA, nLow, nMid, pOut);
//右边递归，直到只含有一个元素
Merge_Sort(pA, nMid + , nHigh, pOut);
//对两个元素进行递归排序
General_Two_MergeSort(pA, nLow, nMid, nHigh, pOut);
} } int main()
{
int c[] = { };
int Dst[] = { ,,,,,, };
//Two_MergeSort(a,b,5,6,c);
Merge_Sort(Dst, , , c);
int i = ;
while (i < )
{
printf("%d ", c[i++]);
} getchar();
return ;
}