十大排序算法

`目录`

1.归并排序

1.1 递归算法1.2 非递归算法1.3 merge接口 2.冒泡排序3.插入排序4.希尔排序5.选择排序6 快速排序7.堆排序

7.1 调整堆7.2 堆的构建 8 计数排序9 桶排序10 基数排序
本文主要介绍排序各大排序算法，话不多说，先介绍各种排序方式。同时分析其复杂度，稳定性，适用情景。
注：排序算法可在leetcode内进行测试
leetcode-921.

ps:稳定性- 比如数组4 3 1 4 6 在升序排序之后，第一个4依旧还是在前面，说明排序算法是稳定的。

各大排序算法稳定性、复杂度分析
ps:图片来源吴师兄学算法，我关注的一个不错的算法类博主，有兴趣可搜索查看。

1.归并排序 1.1 递归算法

核心思路：利用分治的思想，将原数组分为两半，递归的不断分为两半，先排序左右两半，再对两个有序的数组进行合并

//归并排序[begin,end]
void mergeSort(vector & nums,int begin, int end)
{
	if (begin >= end) return;

	//数组 分为两半，分别排序
	int mid = begin + (end - begin) / 2;
	mergeSort(nums,begin,mid);	
	mergeSort(nums,mid+1,end);
	merge(nums,begin,mid,end);	
}

它的时间复杂度是稳定的，O(nlogn),空间复杂度同时只需要一个O(n)数组，为O(n).稳定性看merge函数，它是稳定的

1.2 非递归算法

核心思路：如何做到非递归，需要自底向上的进行合并。
j
假设数组有8个元素，递归算法是4+4 --> 2+2->2+2 -> 1+1 1+1 1+1 1+1. 自底向上算法是先计算1+1 1+1 1+1 1+1 .先两两元素merge好，再继续2+2 2+2 ，一步步往上merge.

void mergeSort(vector& nums)
 {
	//自底向上归并排序
	int length = nums.size();
	for (int i = 1; i < length; i <<= 1)		//每次选择1-2-4-8个元素
	{
		int j = 0;
		while (j+i < length)	//对两组元素进行 merge[j,j+i), [j+i,j+2*i)  
		{
			merge(nums,j,j+i-1, (j+2*i-1) < length ? (j+2*i-1) :  (length-1) );		
			//注意j+2*i可能越界
			j += 2*i;
		}
	}
}

它的时间复杂度是稳定的，O(nlogn),空间复杂度减少为O(1).稳定性看merge函数，它是稳定的

1.3 merge接口

无论是递归，还是非递归，都需要用到merge接口，merge算法的核心思想就是双指针，不断加入最小的元素。

void merge(vector & nums,int begin, int mid,int end)
{
	vector vRes;
	int p = begin;
	int q = mid+1;
	while (p <= mid && q <= end)
	{
		if (nums[p] <= nums[q]) 	//<=保证算法的稳定性
		{
			vRes.push_back(nums[p++]);
		}
		else 
		{
			vRes.push_back(nums[q++]);
		}
	}

	while (p <= mid)
	{
		 vRes.push_back(nums[p++]);
	}

	while (q <= end)
	{
		 vRes.push_back(nums[q++]);
	}

	for (int i = 0; i < vRes.size(); ++i)
	{
		nums[begin++] = vRes[i];
	}
}

2.冒泡排序

冒泡排序，估计是大部分人学的第一个排序算法，简单经典。
核心思想就是从数组首部开始，每次冒出一个最大的值到数组尾部，简称"冒泡"

//冒泡排序
vector bubbleSort(vector& nums)
{
	//从数组首部开始，每次冒出一个最大的值到数组尾部，简称"冒泡"
	for (int i = 0; i < nums.size() - 1; ++i)
	{
		bool swapFlag = false;
		//nums.size()-i往后的数据是有序的，无需比较
		for (int j =1; j < nums.size()-i; ++j)	
		{
			
			if (nums[j] < nums[j-1])
			{
				swapFlag = true;
				swap(nums[j-1],nums[j]);
			}
		}
		if (!swapFlag) break;		//数组有序，没有数据交换，提前结束循环
	}
	return nums;
}

