七大排序汇总

一、选择排序思想：

遍历数组，选择找到最大值，记录最大值下标maxindax，然后将最大值与最后一个值交换，即swap（vec[maxindax],vec[n-1]);
在剩下的待排序数组中，重新找到最大值，重复第一步，swap(vec[maxidnax],vec[n-2]),循环操作，直至数组排序完成。

代码：

#include
#include
using namespace std;
void selectSort(vector&vec,int n)
{
	//j代表是待排序数组的个数,下标对应就是0到j-1
	for (int j = n; j >= 1; j--)
	{
		int max = vec[0];
		int maxindax = 0;
		for (int i = 0; i < j; i++)
		{
			if (vec[i] > max)
			{
				//找到最大数，并且记录下标maxIndax
				max = vec[i];
				maxindax = i;
			}
		}
		//交换最大值与待排序数组的最后一个
		swap(vec[maxindax], vec[j - 1]);
	}
}
int main()
{
	vectorvec = { 2,3,5,8,9,7,4,6,1 };
	selectSort(vec, vec.size());
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n2)

第一次排序时是n个元素，比较n-1次

第二次排序时是n-1个元素，比较n-2次

...

第n-1次排序时是2个元素，比较1次

第n次排序时是1个元素，比较0次

元素交换次数为k （ k

时间复杂度=比较次数+交换次数

故选择排序时间复杂度为O(1+2+3+...+n-1+k)=O(n*(n-1)/2+k)=O(n2)

空间复杂度：O(1)

在原数组上操作，即使用了常数级空间O(1)

稳定性：不稳定

实例：3 2 3 1 从小到大排序（选择最小的放前面），排序之后红色3在黑色3前面，所以不稳定。

二、冒泡排序思想：

从左到右，相邻两数两两比较，若下标小的数大于下标大的数则交换，将最大的数放在数组的最后一位(即下标n-1的位置)
采用相同的方法，再次遍历数组，将第二大的数，放在数组倒数第二的位置(即n-2的位置)，以此类推，直到数组有序
优化：当数组在整个遍历过程中没有发生交换，说明待排序数组已经有序，此时可以直接结束排序过程(用bool类型变量作标记)。

代码：

#include
#include
using namespace std;
void bubbleSort(vector&vec, int n)
{
	for (int j = n; j >= 1; j--)
	{
		bool flag = true;
		for (int i = 0; i < j - 1; i++)
		{
			if (vec[i] > vec[i + 1])
			{
				swap(vec[i], vec[i + 1]);
				flag = false;
			}
		}
		if (flag) return;
	}
}
int main()
{
	vectorvec = { 2,3,5,8,9,7,4,6,1 };
	bubbleSort(vec, vec.size());
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n2)

最好时间复杂度(有序情况)：O(n)

比较n-1次，交换0次故最好时间复杂度为O(n)

最坏时间复杂度(逆序情况):O(n2)

第一次排序时是n个元素，比较n-1次,交换n-1次

第二次排序时是n-1个元素，比较n-2次，交换n-2次

...

第n-1次排序时是2个元素，比较1次，交换1次

第n次排序时是1个元素，比较0次，交换0次

故选择排序时间复杂度为O((1+2+3+...+n-1)*2)=O(n*(n-1))=O(n2)

空间复杂度：O(1)

在原数组上操作，即使用了常数级空间O(1)

稳定性：稳定

三、插入排序思想：

将数组分为有序表和无序表，每次从有序表中取出一个元素，插入到有序表的适当位置，刚开始有序表中只有一个数，无序表中有n-1个数。
每遍历一次，有序表中元素增加一个，无序表中元素个数减少一个，重复n-1次，完成排序。

代码：

