做装修的推广网站有那种,wordpress logo 编辑器,网站后期维护和管理怎么做,做网站怎样租用虚拟空间本文将以「 通俗易懂」的方式来描述排序的基本实现。 #x1f9d1;#x1f4bb;阅读本文前#xff0c;需要一点点编程基础和一点点数据结构知识 本文的所有代码以cpp实现 文章目录
排序的定义
插入排序 ⭐
#x1f9d0;算法描述
#x1f496;具体实现
#x1f… 本文将以「 通俗易懂」的方式来描述排序的基本实现。 阅读本文前需要一点点编程基础和一点点数据结构知识 本文的所有代码以cpp实现 文章目录
排序的定义
插入排序 ⭐
算法描述
具体实现
代码实现
☹️性能分析
题目练习
希尔排序⭐⭐⭐⭐
算法描述
具体实现
代码实现
性能分析
题目练习
冒泡排序⭐
算法描述
具体实现
代码实现
☹️性能分析
题目练习
快速排序⭐⭐⭐⭐
算法描述
具体实现
代码实现
题目练习
性能分析
选择排序⭐
算法描述
具体实现
代码实现
☹️性能分析
题目练习
堆排序⭐⭐⭐⭐⭐
算法描述
具体实现
代码实现
性能分析
题目练习
归并排序⭐⭐⭐
算法描述
具体实现
代码实现
性能分析
题目练习
桶排序⭐⭐⭐
算法描述
具体实现
代码实现
性能分析
题目练习
计数排序⭐⭐
算法描述
具体实现
代码实现
性能分析
题目练习 基数排序⭐⭐⭐⭐
算法描述
具体实现
代码实现
性能分析
题目练习
总结 排序的定义 排序。顾名思义就是将列表中的元素变为有序的过程。 算法稳定性。若待排序表中有两个元素R1和R2其对应关键字相同(key1 key2)且R1在R2前面。排序后R1仍在R2前面称该算法是稳定的。 接下来简单介绍基本排序算法 ⭐越多难度越高。 插入排序 ⭐
算法描述 插入排序Insertion Sort一般也被称为直接插入排序是一种简单直观的排序算法。 对于前面 i - 1 个数已经有序的情况下将第 i 个插入到合适位置。 这个过程类似于平时打扑克牌时摸牌的操作右手摸牌根据牌面大小放到左手中正确的位置。 具体实现
我们以[6, 2, 3, 5, 1, 4]为例 演示一下插入排序算法的整个步骤。 将第一个元素6视为已排序序列将后面元素依次进行排序。
1当前的数2 当前有序列表6
2 6 : 2 放在 6 之前
2当前的数3 当前有序列表2 6
3 6
3 2 : 3 放在 2 之后
3当前的数5 当前有序列表2 3 6
5 3
5 6 : 2 放在 6 之前
4当前的数1 当前有序列表2 3 5 6
1 61 51 31 2 1 放在 2 之前
5当前的数4 当前有序列表1 2 3 5 6
4 64 5
4 34 放在 3 之后
至此排序结束。总共进行 n - 1 次循环。排序结果为 1 2 3 4 5 6 代码实现
#include iostream
using namespace std;void InsertSort(int a[],int n){int i,j,tmp; //定义循环变量和临时变量for(i 1; i n; i){ //使用双层循环外层循环枚举除了第一个元素之外的所有元素tmp a[i]; //对于枚举到的元素储存到tmp中for(j i - 1; j 0; --j){ //内层循环遍历当前元素前面的有序表进行待插入位置查找if(tmp a[j]) a[j 1] a[j]; //若待插入元素当前元素a[j]则将a[j]向后移动else break;}a[j 1] tmp; //最后将tmp插入到合适位置}
}
void Print(int nums[],int n){ //打印列表元素for(int i 0; i n; i){printf(%d ,nums[i]);}puts( );
}
int main(){int nums[] {6,2,3,5,1,4}; //自定义列表int n sizeof(nums) / sizeof(nums[0]); //获取列表长度Print(nums,n);InsertSort(nums,n); //进行插入排序Print(nums,n);return 0;
}
☹️性能分析
时间效率O(n²)
空间效率原地排序O(1)
稳定性因为每次插入元素时总是从后往前比较再移动所以不会出现相同位置发生变化的情况即直接插入排序是一个稳定的算法。
适用性 顺序存储链式存储。 这里可以将直接插入排序优化成折半插入排序。简而言之就是在查找合适位置时进行二分查找这样可以优化一些时间复杂度但它只适用于顺序存储。以下是折半插入排序的实现。
void BinnaryInsertSort(int a[],int n){int i,j,low,high,tmp;for(int i 1; i n; i){tmp a[i];low 0;high i; //定义二分查找的区间 while(low high){ //二分查找大于等于tmp中最小的元素 int mid (low high) 1;if(a[mid] tmp) high mid;else low mid 1;}for(j i - 1; j low; --j) //找到合适位置low统一后移元素空出插入位置 a[j 1] a[j];a[j 1] tmp;}
} 题目练习
【题目描述】 88. 合并两个有序数组 - 力扣LeetCode 【解题思路】 将nums2数组视为待排序数组nums1视为已排序数组。遍历nums2数组将每个元素依次插入到nums1中copy插入排序的代码改一下参数即可。 【AC代码】
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int i,j,tmp;for(i 0; i n; i){tmp nums2[i]; for(j m i - 1; j 0; --j){if(tmp nums1[j])nums1[j 1] nums1[j];else break;}nums1[j 1] tmp;}}
};
【题目描述】147. 对链表进行插入排序 - 力扣LeetCode 【解题思路】 新建一个链表遍历原来的链表对每个结点在有序链表中找合适位置然后进行插入操作。做链表题必画图不理解的小伙伴建议画个图。 【AC代码】
class Solution {
public:ListNode* insertionSortList(ListNode* head) {if (!head || !head-next) { //空链表返回return head;}ListNode* dummy new ListNode(-1); //开辟一个虚拟头结点dummy-next new ListNode(head-val); //将第一个元素视为已排序元素ListNode* curr head-next; //遍历待排序元素while (curr ! nullptr) {ListNode *prev dummy, *tmp curr-next; //双指针方便插入while (prev-next ! nullptr prev-next-val curr-val) { //prev-next等同于j查找合适位置进行插入prev prev-next;}curr-next prev-next; //将当前元素插入到合适位置prev-next curr; curr tmp; //循环遍历下一个结点}return dummy-next;}
};希尔排序⭐⭐⭐⭐
算法描述 希尔排序(Shells Sort)也被称为递减增量排序算法(Diminishing Increment Sort)是插入排序的一种更高效的改进排序算法。 先选定一个间隔把待排序元素分成多个组所有间隔距离的分在同一组并在组内进行插入排序。然后减小间隔重复上述分组和排序的工作。当到达间隔为1时所有元素在统一组内排好序。 具体实现
我们以[9,1,2,5,7,4,8,6,3,5 ]为例演示一下希尔排序算法的整个步骤。 1选择一个增量序列gap n / 2 。图中红色线画中的为第一组。定义一个 i 变量指向这一组的第二个数据定义一个 j 变量指向 i - gap 的位置。 对组内进行插入排序这里不再赘述具体实现在上文。排序结果如下
2 gap 为 2数据此时分为了两组。 排序结果如下 3gap 1. 排序结果如下 代码实现
#include iostream
using namespace std;void ShellSort(int a[],int n){int gap,i,j,tmp;for(gap n/2; gap 0; gap / 2){ //增量变化无统一规定 for(i gap; i n; i){ //每组内进行插入排序 tmp a[i];for(j i - gap; j 0; j - gap){ //查找合适位置 if(tmp a[j]){a[j gap] a[j]; //将元素后移 }else break; }a[j gap] tmp; //插入合适位置 }}
}
void Print(int nums[],int n){ //打印数组 for(int i 0;i n; i){printf(%d ,nums[i]);}puts( );
}
int main(){int nums[] {9,1,2,5,7,4,8,6,3,5}; //自定义数组 int n sizeof(nums)/sizeof(nums[0]); //获取数组长度 Print(nums,n);ShellSort(nums,n); //进行希尔排序 Print(nums,n);return 0;
}
性能分析
时间效率一般O(n^1.3)最坏O(n²)
空间效率原地排序O(1)
稳定性当相同关键字的记录被划分到不同的子表时可能会改变他们之间的相对次序因此希尔排序是一个不稳定的算法。
适用性 仅适用于顺序存储的线性表。
题目练习
【题目描述】506. 相对名次 - 力扣LeetCode 【解题思路】 对数组进行希尔排序成一个排名数组。遍历原数组在排名数组中二分查找元素的下标。然后按照要求完成即可 这里用二分查找可以将复杂度将到O(long₂ⁿ)乘上外层循环O(n)加上希尔排序复杂度O(nlong₂ⁿ)总的时间复杂度为O(long₂ⁿ)。 【AC代码】
class Solution {
public:vectorstring findRelativeRanks(vectorint score) {vectorint Rank ShellSort(score); //对数组进行希尔排序vectorstring ans; for(int x : score){int i binnaryFind(x,Rank); //二分查找下标if(i 1 1) ans.push_back(Gold Medal);else if(i 1 2) ans.push_back(Silver Medal);else if(i 1 3) ans.push_back(Bronze Medal);else ans.push_back(to_string(i 1));}return ans;}vectorint ShellSort(vectorint a){int n a.size();int gap,i,j,tmp;for(gap n/2; gap 0; gap / 2){ for(i gap; i n; i){ //每组内进行插入排序 tmp a[i];for(j i - gap; j 0; j - gap){ //查找合适位置 if(tmp a[j]){a[j gap] a[j]; //将元素后移 }else break; }a[j gap] tmp; //插入合适位置 }}return a;}int binnaryFind(int x,vectorint Rank){int left 0,right Rank.size() - 1;while(left right){int mid (left right) 1;if(Rank[mid] x) left mid 1;else right mid;}return left;}
}; 冒泡排序⭐
算法描述 冒泡排序Bubble Sort又称为泡式排序是一种简单的排序算法。 通过比较相邻元素使较大的元素不断往后冒从而实现排序的过程。 这个算法名字的由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端升序或降序排列就像水中的气泡会冒起来一样。 具体实现
我们以[5,8,6,3,9,2,1,7]为例演示一下冒泡排序算法的整个步骤。
1比较相邻的元素。如果第一个比第二个大就交换它们两个。
2对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。
3针对所有的元素重复以上的步骤除了最后一个。
4持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。 代码实现
#include iostream
using namespace std;void BubbleSort(int a[],int n){for(int i n - 1; i 0; --i){ //外层循环进行 n - 1 趟排序 bool flag false; //表示本趟冒泡是否发生交换 for(int j 0; j i; j){ //每一趟冒泡过程 if(a[j 1] a[j]) swap(a[j 1],a[j]);flag true;}if(flag false) return ; //本趟遍历没有发生交换说明表已经有序 }
}
void Print(int nums[],int n){ //打印数组 for(int i 0;i n; i){coutnums[i] ;}puts( );
}
int main(){int nums[] {5,8,6,3,9,2,1,7}; //自定义数组 int n sizeof(nums)/sizeof(nums[0]); //获取数组大小 Print(nums,n);BubbleSort(nums,n); //进行冒泡排序 Print(nums,n);return 0;
}
☹️性能分析
时间效率O(n²)。加入flag后当初始序列有序时显然第一冒泡后flag为false本趟没有元素交换从而直接跳出循环比较n-1次移动次数为0从而最好的时间复杂度为O(n)。
空间效率原地排序O(1)
稳定性稳定
适用性 顺序存储链式存储的线性表。 题目练习
【题目描述】75. 颜色分类 - 力扣LeetCode 【解题思路】 直接copy冒泡排序。 【AC代码】
class Solution {
public:void sortColors(vectorint nums) {int n nums.size();for(int i n - 1; i 0; --i){ bool flag false; for(int j 0; j i; j){ if(nums[j 1] nums[j]) swap(nums[j 1],nums[j]);flag true;}if(flag false) return ; }}
}; 快速排序⭐⭐⭐⭐
算法描述 快速排序 Quick Sort是利用了「 分而治之 」的思想进行递归计算的排序算法效率在众多排序算法中的佼佼者。 快速排序是冒泡排序的改进版。随机找到一个位置将比它小的数都放到它 左边 比它大的数都放到它 右边然后分别 递归 求解 左边 和 右边 使得两边分别有序。 C 标准库的 std::sort() 函数通常使用快速排序作为默认实现。 具体实现
快速排序实现有多种以下是我常用方式实现。
我们以 [4, 1, 6, 2 ,9, 3]为例演示一下快速排序算法的整个步骤。
1第一遍遍历
在 [4,1,6,2,9,3] 中选择元素 4 作为基准数检查是否 1 4 (基准数)检查是否 6 4 (基准数)检查是否 2 4 (基准数)2 4 (基准数) 是为真将指数2和 存储指数 6 进行交换检查是否 9 4 (基准数)检查是否 3 4 (基准数)3 4 (基准数) 为真将指数3和存储指数6 进行交换最后将基准数 4 和 最右边绿色的数 3 小于等于基准数的最大数进行交换此时基准数4左边全部小于4右边大于4 此时数组顺序为[312496]。
2下一步
递归进行左边排序选择元素 3 作为基准数检查是否 1 3 (基准数)检查是否 2 3 (基准数)将基准数 3和存储指数值 2进行交换现在基准数已经在排序过后的位置进行拆分 [2,1] 选择 2 作为轴心点检查是否 1 2 (基准数)左边遍历完成将基准数2和存储指数1 进行交换 3递归进行右边排序这里不再赘述。 代码实现
#include iostream
using namespace std;int Partition(int a[],int start,int end){ //在start与end区间寻找基准数的下标 int pivot start; //定义第一个元素为基准数int j start 1; //j为大于基准数的数的左边界 for(int i start 1; i end 1; i){ //遍历区间元素 if(a[i] a[pivot]){swap(a[i],a[j]); //保证j以前的数都是小于等于基准数 j;}}swap(a[j - 1],a[pivot]); //将基准数与小于等于基准数的最大数进行交换也就是那个最右边绿色的数 pivot j - 1; //更新基准数下标 return pivot;
}
void QuickSort(int a[],int start,int end){if(start end) return ;int pivot Partition(a,start,end); //获取基准数QuickSort(a,start,pivot - 1); //递归排序左区间 QuickSort(a,pivot 1,end); //递归排序右区间
}
void Print(int nums[],int n){ //打印数组for(int i 0; i n; i){coutnums[i] ;}puts( );
}
int main(){int nums[] {4,1,6,2,9,3};int n sizeof(nums)/sizeof(nums[0]); //获取数组长度 Print(nums,n);QuickSort(nums,0,n - 1); //进行快速排序 Print(nums,n);return 0;
}
题目练习
【题目描述】 217. 存在重复元素 - 力扣LeetCode 【解题思路】 对数组进行排序然后对数组元素进行两两比较若相同说明存在否则不存在相同元素。 【AC代码】
直接调用c封装好的sort函数
class Solution {
public:bool containsDuplicate(vectorint nums) {sort(nums.begin(),nums.end()); //排序数组for(int i 1; i nums.size(); i){if(nums[i] nums[i - 1])return true;}return false;}
};
性能分析
时间效率一般为O(nlong₂ⁿ)。快排整体的综合性能和使用场景都是比较好的所以叫快速排序。
空间效率栈的深度O(n)
稳定性在划分算法中若右端关键字且均小于基准数的记录则在交换到左端区间后他们的相对位置会发生变化即快速排序是一种不稳定的排序算法。
适用性 仅适用于顺序存储的线性表。 快速排序 在众多排序算法中效率较高平均时间复杂度为O(nlong₂ⁿ。但当完全有序时最坏时间复杂度达 到最坏情况 O(n²)。 所以每次在选择基准数的时候我们可以尝试用随机的方式选取这就是 随机快速排序 。 想象一下在随机化版本的快速排序中随机化数据透视选择我们不会总是得到 01 和 n-1 这种非常差的分割。所以不会出现上文提到的问题。
随机快速排序只需要修改 Partition 函数使其随机选择基准元素即可。像这样 int idx start rand() % (end - start 1);// 生成随机下标swap(a[idx], a[end]); // 将随机选择的元素与末尾元素交换int pivot start; 选择排序⭐
算法描述 选择排序Selection sort是一种简单直观的排序算法。 第一次从待排序的数据元素种选出最小或最大的一个元素存放在排序序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素 的个数为零。 选择排序中的关键在于怎么找出一堆数据中最小或最大的。 具体实现
我们以[6, 2, 3, 5, 1, 4]为例演示一下选择排序算法的整个步骤。 第一次参与比较的数据6 2 3 5 1 4
1第一次循环在 2 3 5 1 4 中找出最小值1 。与最左边的值进行交换后1 2 3 5 6 4
2第二次循环在 2 3 5 6 4 中找出最小值2 。与最左边的值进行交换后1 2 3 5 6 4
3第三次循环在 3 5 6 4 中找出最小值3 。与最左边的值进行交换后1 2 3 5 6 4
4第四次循环在 5 6 4 中找出最小值4 。与最左边的值进行交换后1 2 3 4 6 5
5第五次循环在 6 5 中找出最小值5 。与最左边的值进行交换后1 2 3 4 5 6 代码实现
和冒泡排序相比选择排序比冒泡排序的效率高高在交换位置的次数上。选择排序的交换位置是有意义的循环 一次然后找出参加比较的这堆数据中最小的拿着这个最小的值和最前面的数据交换位置。
#include iostream
using namespace std;void SelectionSort(int a[],int n){for(int i 0;i n - 1; i){ //进行 n - 1 趟 int min i; //记录最小元素位置 for(int j i 1; j n; j){ //在剩余未排序元素中找最小 if(a[j] a[min]) min j; //将最小元素下标记录 } swap(a[i],a[min]); //与第一个元素交换 }
}
void Print(int a[],int n){ //打印数组 for(int i 0; i n; i){printf(%d ,a[i]);}puts();
}
int main(){int a[] {6,2,3,5,1,4}; int n sizeof(a)/sizeof(a[0]); //获取数组长度 Print(a,n);SelectionSort(a,n); //进行选择排序 Print(a,n);return 0;
}
☹️性能分析
时间效率O(n²)。
空间效率原地排序O(1)
稳定性在第 i 趟找到最小元素后和第 i 个元素交换可能会导致第 i 个元素与含有相同关键字的元素的相对位置发生改变。选择排序是一种不稳定的算法
适用性 顺序存储链式存储的线性表。 题目练习
【题目描述】611. 有效三角形的个数 - 力扣LeetCode 【解题思路】 组成三角形的条件是任意两边之和大于第三边。 将数组排序然后多维枚举将最大的一条边固定再枚举另外两条边并判断是否满足条件,满足条件计数器加1。 当然这个算法的时间复杂度达到O(n³)有兴趣的小伙伴可以进行二分查找降低复杂度。 【AC代码】
以下是c语言代码怕c会超时
void SelectionSort(int a[],int n){for(int i 0;i n - 1; i){ int min i; for(int j i 1; j n; j){ if(a[j] a[min]) min j; } int temp a[i];a[i] a[min];a[min] temp; }
}
int triangleNumber(int* nums, int numsSize) {SelectionSort(nums,numsSize); //对数组进行选择排序int ans 0;for(int k numsSize - 1; k 0; --k){int c nums[k];for(int i k - 1; i 0; --i){int a nums[i];for(int j i - 1; j 0; --j){int b nums[j];if(a b c) ans; //满足条件计数器加一else break; }}}return ans;
} 堆排序⭐⭐⭐⭐⭐
算法描述 堆排序Heap Sort 就是利用了堆的性质进行排序。 堆是一棵完全二叉树除了最底层其他层的节点都是满的最底层的节点都尽量靠左排列。)不理解完全二叉树的小伙伴可以去看我的数据结构树那块的内容数据结构--树 为方便理解算法这里简单介绍一下什么是堆
堆是一种特殊的树形数据结构通常用于实现优先队列。因为堆能够快速找到最大最小元素。堆通常是一个可以被看做是一棵树的数组对象。
堆的性质在一个小根堆Min Heap中对于每个父节点 i 的值都小于或等于其子节点的值。在一个大根堆Max Heap中对于每个父节点 i 的值都大于或等于其子节点的值。
堆可以通过数组下标从0开始来表示具体来说对于数组中的第 i 个元素
其父节点位于位置 floor((i-1)/2)其左子节点位于位置 (2*i 1)其右子节点位于位置 (2*i 2)
像这样 具体实现
我们以[2, 6, 3, 4,7]为例演示一下堆排序算法的整个步骤。
1构建初始大顶堆
定义一个数组实现的堆结构将原始数组的元素依次存入堆结构的数组中初始顺序不变。从数组的中间位置开始从右至左依次通过「下沉调整」将数组转换为一个大顶堆。 所谓下沉调整 如果当前节点为叶子节点或者没有子节点那么不需要进行调整堆的性质已经满足。 否则找到当前节点的较大大顶堆子节点。交换当前节点与其较大子节点的值。 继续向下检查被交换的子节点重复步骤 2直到当前节点满足堆序性质或成为叶子节点。 2交换元素调整堆
交换堆顶元素第 1个元素与末尾最后 1个元素的位置交换完成后堆的长度减 1。交换元素之后由于堆顶元素发生了改变需要从根节点开始对当前堆进行「下沉调整」使其保持堆的特性。 3重复交换和调整堆重复第 2 步直到堆的大小为 1 时此时大顶堆的数组已经完全有序 代码实现
#include iostream
using namespace std;void maxHeapify(int a[],int n,int i){ //维护大根堆 int largest i; //记录最大数的下标 int lson i * 2 1; //当前结点的左孩子 int rson i * 2 2; //当前结点的右孩子 //找三个节点中最大的if(lson n a[largest] a[lson])largest lson; if(rson n a[largest] a[rson])largest rson;if(largest ! i){ swap(a[largest],a[i]); //交换最大元素 maxHeapify(a,n,largest); //递归交换最大元素 } }
void HeapSort(int a[],int n){//初始化堆 父节点下标 (i - 1)/2 for(int i n / 2 - 1; i 0; --i) //数组最后下标从n-1开始maxHeapify(a,n,i);//排序for(int i n - 1; i 0; --i){swap(a[i],a[0]); //交换堆顶元素与堆的最后一个元素 maxHeapify(a,i,0); //继续维护剩余的元素 }
}
void Print(int a[],int n){ //打印数组 for(int i 0;i n; i){printf(%d ,a[i]);}puts();
}
int main(){int a[] {5,2,7,3,6,1,4};int n sizeof(a)/sizeof(a[0]); //获取数组长度 Print(a,n);HeapSort(a,n); //进行堆排序 Print(a,n);return 0;
}
性能分析
时间效率O(nlong₂ⁿ)。
空间效率原地排O(1)
稳定性在进行「下沉调整」时相等元素的相对位置可能会发生变化。因此堆排序是一种 不稳定排序算法。
适用性仅适用于顺序存储的线性表 题目练习
【题目描述】LCR 159. 库存管理 III - 力扣LeetCode 【解题思路】 对数组进行排序返回前cnt个数即可。 【AC代码】
建议自己手写一遍加深对算法的印象
class Solution {
public:vectorint inventoryManagement(vectorint stock, int cnt) {HeapSort(stock);vectorint ans;for(int i 0; i cnt; i) ans.push_back(stock[i]);return ans;}void HeapSort(vectorint a){int n a.size();for(int i n / 2 - 1; i 0; --i) maxHeapify(a,n,i);for(int i n - 1; i 0; --i){swap(a[i],a[0]); maxHeapify(a,i,0); } } void maxHeapify(vectorint a,int n,int i){ int largest i; int lson i * 2 1; int rson i * 2 2; if(lson n a[largest] a[lson])largest lson; if(rson n a[largest] a[rson])largest rson;if(largest ! i){ swap(a[largest],a[i]); maxHeapify(a,n,largest); } }
}; 归并排序⭐⭐⭐
算法描述 归并排序Merge Sort采用经典的分治策略先递归地将当前数组平均分成两半然后将有序数组两两合并最终合并成一个有序数组。 通过将当前乱序数组分成长度近似的两份分别进行「 递归 」调用然后再对这两个排好序的数组利用两个游标将数据元素依次比较选择相对较小的元素存到一个「 辅助数组 」中再将「 辅助数组 」中的数据存回「 原数组 」。 具体实现
我们以[0,5,7,3,1,6,8,4] 为例演示一下归并排序算法的整个步骤。 分解过程先递归地将当前数组平均分成两半直到子数组长度为 1。 找到数组中心位置 mid从中心位置将数组分成左右两个子数组 。对左右两个子数组分别进行递归分解。最终将数组分解为 n 个长度均为 1的有序子数组。归并过程从长度为 1 的有序子数组开始依次将有序数组两两合并直到合并成一个长度为 n 的有序数组。 使用临时数组复制原数组。使用两个指针 _pos、_pos 分别指向两个有序子数组的开始位置。比较两个指针指向的元素将两个有序子数组中较小元素依次存入到结果数组 a 中并将指针移动到下一位置。重复步骤 3直到某一指针到达子数组末尾。将另一个子数组中的剩余元素存入到结果数组中。 完整流程如下建议反复观看容易理解 代码实现
我觉得我的注释还算清晰了噶##
#include iostream
using namespace std;void merge(int a[],int temp[],int left,int mid,int right){ //归并过程 for(int i 0; i right; i){temp[i] a[i]; //将a数组元素拷贝到辅助数组中 }int l_pos left; //未排序左半区第一个元素下标 int r_pos mid 1; //未排序右半区第一个元素下标 int pos left; //临时数组第一个元素下标 while(l_pos mid r_pos right){if(temp[l_pos] temp[r_pos]) //左半区第一个元素小于右半区第一个元素a[pos] temp[l_pos];elsea[pos] temp[r_pos]; }while(l_pos mid) a[pos] temp[l_pos]; //复制左半区剩余元素 while(r_pos right) a[pos] temp[r_pos]; //复制右半区剩余元素 }
void mSort(int a[],int temp[],int left,int right){ //分解过程 if(left right){//递归地将当前数组平均分成两半 int mid (left right) 1; // 1 等于 /2 mSort(a,temp,left,mid); //左数组分解 mSort(a,temp,mid 1,right); //右数组分解 merge(a,temp,left,mid,right); //合并 }
}
void MergeSort(int a[],int n){int *temp new int[n]; //开辟辅助数组 //c语言 : int *temp (int*)malloc(n * sizeof(int));mSort(a,temp,0,n - 1);delete[] temp; //c语言 free(temp)
}
void Print(int a[],int n){ //打印数组 for(int i 0;i n; i){printf(%d ,a[i]);}puts();
}
int main(){int a[] {0,5,7,3,1,6,8,4};int n sizeof(a)/sizeof(a[0]); //获取数组长度 Print(a,n);MergeSort(a,n); //进行归并排序 Print(a,n);return 0;
}
性能分析
时间效率O(nlong₂ⁿ)。
空间效率O(n)用了辅助数组O(n)。
稳定性因为在两个有序子数组的归并过程中如果两个有序数组中出现相等元素merge算法能够使前一个数组中那个相等元素先被复制从而确保这两个元素的相对顺序不发生改变。因此归并排序算法是一种 稳定排序算法。
适用性适用于顺序存储和链式存储的线性表。 题目练习
【题目描述】LCR 170. 交易逆序对的总数 - 力扣LeetCode 【解题思路】 用暴力解法一定超时这里可采用归并排序。 重点在于 [合并过程] 假设左右区间已经有序执行合并当右区间元素加入到原始数组时计数器加上左区间剩余元素数量作为答案贡献值。因为左区间元素一定小于当前加入元素刚好与当前元素构成逆序对。当左区间元素加入时就不进行计数因为已经算过了。像这样 利用分治思想将大问题分解成小问题。每次合并成更大的子数组为下一次合并做准备直至合并成有序的数组。 【AC代码】
class Solution {
public:int reversePairs(vectorint record) {int n record.size();vectorint temp(n); //开一个辅助数组return MergeSort(record,temp,0,n - 1);}int MergeSort(vectorint a,vectorint temp,int left,int right){if(left right) return 0; int mid (left right) 1;int leftPairs MergeSort(a,temp,left,mid); //记录左区间的逆序对int rightPairs MergeSort(a,temp,mid 1,right); //记录右区间的逆序对int totalPairs MergeAndCount(a,temp,left,mid,right); //记录总的逆序对return leftPairs rightPairs totalPairs; //返回所有的逆序对就是答案}int MergeAndCount(vectorint a,vectorint temp,int left,int mid,int right){for(int i left; i right; i){temp[i] a[i];}int l_pos left,r_pos mid 1;int pos left;int count 0; //计数器while(l_pos mid r_pos right){if(temp[l_pos] temp[r_pos]){a[pos] temp[l_pos];}else{a[pos] temp[r_pos]; count (mid - l_pos 1); //只有右区间加入元素时统计左区间的元素}}while(l_pos mid) a[pos] temp[l_pos];while(r_pos right) a[pos] temp[r_pos];return count;}
}; 桶排序⭐⭐⭐
算法描述 桶排序Bucket Sort将待排序数组中的元素分散到若干个「桶」中然后对每个桶中的元素再进行单独排序。 利用哈希的思想将元素分类同一类的映射哈希到同一个桶中每个桶是一个数组映射完毕以后对每个桶执行排序可以是任意排序比如 快速排序、归并排序 等等。 具体实现
我们 [39,49,8,13,22,15,10,30,5,44]为例演示一下桶排序算法的整个步骤。 确定桶的数量根据待排序数组的值域范围将数组划分为 k 个桶每个桶可以看做是一个范围区间。分配元素遍历待排序数组元素将每个元素根据大小分配到对应的桶中。对每个桶进行排序对每个非空桶内的元素单独排序。合并桶内元素将排好序的各个桶中的元素按照区间顺序依次合并起来形成一个完整的有序数组。 代码实现
#include iostream
#include vector
#include algorithm
using namespace std;// 选择排序
void SelectionSort(vectorint nums){int n nums.size();for(int i 0;i n - 1; i){ int min i; for(int j i 1; j n; j){ if(nums[j] nums[min]) min j; } swap(nums[i],nums[min]); }
}// 桶排序
vectorint bucketSort(vectorint nums) {int bucket_size 5; //定义每个桶的大小 // 计算待排序序列中最大值元素 nums_max、最小值元素 nums_minint nums_min *min_element(nums.begin(), nums.end());int nums_max *max_element(nums.begin(), nums.end());// 定义桶的个数为 (最大值元素 - 最小值元素) / 每个桶的大小 1int bucket_count (nums_max - nums_min) / bucket_size 1;// 定义桶数组 bucketsvectorvectorint buckets(bucket_count);// 遍历待排序数组元素将每个元素根据大小分配到对应的桶中for (int num : nums) {buckets[(num - nums_min) / bucket_size].push_back(num);}// 对每个非空桶内的元素单独排序排序之后按照区间顺序依次合并到 res 数组中vectorint res;for (auto bucket : buckets) {SelectionSort(bucket);res.insert(res.end(), bucket.begin(), bucket.end());}return res; // 返回结果数组
}void Print(vectorint nums){ //打印数组 for(int x : nums){printf(%d ,x);}puts( );
}
int main() {vectorint arr {29,25,3,49,9,37,21,43}; // 待排序数组Print(arr);vectorint sortedArr bucketSort(arr); // 调用桶排序Print(sortedArr);return 0;
}性能分析
时间效率时间复杂度接近于 O(n)。
空间效率O(nm)。由于桶排序使用了辅助空间所以桶排序的空间复杂度是 O(nm)。
稳定性排序的稳定性取决于桶内使用的排序算法。如果桶内使用稳定的排序算法比如插入排序算法并且在合并桶的过程中保持相等元素的相对顺序不变则桶排序是一种 稳定排序算法。反之则桶排序是一种 不稳定排序算法。
适用性顺序存储的线性表。 题目练习
【题目描述】220. 存在重复元素 III - 力扣LeetCode 【解题思路】 此题用暴力也一样会超时可以利用桶排序的思想解决此问题 我们可以首先创建一个桶数组然后遍历数组 nums将每个元素放入对应的桶中。接着我们遍历桶数组对于每个非空的桶我们可以检查与其相邻的桶内的元素是否满足条件。 并不断地更新桶的内容同时根据indexDiff的要求适时删除旧的桶项确保每个时刻桶中保存的信息都是与当前元素相关的、可能形成有效元素对的候选。这种方式隐含了对所有可能的i和j组合的检查避免了双重循环大大提高了效率。 【AC代码】
class Solution {using ll long long;
public:bool containsNearbyAlmostDuplicate(vectorint nums, int indexDiff, int valueDiff) {if (indexDiff 0 || valueDiff 0) return false;unordered_mapll, ll bucket; //用哈希表来存储桶信息ll Size (ll)valueDiff 1; //定义桶大小for (int i 0; i nums.size(); i) {ll x nums[i];ll idx (x - INT_MIN) / Size; //确保当前数的索引为正数if (bucket.count(idx) 0) return true; //对应桶中存在说明满足条件//检查相邻的桶中是否满足条件if (bucket.count(idx - 1) 0 abs(bucket[idx - 1] - x) valueDiff) return true;if (bucket.count(idx 1) 0 abs(bucket[idx 1] - x) valueDiff)return true;bucket[idx] x; //插入桶中if (i indexDiff) bucket.erase(((ll)nums[i - indexDiff] - INT_MIN) / Size); //索引超出直接从桶中删去} return false;}
}; 计数排序⭐⭐
算法描述 计数排序Counting Sort是一个非基于比较的稳定的线性时间的排序算法通过统计数组中每个元素在数组中出现的次数根据这些统计信息将数组元素有序的放置到正确位置从而达到排序的目的。 计数排序的名字会让我们想到“计数法”实际上计数排序的实现就是使用的计数法。 具体实现
我们以 [3,0,4,2,5,1,3,1,4,5] 为例演示一下计数排序算法的整个步骤。 使用一个额外的数组 cnt其中第 i 个元素是待排序数组 nums 中值等于 i 的元素的个数然后根据数组 cnt 来将 nums 中的元素排到正确的位置。创建一个足够大的数组 cnt足够大的意思是 cnt 的下标范围可以包括所有的待排序数据值。然后遍历待排序数据使用计数法统计每个数据的出现次数。最后遍历 cnt 数组将每一个值cnt[i]不为 0 的下标i放入原数组 cnt[i] 次。 代码实现
#include iostream
#include vector
using namespace std;void CountingSort(int nums[], int n) {int maxNum 0;for (int i 0; i n; i) {maxNum max(maxNum, nums[i]);}vectorint cnt(maxNum,0); // 计数器初始化为全 0int top 0;for (int i 0; i n; i) cnt[nums[i]]; //元素在计数器中加一 for (int i 0; i maxNum; i) {while (cnt[i] ! 0) {nums[top] i;--cnt[i];}}
}
void Print(int nums[], int n) { //打印数组 for (int i 0; i n; i) printf(%d , nums[i]);puts();
}
int main() {int nums[] {3, 0, 4, 2, 5, 1, 3, 1, 4, 5};int n sizeof(nums) / sizeof(nums[0]); //获取数组长度 Print(nums, n);CountingSort(nums, n); //进行计数排序 Print(nums, n);
}性能分析
时间效率O(nk)。其中 k 代表待排序数组的值域。
空间效率O(k)。其中 k 代表待排序序列的值域。由于用于计数的数组 cnt 的长度取决于待排序数组中数据的范围大小等于待排序数组最大值减去最小值再加 1。所以计数排序算法对于数据范围很大的数组需要大量的内存。
稳定性由于向结果数组中填充元素时使用的是逆序遍历可以避免改变相等元素之间的相对顺序。因此计数排序是一种 稳定排序算法
适用性计数排序一般用于整数排序不适用于按字母顺序、人名顺序排序。 题目练习
【题目描述】1122. 数组的相对排序 - 力扣LeetCode 【解题思路】 利用计数排序的思想将arr1映射到计数器中在遍历arr2按此顺序添加答案并将计数器置0对于arr2没有出现的数最后需要重新遍历计数器将其加入答案。 【AC代码】
class Solution {
public:vectorint relativeSortArray(vectorint arr1, vectorint arr2) {int maxNum 0;for (int i 0; i arr1.size(); i) maxNum max(maxNum, arr1[i]);vectorint cnt(maxNum 1,0); //定义计数器vectorint ans;for(int x : arr1) cnt[x]; for(int x : arr2){for(int i 0; i cnt[x]; i){ans.push_back(x);}cnt[x] 0; //加完将计数器置0}for(int i 0; i cnt.size(); i){ //最后将遗漏元素加入答案while(cnt[i] ! 0){ans.push_back(i);--cnt[i];} }return ans;}
}; 基数排序⭐⭐⭐⭐
算法描述 基数排序Radix Sort将整数按位数切割成不同的数字然后从低位开始依次到高位逐位进行排序从而达到排序的目的。 基数排序本质也是桶排序不过它是利用数位来划分桶。 具体实现
我们以 [692,924,969,503,871,704,542,436]为例演示一下基数排序算法的整个步骤。 首先准备 10 个队列一种 「 先进先出 」 的数据结构进行若干次「 迭代 」。每次「 迭代 」先清空队列然后取每个待排序数的对应十进制位通过「 哈希 」映射到它「 对应的队列 」中然后将所有数字「 按照队列顺序 」塞回「 原数组 」完成一次 「 迭代 」。 在进行排序过程中我们需要取得一个数字 v 的十进制的第 k 位的值。如下 我们要得到的就是 ak。 可以将 v 直接除上 10ᵏ 再模上 10即 v / 10ᵏ mod 10 。 例如2024 取十位v / 10¹ mod 10 2024 / 10 % 10 2。 定好进制位exp一般从个位1开始。初始化 10个队列将所有数字按照当前位的数值放入对应的队列中。从第 0 个队列到 第 9 个队列将所有数字按照顺序取出来放回原数组。更新进制位exp从低位到高位然后继续迭代。 代码实现
#include iostream
#include vector
#include queue
#include algorithm
using namespace std;void radixSort(vectorint nums) {int maxVal *max_element(nums.begin(), nums.end());//获取数组中的最大数用于确定排序的轮数int exp 1; //初始化为1表示个位queueint buckets[10]; // 10个队列分别存放0-9的数字while(maxVal / exp 0) {// 将所有数字按照当前位的数值放入对应的队列中for(int x : nums) {int idx (x / exp) % 10; //哈希映射 buckets[idx].push(x);}// 从队列中取出元素放回原数组准备下一轮排序int pos 0;for(int i 0; i 10; i) {while( !buckets[i].empty() ) {nums[pos] buckets[i].front();buckets[i].pop();}}exp * 10; // 指数增倍进行更高位的排序}
}void Print(vectorint nums) { // 打印数组for(const int x : nums) {cout x ;}cout endl;
}int main() {vectorint nums {692,924,969,503,871,704,542,436};Print(nums);radixSort(nums); //进行基数排序 Print(nums);return 0;
}
性能分析
时间效率O(n×k)。其中 n 是待排序元素的个数k 是数字位数。k 的大小取决于数字位的选择十进制位、二进制位和待排序元素所属数据类型全集的大小。
空间效率O(nk)。
稳定性基数排序采用的桶排序是稳定的。基数排序是一种 稳定排序算法。
适用性基数排序适用于顺序存储和链式存储 引申如果待排序数组中有负数那么基数排序又该如何如何实现呢。 可以加一个偏移量偏移所有数使其非负。 题目练习
【题目描述】164. 最大间距 - 力扣LeetCode 【解题思路】 题目要求在线性时间复杂度O(n)内解决前面的快速排序归并排序的复杂度达到O(nlong₂ⁿ)。所以这里可以采取基数排序然后遍历数组找到相邻最大元素即可。 【AC代码】
class Solution {
public:int maximumGap(vectorint nums) {int n nums.size();if(n 2) return 0;int maxVal *max_element(nums.begin(),nums.end());queueint buckets[10];int exp 1;while(maxVal / exp 0){for(int num : nums){int idx (num / exp) % 10;buckets[idx].push(num);}int pos 0;for(int i 0; i 10; i){while( !buckets[i].empty() ){nums[pos] buckets[i].front();buckets[i].pop();}}exp * 10;}int ans 0;for(int i 1; i n; i){ans max(nums[i] - nums[i - 1],ans);}return ans;}
}; 总结
做好小事熬过难事静成大事。每天学习一点进步一点好好珍惜现在的学习时光。
最后祝你我在这声色牛马的世界里保持清澈。
