序言：swap函数的源代码
template<class T>
void swap(T &a,T &b){
T temp = a;
a = b;
b =temp;
}
算法：
1、比较相邻的元素，如果前一个大于后一个，则交换这两个数。
2、比较每一对相邻元素，从开始的第一对到最后一对
例： 3 5 2 4 1 6 -> 3 5 2 4 1 6 -> 3 2 5 4 1 6 -> 3 2 4 5 1 6 -> 3 2 4 1 5 6 -> 3 2 4 1 5 6
平均时间复杂度： O(N²)
空间复杂度： O(1)
稳定
冒泡次数 冒泡结果 交换轮数 检查轮数
原始数据 4 5 6 3 2 1 0
第1次冒泡 4 5 3 2 1 6 3 5
第2次冒泡 4 3 2 1 5 6 3 4
第3次冒泡 3 2 1 4 5 6 3 3
第4次冒泡 2 1 3 4 5 6 2 2
第5次冒泡 1 2 3 4 5 6 1 1
代码实现：
//冒泡排序
void bubbleSort(vector<int>&nums) {
int n = nums.size();
if (n <= 1) return;
bool flag = false;
//下标从0开始 但是从下标1开始交换
for (int i = 1; i < n ; i++) {
//1 2 3 4 5 ... n-1 有n-1个数可与下一个数交换
//i= 1 j= 1,2,...n-1 i之前的数不需要交换，i之后的交换
for (int j = 1; j < n - i + 1; j++) {
if (nums[j] < nums[j - 1]) {
swap(nums[j], nums[j - 1]);
flag = true; //表示有数据交换
}
}
if (!flag) break; //没有数据交集，提前退出
}
}
算法：
每次从未排序的区间区间中找到最小的元素，将其放到已排序区间的末尾
平均时间复杂度： O(N²)
空间复杂度： O(1)
不稳定
//选择排序
void selectSort(vector<int>&nums) {
int n = nums.size();
if (n <= 1) return;
//快慢指针
for (int i = 0; i < n - 1; i++) {
int tmp = i;
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[tmp]) tmp = j; //找出最小数的下标
}
swap(nums[tmp], nums[i]);
}
}
算法：
从数组第一个元素开始（初始已排序区间只有一个元素），遍历未排序的每一个元素，插入到已排序的区间保证数据有序。
平均时间复杂度： O(N²)
空间复杂度： O(1)
稳定
代码实现：
//插入排序
void insertSort(vector<int>&nums) {
int n = nums.size();
if (n <= 1) return;
//双指针 对已排序的数进行插入
for (int i = 0; i < n; i++) {
for (int j = i; j > 0; j--) {
if (nums[j] < nums[j - 1]) {
swap(nums[j], nums[j - 1]);
}
}
}
}
算法：
将比较的全部元素取越来越小的步长，分几个区域排序
平均时间复杂度： O(Nlog²N)
空间复杂度： O(1)
不稳定
//希尔排序
void shellSort(vector<int>&nums) {
int n = nums.size();
if (n <= 1) return;
//取步长
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
for (int j = i; j - gap >= 0; j -= gap) {
if (nums[j] < nums[j - gap]) {
swap(nums[j - gap], nums[j]);
}
}
}
}
}
算法：
将全部元素分半分组，每一组再分半分组，递归下去，两两比较，再逐步合并到临时数组，最后全部排序
平均时间复杂度： O(NlogN)
空间复杂度： O(N)
稳定
//归并排序
void merge(vector<int>&nums, int left, int mid, int right) {
int n = nums.size();
//临时数组 必须规定容量n
vector<int>temp(n);
int i = left, j = mid + 1;//被分割的两个数组的起点下标
int k = 0;//临时数组的下标
while(i <= mid && j <= right) {
if (nums[i] < nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
//将剩余数据全部放入
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
//将临时数组中元素全部拷贝回原数组
for (int m = 0; m < k; m++) nums[left + m] = temp[m];
}
void mergeSort(vector<int>&nums,int left,int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
//分治 递归
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);//合并
}
算法：
确定一个枢纽pivot，将所有其他元素跟pivot比较，较小的在前，较大的在后
平均时间复杂度： O(NlogN)
空间复杂度： O(logN)
不稳定
//快速排序
void quickSort(vector<int>&nums, int left, int right) {
if (left >= right) return;
//双指针
int i = left, j = right;
int pivot = nums[i];
while (i < j) {
//右指针 从右往左 小于pivot的值放左边
while (i < j&&nums[j] >= pivot) j--;
nums[i] = nums[j];
//左指针 从左往右 大于pivot的值放右边
while (i < j&&nums[i] <= pivot) i++;
nums[j] = nums[i];
}
//更新
nums[i] = pivot;
//以nums[i]为界 分治 递归
quickSort(nums, left, i - 1);
quickSort(nums, i + 1, right);
}
算法：
利用大根堆或小根堆的特性
ps:一般用到堆排序的算法，只需要priority_queue实现即可，这里不讨论堆排序本身实现的算法，讨论一下利用堆的特性实现排序的方法。
平均时间复杂度： O(NlogN)
空间复杂度： O(1)
不稳定
定义：priority_queue
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大顶堆
1.基本类型
//对于基础类型 默认是大顶堆
priority_queue<int> a;
//等同于 priority_queue, less > a;
priority_queue<int, vector<int>, greater<int> > c; //这样就是小顶堆
2.pair的比较，先比较第一个元素，第一个相等比较第二个
priority_queue<pair<int, int> > a;
3.自定义类型
//方法1
struct tmp1 //运算符重载<
{
int x;
tmp1(int a) {x = a;}
bool operator<(const tmp1& a) const
{
return x < a.x; //大顶堆
}
};
//方法2
struct tmp2 //重写仿函数
{
bool operator() (tmp1 a, tmp1 b)
{
return a.x < b.x; //大顶堆
}
};
priority_queue<tmp1> d;
priority_queue<tmp1, vector<tmp1>, tmp2> f;
算法：
用待排序的数作为计数组的下标，统计每个数字的个数
平均时间复杂度： O(N²)
空间复杂度： O(1)
稳定
//计数排序
void countSort(vector<int>&nums) {
int n = nums.size();
if (n <= 1) return;
int maxValue = nums[0];
//找出最大值
for (int i = 1; i < n; i++) {
maxValue = max(maxValue, nums[i]);
}
//哈希表
vector<int>tmp1(n + 1);
for (int i = 0; i < n; i++) {
tmp1[nums[i]]++;//统计每个数字的个数
}
//将所有数字分为 1~maxValue
for (int i = 1; i <= maxValue; i++) {
tmp1[i] += tmp1[i - 1];
}
vector<int>tmp2(n + 1);
for (int i = n - 1; i >= 0; i--) {
int idx = tmp1[nums[i]] - 1;
tmp2[idx] = nums[i];
tmp1[nums[i]]--;
}
for (int i = 0; i < n; i++) {
nums[i] = tmp2[i];
}
}
算法：
将数组分到有限数量的桶里，每个桶再分别排序(个人理解，找出最大或者最小元素后，以序号的方式放桶，主要存储相同元素，最后大小输出直接按照序号输出)
平均时间复杂度： O(N+K)
空间复杂度： O(N+K)
稳定
//桶排序
void bucketSort(vector<int>&nums) {
int len = nums.size();
if (len <= 1) return;
int low = *min_element(nums.begin(), nums.end());//最小元素
int high = *max_element(nums.begin(), nums.end());//最大元素
int n = high - low + 1;
vector<int>buckets(n);//放置的桶
vector<int>ans;
for (auto x : nums) buckets[x - low]++;//相同的数放一个桶
//按照序号输出
for (int i = 0; i < n; i++) {
//将相同的数输出
for (int j = 0; j < buckets[i]; j++) {
ans.push_back(i + low);
}
}
for (int i = 0; i < ans.size(); i++) {
nums[i] = ans[i];
}
}
算法：
对排序的数据有要求，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果a的高位>b的高位，则a>b。此外，每一位的数据范围不能太大，需要一定线性，基数排序相当于循环多次实现多次桶排序。
ps:由于对数据有要求，加上时间空间复杂度并没有优于桶排序，这里不作深入研究。
平均时间复杂度： O(N×K)
空间复杂度： O(N+K)
稳定
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）