#include
#include
using namespace std;
void insertSort(vector&vec, int n)
{
	//j表示无序表第一个元素下标
	for (int j = 1; j 
		//i表示有序表最后一个元素下标
		for (int i = j - 1; i >= 0; i--)
		{
			if (vec[i] > vec[i + 1])
			{
				swap(vec[i], vec[i + 1]);
			}
		}
	}
}
int main()
{
	vectorvec = { 2,3,5,8,9,7,4,6,1 };
	insertSort(vec, vec.size());
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n2)

最好时间复杂度(全部有序)：O(n)

比较n-1趟，每一趟比较一次，不移动元素，最好时间复杂度为O(n)

最坏时间复杂度(全部逆序)：O(n2)

第一次排序时有序表1个元素，无序表n-1个元素，比较1次，移动1次

第二次排序时有序表2个元素，无序表n-2个元素，比较2次，移动2次

...

第n-1次排序时有序表n-1个元素，无序表1个元素，比较n-1次，移动n-1次

故最坏时间复杂度为O((1+2+3+...+n-1)*2)=O(n*(n-1))=O(n2)

空间复杂度：O(1)

在原数组上操作，即使用了常数级空间O(1)

稳定性：稳定

四、桶排序思想：

原理：将数值作为桶号，遍历整个数组，将相应的桶进行计数

遍历原数组，找到最大值max，然后申请max+1个空间(桶)，初始化为0(下标为0-max)，即vectorbucket(max+1,0)
再次遍历原数组，找到每个数值对应的桶号，并对桶计数++，即bucket[vec[i]]++
遍历桶数组，看对应的桶内计数为几就取出几下下标值(桶号)，放到原数组中。

代码：

#include
#include
using namespace std;
void bucketSort(vector&vec, int n)
{
	int max = vec[0];
	for (int i = 0; i < n; i++)
	{
		if (vec[i] > max)
		{
			max = vec[i];
		}
	}
	//申请max+1个桶
	//int *bucket = new int[max + 1];
	//给每个桶赋初值为0；
	//memset(bucket, 0, (max + 1) * sizeof(int));
	vectorbucket(max + 1, 0);


	//遍历原数组，把相应的数放到相应的桶里
	for (int i = 0; i < n; i++)
	{
		bucket[vec[i]]++;
	}
	int index = 0;
	//从桶里把数取出来, i代表的数值对应桶下标， bucket[i]代表的是个数
	for (int i = 0; i < bucket.size(); i++)
	{
		while (bucket[i] > 0)
		{
			vec[index++] = i;
			bucket[i]--;
		}
	}
}
int main()
{
	vectorvec = { 2,3,5,8,9,7,4,6,1 };
	bucketSort(vec, vec.size());
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n)

遍历数组找最大值max 时间复杂度为O(n)

遍历数组把对应的数放入对应的桶时间复杂度也为O（n）

遍历桶，从桶中把数取出来放入原数组，假设有m个空桶，则时间复杂度为O(n+m)

总上所述时间复杂度为O(3n+m)=O(n)

空间复杂度：O(n)

创建了辅助数组(桶)，即max+1个桶，(不管创建多少桶，只要创建了辅助数组，空间复杂度就是O(n))

稳定性：稳定

五、堆排序基础：