可以看出，平均时间复杂度是O(n^2), 空间复杂度是O(1)，算法是稳定的(元素相同不做交换)

3.插入排序

核心思想：将数组分为已排序部分和未排序部分，每次从未排序部分中取出一个元素，正确插入到已排序部分中。核心就是将新的元素插入到已排序数组中

vector insertSort(vector& nums) 
{
	//将数组分为已排序部分和未排序部分，每次从未排序部分中取出一个元素，正确插入到已排序部分中
	int length = nums.size();
	for (int i = 1; i < length ; ++i)	//依次判断 [1,length-1]内的元素，判断他们的插入位置
	{
		int val = nums[i];	//要插入的元素
		int j = i -1;
		for (; j >= 0; --j)
		{
			if (nums[j] > val)		//元素后移
			{
				nums[j+1] = nums[j];
			}
			else break;			//已找到指定位置
		}
		nums[j+1] = val;		//新的位置
	}
	return nums;
}

可以看出，平均时间复杂度是O(n^2), 空间复杂度是O(1)，算法是稳定的(元素相同不做交换)
情况好是数组是升序的，时间复杂度是O(n),情况差是数组是降序的，时间复杂度是O(n^2).

对比冒泡排序，它更优先，每次时只需要比较并赋值一次，冒泡排序需要比较然后交换(赋值3次).

4.希尔排序

希尔排序也是一种优化的插入排序。从插入排序中可以看出，每次插入新元素时，我们都是以步长为1对前面元素进行比较，移动。我们能不能考虑进行多次循环，分别以步长为2 ，步长为3，步长为4等对前面元素进行分析呢。这就是希尔排序算法的由来。
假设步长为gap, 一种经典的gap取法是，第一次遍历选择gap=length/2, 第二次 gap= gap/2 ,直到最后一次gap=1. （只要最后一次gap=1都可以保证正确排序）.
eg: gap= 2

步长为2, 数字3 1 0 9 7 同属一组，插入排序时在同组内比较移动.

//希尔排序， 分段插入排序，  对0，gap，2gap，3gap，。。同属同一系列内的元素进行插入排序
//gap取值 从 gap/2，gap/4。。。1  
vector shellSort(vector& nums) 
{
	int length = nums.size();			//希尔排序，分段使用插入排序
	for (int gap = length / 2; gap >= 1; gap /= 2)
	{
		for (int i = gap; i < length; ++i)
		{
			//对于位置i的元素， 根据当前步长，插入合适的位置
			int j = i;
			int value = nums[j];
			while (j >= gap && value< nums[j-gap])
			{
				nums[j] = nums[j-gap];
				j-=gap;
			}
			nums[j] = value;		
		}
	}
	return nums;
}

希尔排序的复杂度取决于gap的计算方式，整体来说比插入排序要快，但是它是不稳定的(多步分段插入排序破坏了原有的顺序)。

5.选择排序

核心思路：选择排序类似插入排序，每次从未排序数组中选择一个最小的值放入数组首部。

//选择排序：每次在未排序序列中，选择最小的一个数，然后放入已排序数组的尾部
vector selectSort(vector& nums) 
{
	int length = nums.size();
	for (int i = 0; i < nums.size(); ++i)
	{
		int minValue = nums[i];
		int minIndex = i;
		//从[i,n-1]中选择最小的一个数， 和i位置元素进行交换
		for (int j = i + 1; j < nums.size(); ++j)		
		{
			if (nums[j] < minValue)	//<保证稳定性
			{
				minValue = nums[j];
				minIndex = j;
			}
		}
		swap(nums[i],nums[minIndex]);
	}
	return nums;
}

可以看出，无论何种情况他的复杂度都是O(n^2),空间复杂度未O(1). 它是稳定的.

6 快速排序

排序算法中较为经典的算法，快排，顾名思义，就是一种快速的排序算法。
核心思想：它和归并排序类似，也是分治的思想。选取一个基准点，将比基准点小的值放基准点左边，把比基准点值大的放在基准点右边。不断分治。代码如下

//选择基准点 排序，比基准点大的放一边，比基准点小的放另外一边， 不断分治
void quickSort(vector & nums,int begin,int end)
{
	if (begin >= end) return;

	int splitPos = Partition(nums,begin,end);
	quickSort(nums,begin,splitPos-1);
	quickSort(nums,splitPos+1,end);
}

