排序算法总结 C++

博主： admin
发布时间：2021 年 06 月 05 日
354 次浏览
暂无评论
9772字数
分类：默认分类

使用模板编写，自带类型均可使用，使用类 class 或结构体 struct 时必须重载大于 > 运算符

参数汇总
--------

# 1. 冒泡排序

> 思路：比较相邻两个元素，小者交换到前面
> 从前到后两两交换，一直比较到最后，最大值置于最后

## 1.0 简化冒泡

```cpp
template
void bubbleSort(vector& nums)
{
for (int i = 0; i < nums.size() - 1; ++i)
{
for (int j = 0; j < nums.size() - 1 - i; ++j)
if (nums[j] > nums[j + 1])
swap(nums[j], nums[j + 1]);
}
}
```

## 1.1 优化

用 flag 优化，写有序时跳出循环

```cpp
void bubbleSort(vector& nums)
{
for (int i = 0; i < nums.size() - 1; ++i)
{
bool flag = true;
for (int j = 0; j < nums.size() - 1 - i; ++j)
if (nums[j] > nums[j + 1])
{
swap(nums[j], nums[j + 1]);
flag = false;
}
if(flag)
break;
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |

# 2. 选择排序

> 思路：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
> 再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。

```cpp
template
void selectSort(vector& nums)
{
for (int i = 0; i < nums.size() - 1; ++i)
{
int min = i;
for (int j = i + 1; j < nums.size(); ++j)
{
if (nums[j] < nums[min])
min = j;
}
swap(nums[i], nums[min]);
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |

# 3. 插入排序

> 思路：从数组的第二个元素开始，将元素按顺序插入到前面已经排好序的数组中
> 一般以第一个元素作为起始元素，从第二个元素开始依次插入

```cpp
template
void insertSort(vector& nums)
{
for (int i = 0; i < nums.size() - 1; ++i)
{
for (int j = i + 1; j > 0; --j)
{
if (nums[j] >= nums[j - 1])
break;// 减少比较次数
else
swap(nums[j], nums[j - 1]);
}
}
}
```

## 参数

# 4. 希尔排序

> 思路：希尔排序插入排序的一种更高效的改进版本，非稳定排序算法
> 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
> 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰分成一组，算法便终止
> 与插入排序区别是，插入排序每次递增量是 1 ，希尔排序是 gap

```cpp
template
void shellSort(vector& nums)
{
int i, j, gap;
int n = nums.size();
for (gap = n / 2; gap > 0; gap /= 2)
{
// 共 gap 个组，对每组都执行直接插入排序
for (int i = 0; i < gap; ++i)
{// 此后为插入排序！！！
// 注意内部循环写法
for (j = i + gap; j < n; j += gap)
{
// 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
if (nums[j] < nums[j - gap])
{
T tmp = nums[j];
int k = j - gap;
// 此时插入要向前循环，k 会变化，因此要检验
// 不能简单将上面式子代入！！
while (k >= 0 && nums[k] > tmp)
{
nums[k + gap] = nums[k];
k -= gap;
}
nums[k + gap] = tmp; //交换完成
}
}
}
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(nlogn)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 不稳定 |

# 5. 归并排序

> 思路：分而治之，后序遍历二叉树的思想

```cpp
template
// [] 区间
void mergeSort(vector &nums, int left, int right)
{
if (left < right)
{
int mid = (right + left) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
mergeSortHelpter(nums, left, mid, right);
}
}
template
void mergeSortHelpter(vector &nums, int left, int mid, int right)
{
vector tmp = nums;
int start = left; // // 注意此处 start = left，不是 0
int i = start, j = mid + 1;
// 都是 <=
while (i <= mid && j <= right)
nums[start++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j++];
while (i <= mid)
nums[start++] = tmp[i++];
while (j <= right)
nums[start++] = tmp[j++];
}```
## 参数
| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
|:---------:|:---------:|:---------:|:------:|:---:|
| $O(nlog(n))$ | $O(nlog(n))$ | $O(nlog(n))$ | $O(n)$ | 稳定 |
# 6. 快速排序
> 思路：在数组中选择一个元素作为基准
> 小于基准元素移到基准左边，反之移到基准右边（分区操作）
> 此时基准元素所在位置就是排序完成后，基准元素的最终位置
> 对基准元素的左右两个子集重复一二步，直到子集中剩余一个元素为止

```cpp
template
void quickSort(vector& nums, int left, int right)
{
if (left < right)
{
int pivot = quickSortHelper(nums, left, right);
quickSort(nums, left, pivot - 1);
quickSort(nums, pivot + 1, right);
}
}
template
int quickSortHelper(vector&nums, int left, int right)
{
int pivot = nums[left];
while (left < right)
{
// pivot 取 left，则先从右边开始 --
// 都是交换 left 与 right，pivot 只是起到一个记录的作用
while (left < right&&pivot <= nums[right]) right--;
nums[left] = nums[right];
while (left < right&&nums[left] <= pivot) left++;
nums[right] = nums[left];
}
nums[left] = pivot;
return left;
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(nlog(n))$ | $O(n^2)$ | $O(nlog(n))$ | $O(nlogn)$ | 不稳定 |

# 7. 堆排序

利用堆此种数据结构设计的排序算法
堆是一种特殊的树（完全二叉树叶子结点只可能在最大的两层出现）

> 特点：根节点下标为 0，若父节点下标为 i

1. 其左孩子下标为 2*i+1
2. 右孩子为 2*i+2
3. 第一个非叶子节点为 arr.size()/2-1

- 小顶堆：每个节点的值都 >= 其子节点的值 => 堆排序的升序排序
- 大顶堆：每个节点的值都 <= 其子节点的值 => 堆排序的降序排序
- 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
- 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

## 思想

利用大(小)顶堆记录最大(小)关键词的特性

1. 将数组构建成大顶堆，此堆为初始的无序区(堆顶确定)
2. 将堆顶元素R[0]与最后一个元素R[n-1]交换得到无序区[0,n-2]与有序区[n-1]
3. 调整无序区为新堆，重复2，3
4. 无序区不断减少，有序区逐渐增加，当有序区间元素个数为 n-1 时完成

```cpp
template
void heapSort(vector &nums)
{
int n = nums.size();
//1. 构建一个最大堆
// 从最后一个非叶子节点开始
for (int i = n / 2 - 1; i >= 0; --i)
{
heapSortHelperMin(nums, i, n);
//heapSortHelperMax(nums, i, n);
}
//2. 将堆顶（最大值）与末位交换，再重新调整最大堆
for (int i = n - 1; i > 0; --i)
{
swap(nums[0], nums[i]);
// 构造堆时，遍历每个非叶子节点已经排好序
// 当交换元素时，只会影响最顶端的顺序，最低端是有序区
// 因为堆是整体有序的，因此只需要管理受影响的最顶端，有问题可以递归处理后面受影响的堆
heapSortHelperMin(nums, 0, i);
//heapSortHelperMax(nums, 0, i);
}
}

// 调整堆，不是构造堆
template
void heapSortHelperMax(vector &nums, int father, int length)
{
int maxIndex = father;
// 如有左子树，同时左子树大于父节点，则最大指针指向左子树
if (father * 2 + 1 < length && nums[father * 2 + 1] > nums[maxIndex])
maxIndex = 2 * father + 1;
// 如有右子树，同时右子树大于父节点和左子树，则最大指针指向右子树
if (father * 2 + 2 < length && nums[father * 2 + 2] > nums[maxIndex])
maxIndex = 2 * father + 2;
// 父节点不是最大值，则将父节点与最大值交换，同时递归调整
if (maxIndex != father)
{
swap(nums[maxIndex], nums[father]);
heapSortHelperMax(nums, maxIndex, length);
}
}

template
void heapSortHelperMin(vector &nums, int father, int length)
{
int minIndex = father;
if (father * 2 + 1 < length && nums[father * 2 + 1] < nums[minIndex])
minIndex = 2 * father + 1;
if (father * 2 + 2 < length && nums[father * 2 + 2] < nums[minIndex])
minIndex = 2 * father + 2;
if (minIndex != father)
{
swap(nums[minIndex], nums[father]);
heapSortHelperMin(nums, minIndex, length);
}
}
```

## 构造堆的其它方法

使用 STL 的优先队列，`priority_queue`，需要头文件
底层就是一个堆结构，通过 top() 来访问队首元素
`priority_queue< type, container, function >`
三个参数，后面两个可以省略，第一个不可以。其中：

1. **type**数据类型；
2. **container**实现优先队列的底层容器；
3. **function**元素之间的比较方式；
container，要求必须是数组形式实现的容器，例如vector、deque，不能是list

在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。

```cpp
// 默认为大顶堆
priority_queue big_heap;
//另一种构建大顶堆的方法
priority_queue,less > big_heap2;
//构造一个空的优先队列,此优先队列是一个小顶堆
priority_queue,greater > small_heap;
```

## 优先队列堆排序

```cpp
// 利用优先队列实现
template
// 调整遍历顺序或大小堆，即可逆转排序
void heapSort(vector &nums)
{
int n = nums.size();
//1. 构建一个最大堆
priority_queue> bigHeap;
priority_queue, less> smallHeap;
for (auto x : nums)
bigHeap.push(x);

//2. 将堆顶（最大值）与末位交换，再重新调整最大堆
for (int i = 0; i < n; ++i)
{
nums[i] = bigHeap.top();
bigHeap.pop();
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(nlog(n))$ | $O(nlog(n))$ | $O(nlog(n))$ | $O(1)$ | 不稳定 |

# 8. 计数排序

> 思路：将输入的数据值转化为键存储在额外开辟的数组空间中
> 要求输入的数据：必须在***确定范围***内的***整数***

- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

```cpp
void countSort(vector& nums)
{
int n = nums.size();
int minVal = nums[0], maxVal = nums[0];
for (int i = 0; i < n; ++i)
{
minVal = min(minVal , nums[i]);
maxVal = max(maxVal, nums[i]);
}
vector bucket(maxVal - minVal + 1, 0);
int offset = minVal - 0;

// 将数据存入 bucket
for (auto x : nums)
bucket[x - offset]++;
int j = 0;
for (int i = 0; i < bucket.size(); ++i)
{
// 对应数值是 i+offset
// 每个数值次数是 bucket[i]
// 外部 --
while (bucket[i]--)
nums[j++] = i + offset;
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |

# 9. 桶排序

桶排序是计数排序的升级版，利用函数的映射关系，把计数排序中的多个坑位整合成为一个桶

## 思路

(1) 设置一个定量的数组当作空桶；
(2) 遍历输入数据，并且把数据一个一个放到对应的桶里去；
(3) 对每个不是空的桶进行排序；
(4) 从不是空的桶里把排好序的数据拼接起来。

算法效率在于映射函数的确定。为了更加高效，需要：

1. 在外部空间充足的情况下，尽可能**增大桶的数量**
2. 使用的映射函数能够将输入的 N 个数据**均匀地分配到 K 个桶中**

最快：输入数据均匀分配到每个桶中
最慢：输入数据被分配到同一个桶中
当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)

```cpp
// 桶排序
// 桶的大小
void bucketSort(vector& nums, int bucketSize)
{
int n = nums.size();
if (n < 2) return;
int minVal = nums[0], maxVal = nums[0];
for (int i = 1; i < n; ++i)
{
minVal = min(nums[i], minVal);
maxVal = max(nums[i], maxVal);
}

// 桶的数量，当 bucketSize 为 1 时，退货为计数排序
int bucketCount = (maxVal - minVal) / bucketSize + 1;
int offset = minVal - 0;
vector> bucketVec(bucketCount, vector());

// 元素入桶
for (int i = 0; i < n; ++i)
{
// 重点！！！
bucketVec[(nums[i] - offset) / bucketSize].push_back(nums[i]);
}
// clear 之后，不能直接用 []，因为并没有初始化，需要用 push_back
nums.clear();
for (int i = 0; i < bucketCount; ++i)
{
// 内部可以选择方法对桶内元素进行排序
// 空桶跳过，提高效率
if (bucketVec[i].size() != 0)
{
sort(bucketVec[i].begin(), bucketVec[i].end());
for (auto x : bucketVec[i])
nums.push_back(x);
//nums[j++] = x;
}
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(n+k)$ | $O(n^2)$ | $O(n)$ | $O(n+k)$ | 稳定 |

# 10. 基数排序

一种非比较型整数排序算法，原理是将整数按位数切割成不同的数字，按每个位数分别比较
因为整数可以表达字符串(名字或日期)和特定模式的浮点数，因此基数排序也可用于字符串

### 计数排序，桶排序，基数排序区别

三者都使用了桶的概念，但是

1. 计数排序：每个桶只存储单一键值
2. 桶排序：每个桶存储一定范围的数值
3. 基数排序：根据键值的每位数字来分配桶

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital）

- LSD: 由键值的最右边（最小位）开始, 适用于位数少的序列，可采用桶排序
- MSD: 由键值的最左边（最大位）开始, 适用于位数多的序列，可采用计数排序

> 在进行某个特定位数比较时，要用稳定排序，将上次排序成果保留。例如十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。
> 基数排序对有负数和0的数列难以进行排序

![radixSort](media/16228637990486/radixSort.gif)

![](media/16228637990486/16238487090536.jpg)

```cpp
void radixSort(vector& nums)
{
int maxVal = 0;
for (int x : nums)
if (x > maxVal) maxVal = x;

// d 表示 1，10，100 等，序列最大值长度为3，d = 100
int d = 10;
while (maxVal / 10)
{
d *= 10;
maxVal /= 10;
}

// 从个位开始
int index = 1;
while (index {
// 从0到9总共10个桶
// 每个桶最多有 nums.size()个元素，初始化大小后才能使用 []
// 如何要使用 push_back() 就不要初始化大小，因为再 push_back() 则会将元素保存在初始化大小的元素之后！！！
// 同时放于此处可以不用清空数组，当更换数位时
vector> bucketVec(10, vector());
//将序列的每个数字放在相应的桶里
for (int x : nums)
{
// 当前位上的数值
int digit = (x / index) % 10;
bucketVec[digit].push_back(x);
}

// 重写入数组时遍历秩，当下一轮位数变化时，k 能自己重置为 0
int k = 0;
// 将上一次排序结果覆盖到原数组
for (int i = 0; i < 10; i++)
{
// 若桶内有元素，依次取出放到原数组中
if (bucketVec[i].size()!=0)
{
for (int j = 0; j < bucketVec[i].size(); ++j)
nums[k++] = bucketVec[i][j];
}
}
// 将位数前移
index *= 10;
}
}
```

## 参数

| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 |
| :----------------: | :----------------: | :----------------: | :----------: | :------: |
| $O(n*k)$ | $O(n*k)$ | $O(n*k)$ | $O(n+k)$ | 稳定 |

最后修改：2023 年 03 月 27 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

排序算法总结 C++

admin • 2021 年 06 月 05 日

使用模板编写，自带类型均可使用，使用类 class 或结构体 struct 时必须重载大于 > 运算符参数汇总 
--------# 1. 冒泡排序> 思路：比较相邻两个元素，小者交换到前面 
> 从前到后两两交换，一直比较到最后，最大值置于最后## 1.0 简化冒泡```cpp 
template <typename T> 
void bubbleSort(vector<T>& nums) 
{ 
	for (int i = 0; i < nums.size() - 1; ++i) 
	{ 
		for (int j = 0; j < nums.size() - 1 - i; ++j) 
			if (nums[j] > nums[j + 1]) 
				swap(nums[j], nums[j + 1]); 
	} 
} 
```## 1.1 优化用 flag 优化，写有序时跳出循环```cpp 
void bubbleSort(vector<T>& nums) 
{ 
	for (int i = 0; i < nums.size() - 1; ++i) 
	{ 
	 bool flag = true; 
		for (int j = 0; j < nums.size() - 1 - i; ++j) 
			if (nums[j] > nums[j + 1]) 
			{ 
			 swap(nums[j], nums[j + 1]); 
			 flag = false; 
			} 
		if(flag) 
		 break; 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |# 2. 选择排序> 思路：	首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。 
> 再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。```cpp 
template<typename T> 
void selectSort(vector<T>& nums) 
{ 
	for (int i = 0; i < nums.size() - 1; ++i) 
	{ 
		int min = i; 
		for (int j = i + 1; j < nums.size(); ++j) 
		{ 
			if (nums[j] < nums[min]) 
				min = j; 
		} 
		swap(nums[i], nums[min]); 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 不稳定 |# 3. 插入排序> 思路：从数组的第二个元素开始，将元素按顺序插入到前面已经排好序的数组中 
> 一般以第一个元素作为起始元素，从第二个元素开始依次插入```cpp 
template<typename T> 
void insertSort(vector<T>& nums) 
{ 
	for (int i = 0; i < nums.size() - 1; ++i) 
	{ 
		for (int j = i + 1; j > 0; --j) 
		{ 
			if (nums[j] >= nums[j - 1]) 
				break;// 减少比较次数 
			else 
				swap(nums[j], nums[j - 1]); 
		} 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(n^2)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 稳定 |# 4. 希尔排序> 思路：希尔排序 插入排序的一种更高效的改进版本，非稳定排序算法 
> 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序； 
> 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰分成一组，算法便终止 
> 与插入排序区别是，插入排序每次递增量是 1 ，希尔排序是 gap```cpp 
template<typename T> 
void shellSort(vector<T>& nums) 
{ 
	int i, j, gap; 
	int n = nums.size(); 
	for (gap = n / 2; gap > 0; gap /= 2) 
	{ 
		// 共 gap 个组，对每组都执行直接插入排序 
		for (int i = 0; i < gap; ++i) 
		{// 此后为插入排序！！！ 
			// 注意内部循环写法 
			for (j = i + gap; j < n; j += gap) 
			{ 
				// 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。 
				if (nums[j] < nums[j - gap]) 
				{ 
					T tmp = nums[j]; 
					int k = j - gap; 
					// 此时插入要向前循环，k 会变化，因此要检验 
					// 不能简单将上面式子代入！！ 
					while (k >= 0 && nums[k] > tmp) 
					{ 
						nums[k + gap] = nums[k]; 
						k -= gap; 
					} 
					nums[k + gap] = tmp; //交换完成 
				} 
			} 
		} 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(nlogn)$ | $O(n^2)$ | $O(n)$ | $O(1)$ | 不稳定 |# 5. 归并排序> 思路：分而治之，后序遍历二叉树的思想```cpp 
template <typename T> 
// [] 区间 
void mergeSort(vector<T> &nums, int left, int right) 
{ 
if (left < right) 
{ 
int mid = (right + left) >> 1; 
mergeSort(nums, left, mid); 
mergeSort(nums, mid + 1, right); 
mergeSortHelpter(nums, left, mid, right); 
} 
} 
template <typename T> 
void mergeSortHelpter(vector<T> &nums, int left, int mid, int right) 
{ 
vector<T> tmp = nums; 
int start = left; // // 注意此处 start = left，不是 0 
int i = start, j = mid + 1; 
// 都是 <= 
while (i <= mid && j <= right) 
nums[start++] = tmp[i] < tmp[j] ? tmp[i++] : tmp[j++]; 
while (i <= mid) 
nums[start++] = tmp[i++]; 
while (j <= right) 
nums[start++] = tmp[j++]; 
}``` 
## 参数 
| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
|:---------:|:---------:|:---------:|:------:|:---:| 
| $O(nlog(n))$ | $O(nlog(n))$ | $O(nlog(n))$ | $O(n)$ | 稳定 | 
# 6. 快速排序 
> 思路：在数组中选择一个元素作为基准 
> 小于基准元素移到基准左边，反之移到基准右边（分区操作） 
> 此时基准元素所在位置就是排序完成后，基准元素的最终位置 
> 对基准元素的左右两个子集重复一二步，直到子集中剩余一个元素为止```cpp 
template<typename T> 
void quickSort(vector<T>& nums, int left, int right) 
{ 
	if (left < right) 
	{ 
		int pivot = quickSortHelper(nums, left, right); 
		quickSort(nums, left, pivot - 1); 
		quickSort(nums, pivot + 1, right); 
	} 
} 
template<typename T> 
int quickSortHelper(vector<T>&nums, int left, int right) 
{ 
	int pivot = nums[left]; 
	while (left < right) 
	{ 
		// pivot 取 left，则先从右边开始 -- 
		// 都是交换 left 与 right，pivot 只是起到一个记录的作用 
		while (left < right&&pivot <= nums[right]) right--; 
		nums[left] = nums[right]; 
		while (left < right&&nums[left] <= pivot) left++; 
		nums[right] = nums[left]; 
	} 
	nums[left] = pivot; 
	return left; 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(nlog(n))$ | $O(n^2)$ | $O(nlog(n))$ | $O(nlogn)$ | 不稳定 |# 7. 堆排序利用堆此种数据结构设计的排序算法 
堆是一种特殊的树（完全二叉树 叶子结点只可能在最大的两层出现）> 特点：根节点下标为 0，若父节点下标为 i1. 其左孩子下标为 2*i+1 
2. 右孩子为 2*i+2 
3. 第一个非叶子节点为 arr.size()/2-1- 小顶堆：每个节点的值都 >= 其子节点的值 => 堆排序的升序排序 
- 大顶堆：每个节点的值都 <= 其子节点的值 => 堆排序的降序排序 
- 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 
- 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]## 思想利用大(小)顶堆记录最大(小)关键词的特性1. 将数组构建成大顶堆，此堆为初始的无序区(堆顶确定) 
2. 将堆顶元素R[0]与最后一个元素R[n-1]交换得到无序区[0,n-2]与有序区[n-1] 
3. 调整无序区为新堆，重复2，3 
4. 无序区不断减少，有序区逐渐增加，当有序区间元素个数为 n-1 时完成```cpp 
template <typename T> 
void heapSort(vector<T> &nums) 
{ 
int n = nums.size(); 
//1. 构建一个最大堆 
// 从最后一个非叶子节点开始 
for (int i = n / 2 - 1; i >= 0; --i) 
{ 
heapSortHelperMin(nums, i, n); 
//heapSortHelperMax(nums, i, n); 
} 
//2. 将堆顶（最大值）与末位交换，再重新调整最大堆 
for (int i = n - 1; i > 0; --i) 
{ 
swap(nums[0], nums[i]); 
// 构造堆时，遍历每个非叶子节点已经排好序 
// 当交换元素时，只会影响最顶端的顺序，最低端是有序区 
// 因为堆是整体有序的，因此只需要管理受影响的最顶端，有问题可以递归处理后面受影响的堆 
heapSortHelperMin(nums, 0, i); 
//heapSortHelperMax(nums, 0, i); 
} 
}// 调整堆，不是构造堆 
template <typename T> 
void heapSortHelperMax(vector<T> &nums, int father, int length) 
{ 
int maxIndex = father; 
// 如有左子树，同时左子树大于父节点，则最大指针指向左子树 
if (father * 2 + 1 < length && nums[father * 2 + 1] > nums[maxIndex]) 
maxIndex = 2 * father + 1; 
// 如有右子树，同时右子树大于父节点和左子树，则最大指针指向右子树 
if (father * 2 + 2 < length && nums[father * 2 + 2] > nums[maxIndex]) 
maxIndex = 2 * father + 2; 
// 父节点不是最大值，则将父节点与最大值交换，同时递归调整 
if (maxIndex != father) 
{ 
swap(nums[maxIndex], nums[father]); 
heapSortHelperMax(nums, maxIndex, length); 
} 
}template <typename T> 
void heapSortHelperMin(vector<T> &nums, int father, int length) 
{ 
int minIndex = father; 
if (father * 2 + 1 < length && nums[father * 2 + 1] < nums[minIndex]) 
minIndex = 2 * father + 1; 
if (father * 2 + 2 < length && nums[father * 2 + 2] < nums[minIndex]) 
minIndex = 2 * father + 2; 
if (minIndex != father) 
{ 
swap(nums[minIndex], nums[father]); 
heapSortHelperMin(nums, minIndex, length); 
} 
} 
```## 构造堆的其它方法使用 STL 的优先队列，`priority_queue`，需要头文件<queue> 
底层就是一个堆结构，通过 top() 来访问队首元素 
`priority_queue< type, container, function >` 
三个参数，后面两个可以省略，第一个不可以。其中：1. **type**数据类型； 
2. **container**实现优先队列的底层容器； 
3. **function**元素之间的比较方式； 
container，要求必须是数组形式实现的容器，例如vector、deque，不能是list在STL中，默认情况下（不加后面两个参数）是以vector为容器，以 operator< 为比较方式，所以在只使用第一个参数时，优先队列默认是一个最大堆，每次输出的堆顶元素是此时堆中的最大元素。```cpp 
// 默认为大顶堆 
priority_queue<int> big_heap; 
//另一种构建大顶堆的方法 
priority_queue<int,vector<int>,less<int> > big_heap2; 
//构造一个空的优先队列,此优先队列是一个小顶堆 
priority_queue<int,vector<int>,greater<int> > small_heap; 
```## 优先队列堆排序```cpp 
// 利用优先队列实现 
template <typename T> 
// 调整遍历顺序或大小堆，即可逆转排序 
void heapSort(vector<T> &nums) 
{ 
int n = nums.size(); 
//1. 构建一个最大堆 
priority_queue<T, vector<T>> bigHeap; 
priority_queue<T, vector<T>, less<T>> smallHeap; 
for (auto x : nums) 
bigHeap.push(x);//2. 将堆顶（最大值）与末位交换，再重新调整最大堆 
for (int i = 0; i < n; ++i) 
{ 
nums[i] = bigHeap.top(); 
bigHeap.pop(); 
} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(nlog(n))$ | $O(nlog(n))$ | $O(nlog(n))$ | $O(1)$ | 不稳定 |# 8. 计数排序> 思路：将输入的数据值转化为键存储在额外开辟的数组空间中 
> 要求输入的数据：必须在***确定范围***内的***整数***- 找出待排序的数组中最大和最小的元素 
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项 
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加） 
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1```cpp 
void countSort(vector<int>& nums) 
{ 
	int n = nums.size(); 
	int minVal = nums[0], maxVal = nums[0]; 
	for (int i = 0; i < n; ++i) 
	{ 
		minVal = min(minVal , nums[i]); 
		maxVal = max(maxVal, nums[i]); 
	} 
	vector<int> bucket(maxVal - minVal + 1, 0); 
	int offset = minVal - 0;	// 将数据存入 bucket 
	for (auto x : nums) 
		bucket[x - offset]++; 
	int j = 0; 
	for (int i = 0; i < bucket.size(); ++i) 
	{ 
		// 对应数值是 i+offset 
		// 每个数值次数是 bucket[i] 
		// 外部 -- 
		while (bucket[i]--) 
			nums[j++] = i + offset; 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | $O(n+k)$ | 稳定 |# 9. 桶排序桶排序是计数排序的升级版，利用函数的映射关系，把计数排序中的多个坑位整合成为一个桶## 思路(1) 设置一个定量的数组当作空桶； 
(2) 遍历输入数据，并且把数据一个一个放到对应的桶里去； 
(3) 对每个不是空的桶进行排序； 
(4) 从不是空的桶里把排好序的数据拼接起来。算法效率在于映射函数的确定。为了更加高效，需要：1. 在外部空间充足的情况下，尽可能**增大桶的数量** 
2. 使用的映射函数能够将输入的 N 个数据**均匀地分配到 K 个桶中**最快：输入数据均匀分配到每个桶中 
最慢：输入数据被分配到同一个桶中 
当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间 O(n)```cpp 
// 桶排序 
// 桶的大小 
void bucketSort(vector<int>& nums, int bucketSize) 
{ 
	int n = nums.size(); 
	if (n < 2) return; 
	int minVal = nums[0], maxVal = nums[0]; 
	for (int i = 1; i < n; ++i) 
	{ 
		minVal = min(nums[i], minVal); 
		maxVal = max(nums[i], maxVal); 
	}	// 桶的数量，当 bucketSize 为 1 时，退货为计数排序 
	int bucketCount = (maxVal - minVal) / bucketSize + 1; 
	int offset = minVal - 0; 
	vector<vector<int>> bucketVec(bucketCount, vector<int>());	// 元素入桶 
	for (int i = 0; i < n; ++i) 
	{ 
		// 重点！！！ 
		bucketVec[(nums[i] - offset) / bucketSize].push_back(nums[i]); 
	} 
	// clear 之后，不能直接用 []，因为并没有初始化，需要用 push_back 
	nums.clear(); 
	for (int i = 0; i < bucketCount; ++i) 
	{ 
		// 内部可以选择方法对桶内元素进行排序 
		// 空桶跳过，提高效率 
		if (bucketVec[i].size() != 0) 
		{ 
			sort(bucketVec[i].begin(), bucketVec[i].end()); 
			for (auto x : bucketVec[i]) 
				nums.push_back(x); 
				//nums[j++] = x; 
		} 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(n+k)$ | $O(n^2)$ | $O(n)$ | $O(n+k)$ | 稳定 |# 10. 基数排序一种非比较型整数排序算法，原理是将整数按位数切割成不同的数字，按每个位数分别比较 
因为整数可以表达字符串(名字或日期)和特定模式的浮点数，因此基数排序也可用于字符串### 计数排序，桶排序，基数排序区别三者都使用了桶的概念，但是1. 计数排序：每个桶只存储单一键值 
2. 桶排序：每个桶存储一定范围的数值 
3. 基数排序：根据键值的每位数字来分配桶基数排序的方式可以采用 LSD（Least significant digital） 或 MSD（Most significant digital）- LSD: 由键值的 最右边（最小位） 开始, 适用于位数少的序列，可采用桶排序 
- MSD: 由键值的 最左边（最大位） 开始, 适用于位数多的序列，可采用计数排序> 在进行某个特定位数比较时，要用稳定排序，将上次排序成果保留。例如十位数的排序过程能保留个位数的排序成果，百位数的排序过程能保留十位数的排序成果。 
> 基数排序对有负数和0的数列难以进行排序![radixSort](media/16228637990486/radixSort.gif)![](media/16228637990486/16238487090536.jpg)```cpp 
void radixSort(vector<int>& nums) 
{ 
	int maxVal = 0; 
	for (int x : nums) 
		if (x > maxVal) maxVal = x;	// d 表示 1，10，100 等，序列最大值长度为3，d = 100 
	int d = 10; 
	while (maxVal / 10) 
	{ 
		d *= 10; 
		maxVal /= 10; 
	}	// 从个位开始 
	int index = 1; 
	while (index<d) 
	{ 
		// 从0到9总共10个桶 
		// 每个桶最多有 nums.size()个元素，初始化大小后才能使用 [] 
		// 如何要使用 push_back() 就不要初始化大小，因为再 push_back() 则会将元素保存在初始化大小的元素之后！！！ 
		// 同时放于此处可以不用清空数组，当更换数位时 
		vector<vector<int>> bucketVec(10, vector<int>()); 
		//将序列的每个数字放在相应的桶里 
		for (int x : nums) 
		{ 
			// 当前位上的数值 
			int digit = (x / index) % 10; 
			bucketVec[digit].push_back(x); 
		}		// 重写入数组时遍历秩，当下一轮位数变化时，k 能自己重置为 0 
		int k = 0; 
		// 将上一次排序结果覆盖到原数组 
		for (int i = 0; i < 10; i++) 
		{ 
			// 若桶内有元素，依次取出放到原数组中 
			if (bucketVec[i].size()!=0) 
			{ 
				for (int j = 0; j < bucketVec[i].size(); ++j) 
					nums[k++] = bucketVec[i][j]; 
			} 
		} 
		// 将位数前移 
		index *= 10; 
	} 
} 
```## 参数| 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | 
| :----------------: | :----------------: | :----------------: | :----------: | :------: | 
| $O(n*k)$ | $O(n*k)$ | $O(n*k)$ | $O(n+k)$ | 稳定 |

排序算法总结 C++

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

2-31. 表示数值的字符串

Chevereto 图床安装及 uPic 图床配置教程

如何保持与 fork 仓库同步

2-24机器人的运动范围

2-34. 链表中环的入口节点

typehcho 使用

优先队列及 sort 函数算子

mweb+ typecho 一键发布博客

随想

1-14. 不修改数组找出重复的数字

排序算法总结 C++

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

排序算法总结 C++

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款