1.完全二叉树:若设二叉树的深度为h，除第h层外，其他各层(1~h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，只能从最深处最右边从右往左缺省。

2.最大堆结构：是一个完全二叉树，堆中每个节点的值总是不大于其父亲节点的值（即根节点总是最大的元素）

3.创建最大堆:把所有非终端结点检查一遍，看是否满足最大堆的要求，如果不满足，则进行调整(检查当前结点是否满足:根>=左、右，若有不满足，则将当前结点与更大的一个孩子进行交换，若元素互换破坏了下一级的堆，则采用相同的方式继续往下调整，直至符合最大堆要求)，我们以数组{53,17,78,9,45,65,87,32}为例，过程如图所示:

(二叉树的终端节点：度为0的节点，也就是叶子节点)。

4.基于最大堆进行排序过程:每趟将堆顶元素加入有序子序列(与待排序序列最后一个元素交换,并将待排序序列再次调整最大堆)，再次重新调整为大根堆的过程只需要从整棵树的根节点向下调整即可过程如图所示：

思想：

1.将待排序数组形象成一个最大堆结构，从最后一个父节点(n/2-1)开始将其调整为最大堆 (父节点下标为i，则左孩子下标为2i+1，右孩子下标为2i+2)

2.将堆顶元素与待排序数组最后一个元素进行交换

3.待排序数组数量减少一个，将待排序数组重新调整成最大堆结构，重复2、3操作n-1 次，将所以数据排序完成。

代码：

#include
#include
using namespace std;
//start 调整最大堆的起始位置，end 调整最大堆的结束位置
void adjustHeap(vector&vec, int strat, int end)
{
	int father = strat; // 根节点
	int child = 2 * father + 1; //左子树
        //while 循环是为了在调整最大堆的过程中破坏子树的结构，继续向下调整
	while (child < end) 
	{    
          //因为child是左子树，根节点要大于左右子树，所以要在子树中找到最大的再与根节点比较，所以要防止右子树越界就是在数组中下标为child+1的元素，child就是子树中最大的元素。
		if (child + 1 < end && vec[child + 1] > vec[child]) child++;
        //如果根节点大于子树就交换
		if (vec[child] > vec[father])
		{
			swap(vec[child], vec[father]);
        //如果发生交换就继续向下调整，因为可能破坏子树最大堆结构
			father = child;
			child = 2 * father + 1;
		}
        //如果没发生交换就退出该函数
		else return; 
	}
}
void HeapSort(vector&vec)
{
	//从最后一个有子节点的节点开始调整
	for (int i = vec.size() / 2 - 1; i >= 0; i--)
	{
		adjustHeap(vec, i, vec.size());
	}
	for (int i = vec.size() - 1; i >= 1; i--)
	{
		swap(vec[0], vec[i]);
		//只有下标为0的元素被打乱，从根节点开始向下调整;
		adjustHeap(vec, 0, i);
	}
}
int main()
{
	vectorvec = { 53,17,78,9,45,65,87,32};
	HeapSort(vec);
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n*logn)

n个节点的完全二叉树有log 2(n+1)层

创建最大堆过程中，两两元素相互比较共比较n-1次，在交换过程中可能破坏某个最大堆结构，我们可以假设共调整k次可以恢复最大堆结构，故建堆过程时间复杂度为O(n+k)=O(n)。

每个根节点最大下降log(n+1)-1层，每下降一层需比较两次，假设每个根节点都下降到最底层，则下降一个根节点的时间复杂度为O(2*(log(n+1)-1))，共有n-1个根节点需要下降，则下降过程的时间复杂度为O((n-1)*2*(log(n+1)-1))=O(n*logn)。

综上所述，堆排序时间复杂度为O(n)+O(n*logn)=O(n*logn)。

空间复杂度：O(1)

在原数组上操作，即使用了常数级空间O(1)

稳定性：不稳定

实例：67 21 3 21

六、快速排序引例：三色旗思想：

问题描述：

有一个只由0，1，2三种元素构成的整数数组，请使用交换、原地排序而不是使用计数进行排序。

解题思路：

定义两个下标left和right；

left的含义：使数组中<=left的部分都比1小，left的初始值为-1；

right的含义：使数组中>=right的部分都比1大，right的初始值为n；

从index = 0开始遍历；

根据index所指向的值分别进行不同的操作；

如果vec[index] = 0，swap(vec[index++],vec[++left]；

(这里index++的原因是因为index左边不可能有==2的数据了)

如果vec[index] = 1，index++；

如果vec[index] = 2，swap(vec[index],vec[--right])。

代码实现: 以{ 0,1,2,0,0,1,2,1,0 } 为例：

#include
#include
using namespace std;
void Quick(vector&vec, int L, int R)
{
	int left = L - 1;
	int right = R + 1;
	int temp = 1;
	int index = 0;
	while (index < right)
	{
		if (vec[index] == temp)
		{
			index++;
		}
		else if(vec[index]
			swap(vec[index++], vec[++left]);
		}
		else
		{
			swap(vec[index], vec[--right]);
		}
	}
}
int main()
{
	vectorvec = { 0,1,2,0,0,1,2,1,0 };
	Quick(vec, 0, vec.size() - 1);
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

思想：

三色旗问题：找一个基准值(这里选取待排序数组最左边的那个值)，然后将待排序数组分为三部分：

第一部分：数据全部小于基准值

第二部分：数据全部等于基准值

第三部分，数据全部大于基准值

2、将第一部分和第三部分分别进行三色旗问题处理，直到index>=j，即数组有序

代码：

#include
#include
using namespace std;
pairquick(vector&vec, int L, int R)
{
	int i = L - 1;
	int j = R + 1;
	int index = L;
	int temp = vec[L];
	while (index < j)
	{
		if (vec[index] > temp)
		{
			swap(vec[index], vec[--j]);
		}
		else if (vec[index] < temp)
		{
			swap(vec[index++], vec[++i]);
		}
		else
		{
			index++;
		}
	}
	return make_pair(i, j);
}
void quickSort(vector&vec, int L, int R)
{
	if (L >= R)return;
	pairp = quick(vec, L, R);
	quickSort(vec, L, p.first);
	quickSort(vec, p.second, R);
}


int main()
{
	vectorvec = {49,38,65,97,76,13,27,49 };
	quickSort(vec,0,vec.size()-1);
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n*logn)

每次进行三色旗问题处理第一部分和第三部分需要处理的元素不超过n个，故时间复杂度不超过O(n)

最好时间复杂度(每次选取中位数作为基准值)：O(n*logn)

若每次选取中位数当做基准值，则n个数会递归log(n+1)次，即会进行log(n+1)次三色旗问题，每处理一次三色旗问题时间复杂度为O(n)，所以最好时间复杂度为O(n*logn);

最坏时间复杂度(每次选取最大值或者最小值作为基准值，即正序或者逆序时)：O(n2)

每次选取最值作为基准值，则n个数会递归n次，即会进行n次三色旗问题，每处理一次三色旗问题时间时间复杂度为O(n),所以最好时间复杂度为O(n*n)=O(n2);

空间复杂度：O(logn)或者O(n)

空间复杂度由时间复杂度决定因为函数调用需要申请函数栈:

当选取中位数作为基准值时递归调用log(n+1)次函数，故其空间复杂度为O(logn);

当选取极值作为基准值时递归调用n次函数，故其空间复杂度为O(n);

稳定性：不稳定

实例：5 7 7 1 1 以5 为基准值交换之后红色 7 在黑色 7 前面

七、归并排序基础：二分法

二分法查找思想：(适用于有序数组)

(1)首先确定整个查找区间的中间位置mid=(right-left)/2+left;

(2)用待查关键字值与中间位置关键字值进行比较；

若相等，则查找成功；

若大于，则在后半个区域中继续进行折半查找。

若小于，则在前半个区域中继续进行折半查找。

查找成功，返回关键字所在数组下标，没找到返回-1；

实现代码:

#include
#include
using namespace std;
int HalfSearch(vector&vec, int target)
{
	int L = 0;
	int R = vec.size() - 1;
	while (L <= R)
	{
		int mid = (R - L) / 2 + L;
		if (target < vec[mid])
		{
			R = mid - 1;
		}
		else if(target>vec[mid])
		{
			L = mid + 1;
		}
		else
		{
			return vec[mid];
		}
	}
	return -1;
}
int main()
{
	vectorvec = { 1,3,5,6,4,8,7 };
	int n = HalfSearch(vec, 8);
	cout << n;
	return 0;
}

时间复杂度分析:

假设总共n个元素：

第1次折半后还剩n/2个元素

第2次折半后还剩n/4个元素

...

第k次折半后还剩n/2k个元素

假设m次折半后还剩1个元素，则有n/2m=1，得m=logn

故二分法时间复杂度为O(logn)。

思想：

将两个有序数组合并成一个有序数组。

1.将数组进行分解，当分解成单个元素为一组的时候才是组内有序的 (将目标数组拆成两个数组，设初始数组最小下标为L，最大下标为R，控制项mid=(R-L)/2+L,得到两个子数组{vec[L],...,vec[mid]}和{vec[mid+1],...,vec[R]},对两个子数组再次进行拆分递归，递归结束条件：L==R，即单个数值。)

2.将两两有序的数组进行合并，先申请等于两个数组合并后大小的空间，然后将两个排序好数组逐一比较，向申请的空间中放入较小元素，直至两个有序数组组合成为一个有序数组。重复第二步，直至排序完成。(对拆分递归后的有序数组进行排序结合生成结果数组，将其中的较小值依次放入结果数组，由于操作的数组本身是有序数组，比较后第一个放入的较小值其实是两个数组的最小值，合并之后的结果数组也是有序数组。数组在逐层区域排序之后，其中的数值完全区域有序，最外层的区域排序将得到最终的结果数组)

代码：

#include
#include
using namespace std;
void Merg(vector&vec, int L, int mid, int R)
{
	//先申请一个辅助数组大小为：R - L + 1
	vectortemp(R - L + 1);
	int i = L, j = mid + 1, index = 0;
	//利用while循环比较两个有序数组分别为： L到mid  和  mid+1到R 
	while (i <= mid && j <= R)
	{
		if (vec[i] <= vec[j])
		{
			temp[index++] = vec[i++];
		}
		else
		{
			temp[index++] = vec[j++];
		}
	}
	//经历过上一个步骤一定有剩余的元素，利用两个while循环判断
	while (i <= mid)
	{
		temp[index++] = vec[i++];
	}
	while (j <= R)
	{
		temp[index++] = vec[j++];
	}
	//将辅助数组中的元素还原到原数组中，还原到对应的位置上 L 到 R
	index = L;
	for (int i = 0; i < R - L + 1; i++)
	{
		vec[index++] = temp[i];
	}
}
void MergSort(vector&vec, int L, int R)
{
	if (L >= R) return;
	int mid = (R - L) / 2 + L;
	MergSort(vec, L, mid);
	MergSort(vec, mid + 1, R);
	Merg(vec, L, mid, R);
}
int main()
{
	vectorvec = { 49,38,65,97,76,13,27 };
	MergSort(vec,0,vec.size()-1);
	for (auto it : vec)
	{
		cout << it << " ";
	}
	return 0;
}

平均时间复杂度：O(n*logn)

归并排序形态上像一颗倒立的二叉树，n个元素的二叉树，高度为log(n+1)层，即n个元素进行归并排序，会递归log(n+1)次，(即类似于n个元素进行二分)，结合二分时间复杂度可得递归过程时间复杂度为O(logn);而每次递归需要排序的元素为n-k个(与快排类似)，其时间复杂度为O(n);

综上所述，归并排序所需的时间复杂度为O(n*logn)

空间复杂度：O(n)

每次递归完合并两个有序数组时都会创建辅助数组，但是函数运行完之后辅助数组会自动释放，所以辅助数组空间并不叠加，仅会保留最后一个辅助数组空间，即上图的第三次归并时所创建的辅助数组，其空间复杂度为O(n)；n个元素进行排序会递归log(n+1)次，所以递归所需要的空间复杂度为O(logn)。

综上所述，归并排序所需空间复杂度为O(n)+O(logn)=O(n)。

稳定性：稳定

七大排序汇总

Java相关栏目本月热门文章