可以看出，核心的算法就是Partition算法。我们采用双指针思路，左边指针找到一个比基准值大的，右边指针找到一个比基准值小的，然后交换.

int Partition(vector & nums,int begin,int end)
{
	//以最后一个元素作为基准点
	int basevalue = nums[end];
	int i = begin;
	int j = end;

	//哨兵i从数组左边开始，找到第一个比基准点大的值
	// 哨兵j从数组右边开始，找到第一个比基准点小的值， 互相交换位置后，继续哨兵移动
	while (i < j)
	{
		while (i < j && nums[i] <= basevalue) i++;
		while (j > i && nums[j] >= basevalue) j--;

		if (i == j)break;
		swap(nums[i],nums[j]);
	}
	swap(nums[i],nums[end]);
	return i;
}

它是跳跃式交换，可以看出算法是不稳定的。平均时间复杂度是O（nLogN），当数组有序时，退化成O(n^2)。空间复杂度为O(1)

为何会退化，主要是基准点的选择影响。数组有序时，选择最右边值作为基准点，会比较每一个数.
可以进行简单的优化–三数取中法
在选取基准点时，可以对数组最左边，最右边，中间的三个值，取中间的值作为基准点，这样不会退化太严重。

int Partition(vector & nums,int begin,int end)
{
	int midPos = getMidPos(nums,begin,end,begin + (end-begin)/2);		
	//左、右、中间 去 一个中间的值作为基准点  
	swap(nums[midPos],nums[end]);		//巧妙思路，统一取最右边的值，下面while循环顺序一致
	//以最后一个元素作为基准点
	int basevalue = nums[end];
	int i = begin;
	int j = end;

	//哨兵i从数组左边开始，找到第一个比基准点大的值
	// 哨兵j从数组右边开始，找到第一个比基准点小的值， 互相交换位置后，继续哨兵移动
	while (i < j)
	{
		while (i < j && nums[i] <= basevalue) i++;
		while (j > i && nums[j] >= basevalue) j--;

		if (i == j)break;
		swap(nums[i],nums[j]);
	}
	swap(nums[i],nums[end]);
	return i;
}

//getMidPos自己实现，取三值中中间那个值.

7.堆排序

堆的定义：如果二叉树中每个父节点的值比左右子节点更大(更小),它构成了一个堆。
大根堆：父节点值比左右节点更大，反之就是小顶堆.

回到数组排序，将数组元素构建成一个二叉树，每次从堆顶中取出一个元素，再重新调整堆，不断循环，就可以得到一个有序数组。

void heapSort(vector & nums)
{
	makeHeap(nums);		//建立大顶堆

	//将堆顶元素放入数组最后面，从而原地adjustHeap， 变成升序序列
	for (int i = nums.size()-1; i >= 0; --i)
	{
		swap(nums[0],nums[i]);
		adjustHeap(nums,0,i);
	}
}

这里用到一个节省空间复杂度的方法，求升序序列时构建大顶堆，每次和数组尾部元素交换，这样构成一个升序序列（这也是从堆顶删除元素的方式）.

7.1 调整堆

adjustHeap接口，此时nums[0] 堆顶元素可能不符合堆的结构要求，对堆顶元素不断调整，将它放到合适

//自定向下  保证 父节点值 比左右子节点的值还大
void adjustHeap(vector & nums,int pos,int size)
{
	int maxIndex = pos;
	while(true)
	{
		//父节点pos和左子节点2pos+1 右子节点2pos+2，找出一个最大的
		if ( 2*pos+1 < size && nums[2*pos+1] > nums[maxIndex]) maxIndex = 2*pos + 1;
		if ( 2*pos+2 < size && nums[2*pos+2] > nums[maxIndex]) maxIndex = 2*pos + 2;
		if (maxIndex == pos) break;
		swap(nums[pos],nums[maxIndex]);
		pos = maxIndex;
	}
}

7.2 堆的构建

堆的构建也是利用了adjustHeap,对所有有子节点的父节点，依次进行调整操作，即可构建一个堆

