上车吗？大兄弟
最近几天重新温习一下这些经典的算法，看完之后觉得应该总结（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; //记录是否存在交换
//走iDataNum-1趟
for (int i = 0; i < iDataNum - 1; i++) {
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个元素交换，至此选择排序完成。
image.png
以下面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；然后再分别对前半段和后半段进行递归快速排序。其实现细节如下图所示：
image.png
二. 算法分析
平均时间复杂度：O(nlog2n)
空间复杂度：O(n)
稳定性：不稳定
三. 算法实现
public class QuickSort {
public static void quickSort(int[] arr,int low,int high){
int i,j,temp,t;
if(low>high){
return;
}
i=low;
j=high;
//temp就是基准位
temp = arr[low];
while (i<j) {
//先看右边，依次往左递减
while (temp<=arr[j]&&i<j) {
j--;
}
//再看左边，依次往右递增
while (temp>=arr[i]&&i<j) {
i++;
}
//如果满足条件则交换
if (i<j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}
//最后将基准为与i和j相等位置的数字交换
arr[low] = arr[i];
arr[i] = temp;
//递归调用左半数组
quickSort(arr, low, j-1);
//递归调用右半数组
quickSort(arr, j+1, high);
}
public static void main(String[] args){
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
quickSort(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
/********************************************************
*函数名称：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篇有用的文章，目标是签约简书。
如果文章对您有帮助，希望能点个赞或者关注我。
您的关注和点赞是对我最大的鼓励，感谢您的阅读