//堆的建立
void makeHeap(vector &nums)
{
	int length = nums.size();
	for (int i = length / 2 -1;i >= 0; --i)		//对 有子节点的 节点，不断进行堆化操作
	{
		adjustHeap(nums,i,length);
	}
}

可以看出，堆排序时不稳定的(参考相同的值位于两个不同的数)
它的空间复杂度经过优化，可以达到O(1)，时间复杂度为O(n^2)

8 计数排序

计数排序是一种线性排序算法，它适应于一种特殊的情况。数据元素个数远远大于数据范围值。并且数据可以稳定放入桶中(eg:小数值无法合适的放入桶中)
eg ：100万考生的高考分数排序，分数从0-750. 只需要分配751个桶，将数据丢入桶中即可.

//计数排序：特定应用场景- 适合 元素分布在一个小范围内，数组大小远大于这个范围
	void countSort(vector &nums)
	{
		//假设数组分布在0-maxValue中
		if (nums.size() == 0) return;
		int maxValue = nums[0];
		for (int i = 1; i < nums.size(); ++i)
		{
			if (nums[i] > maxValue) maxValue = nums[i];
		}

		//count[i] 代表小于i的值有多少个
		vector count(maxValue+1);
		for (int i = 0; i < nums.size(); ++i)
		{
			count[nums[i]]++;
		}
		for (int i = 1; i < count.size(); ++i)
		{
			count[i] += count[i-1];
		}

		//如果只是单纯的数字排序，直接输出count即可。如果需要稳定排序，逆序遍历数组
		//逆序遍历nums数组，根据count对应元素的值，放入合适的位置(逆序保证算法的稳定性)
		vector res(nums.size());
		for (int i = nums.size()-1;i >= 0; --i)
		{
			res[--count[nums[i]]] = nums[i];
		}
		nums = res;
	}

算法是稳定的，为了保证稳定性，它逆序的将每个元素放入对应的位置.
它适用于特定的状况，时间复杂度是O(n).空间复杂度也是O(n)

9 桶排序

将要排序的数据，放入有序的几个桶中，桶内用常规其他排序算法，根据顺序依次输出各个桶的顺序。
eg:假设数据分布在1-10万中，设立10个桶，0-1万，1-2万，2-3万等，依次放入，桶内排序后再依次输出即可。

桶排序对数据的要求比较高，要求均匀分布，否则有些桶内数据太多，直接退化成普通排序。
桶排序最合适的是外部排序，数据分布在磁盘等外界设施内，无法一次全部加载进入内存。此时一次一次的读取。。

代码略了.主要求得数据的最大值和最小值，创建合适数量的桶，将元素放入对应的桶中

10 基数排序

基数排序类似桶的思想，多次排序。
eg：数据有3位，0-999. 建立10个桶
1：关注个位数，将元素放入桶中
2：将元素串联起来，关注十位数，将元素放入桶中
3：将元素串联起来，关注百位数，将元素放入桶中.

得出的数据就是有序的。

//获取数组中最大元素
int getMax(vector& nums)
{
	int maxValue = nums[0];
	for (int i = 1; i < nums.size(); ++i)
	{
		if ( nums[i] > maxValue) maxValue = nums[i];
	}
	return maxValue;
}

//按位数进行 桶排序
void countSortR(vector& nums,int exp)
{
	if (exp == 0) return;

	//对数组中元素，取第n位的数字放入 桶中
	int length = nums.size();
	vector vBucket[10];
	for (int i = 0; i < nums.size(); ++i)
	{
		vBucket[ (nums[i] / exp) % 10].push_back(nums[i]);
	}

	nums.clear();
	for (int i = 0; i < 10; ++i)
	{
		nums.insert(nums.end(),vBucket[i].begin(),vBucket[i].end());
	}
}


//基数排序
vector  radixSort(vector& nums)
{
	if (nums.size() <= 1) return nums;

	//获取数组中最大元素
	int maxValue = getMax(nums);

	//从个位到最高位，取对应位的数放入10个桶中
	for (int exp = 1; maxValue / exp > 0; exp *= 10)
		countSortR(nums,exp);

	return nums;
}

十大排序算法

Java相关栏目本月热门文章