C/C++教程
leetcode刷题笔记_排序1
排序
冒泡排序
-
两两交换，依次把最大值移到最后面
#include <iostream> #include <cstring> #include <vector> #include <map> #include <cmath> #include <set> using namespace std; void busort(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) { for (int j = 1; j < arr.size() - i - 1; j++) { if (arr[j - 1] > arr[j]) { int temp = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = temp; } } } } int main() { vector<int> arr = {1,4,2,3,7,5,9,6,8}; busort(arr); for (int i = 0; i < arr.size(); i++) cout << arr[i] << endl; return 0; }
把数组排成最小的数
题目：输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
测试用例：
输入: [10,2] 输出: "102"
思路：其实就是对数组中的每个数的每一位进行排序，取最小的值
代码
class Solution {
public:
string minNumber(vector<int>& nums) {
if (nums.size() == 0)
return "";
string res;
//对数组进行排序，如果两个数交换顺序之后组成的字符串更小，就交换两个数
for (int k = 0; k < nums.size(); k++)
{
for (int x = 1; x < nums.size(); x++)
{
if (to_string(nums[x])+to_string(nums[x-1])< to_string(nums[x-1]) + to_string(nums[x]))
{
int temp = nums[x];
nums[x] = nums[x - 1];
nums[x - 1] = temp;
}
}
}
//对每一位数把整形转化为字符串
for (int k = 0; k < nums.size(); k++)
{
res = res + to_string(nums[k]);
}
return res;
}
};
移动零
-
题目:给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。 -
测试样例
-
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
-
代码
class Solution { public: void moveZeroes(vector<int>& nums) { //采用冒泡排序思想，遇到零就把它移到末尾 for(int i=0;i<nums.size();i++) { for(int j=1;j<nums.size()-i;j++) { if(nums[j-1]==0) { int temp=nums[j]; nums[j]=nums[j-1]; nums[j-1]=temp; } } } } };
选择排序
双重循环遍历数组，每经过一轮比较，找到最小元素的下标，将其交换至首位
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <string>
using namespace std;
class Solution {
public:
void SelectSort(vector<int>& arr)
{
for (int i = 0; i < arr.size(); i++)
{
//存储最小的下标
int indexMin = i;
for (int j = i+1; j < arr.size(); j++)
{
if (arr[j] < arr[indexMin])
indexMin = j;
}
//找到最小元素的下标，将其交换至首位，也就是交换i下标对应的值和indexmin对应的值
int temp = arr[i];
arr[i] = arr[indexMin];
arr[indexMin] = temp;
}
}
};
int main()
{
Solution* solution = new Solution();
vector<int> arr = { 7,2,4,5,1,6,9 };
solution->SelectSort(arr);
for (int i = 0; i < arr.size(); i++)
cout << arr[i];
return 0;
}
数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
-
思路：从0到k选择排序，找到第k大的数就停止
class Solution { public: int findKthLargest(vector<int>& nums, int k) { for(int i=0;i<k;i++) { //记录这一轮最大的数 int maxIndex=i; for(int j=i+1;j<nums.size();j++) { if(nums[j]>nums[maxIndex]) maxIndex=j; } //把这一轮最大的数和第i个数交换 int temp=nums[i]; nums[i]=nums[maxIndex]; nums[maxIndex]=temp; } //返回k-1坐标的数也就是第k大的数 return nums[k-1]; } };
排序数组
给你一个整数数组 nums，请你将该数组升序排列。
-
直接选择排序会超出时间限制
class Solution { public: vector<int> sortArray(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) { //存储最小的下标 int indexMin = i; for (int j = i+1; j < arr.size(); j++) { if (arr[j] < arr[indexMin]) indexMin = j; } //找到最小元素的下标，将其交换至首位，也就是交换i下标对应的值和indexmin对应的值 int temp = arr[i]; arr[i] = arr[indexMin]; arr[indexMin] = temp; } return arr; } }; -
快速排序
-
class Solution { public: vector<int> sortArray(vector<int>& arr) { sort(arr.begin(),arr.end()); return arr; } };
插入排序
插入排序的思想非常简单，生活中有一个很常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。
插入排序有两种写法：
交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。
移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/ev4tee/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <string>
using namespace std;
class Solution {
public:
void InsertSort(vector<int>& arr)
{
//从第二个数组开始，依次插入到合适的位置上
for (int i = 1; i < arr.size(); i++)
{
int insertIndex = 0;
int num = arr[i];
//找到插入的位置
while (insertIndex<i&& num> arr[insertIndex])
{
insertIndex++;
}
//从插入位置开始到i，整个数组往后移动
for (int k = i; k > insertIndex; k--)
arr[k] = arr[k-1];
arr[insertIndex] = num;
}
}
};
int main()
{
Solution* solution = new Solution();
vector<int> arr = { 7,2,4,5,1,6,9 };
solution->InsertSort(arr);
for (int i = 0; i < arr.size(); i++)
cout << arr[i];
return 0;
}
对链表进行插入排序
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(head==nullptr&&head->next==nullptr)
return head;
//定义一个新链表保存插入后的链表
ListNode* res=new ListNode(0);
res->next=new ListNode(head->val);
//p1指向当前待插入的结点
ListNode* p1=head->next;
//p2指向插入的位置
ListNode*p2=res->next;
//pre指向插入位置的前一个结点
ListNode*pre=res;
while(p1)
{
int value=p1->val;
p2=res->next;
pre=res;
while(p2&&(value>(p2->val)))
{
pre=p2;
p2=p2->next;
}
//找到插入的位置之后，把val这个结点插到对应的位置上
ListNode *newNode=new ListNode(p1->val);
newNode->next=pre->next;
pre->next=newNode;
//指向下一个待插入的节点
p1=p1->next;
}
return res->next;
}
};
小结
本章我们介绍了三种基础排序算法：冒泡排序、选择排序、插入排序。
冒泡排序
冒泡排序有两种优化方式：
记录当前轮次是否发生过交换，没有发生过交换表示数组已经有序；
记录上次发生交换的位置，下一轮排序时只比较到此位置。
选择排序
选择排序可以演变为二元选择排序：
二元选择排序：一次遍历选出两个值——最大值和最小值；
二元选择排序剪枝优化：当某一轮遍历出现最大值和最小值相等，表示数组中剩余元素已经全部相等。
插入排序
插入排序有两种写法：
交换法：新数字通过不断交换找到自己合适的位置；
移动法：旧数字不断向后移动，直到新数字找到合适的位置。
相同点
时间复杂度都是 O(n^2) ，空间复杂度都是 O(1)。
都需要采用两重循环。
不同点
选择排序是不稳定的，冒泡排序、插入排序是稳定的；
在这三个排序算法中，选择排序交换的次数是最少的；
在数组几乎有序的情况下，插入排序的时间复杂度接近线性级别。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/oz4nzd/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
希尔排序
-
将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组
-
逐渐缩小间隔进行下一轮排序
-
最后一轮时，取间隔为 1，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/eu039h/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
堆排序
堆：符合以下两个条件之一的完全二叉树：
根节点的值 ≥ 子节点的值，这样的堆被称之为最大堆，或大顶堆；
根节点的值 ≤ 子节点的值，这样的堆被称之为最小堆，或小顶堆。
堆排序过程如下：
用数列构建出一个大顶堆，取出堆顶的数字；
调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字；
循环往复，完成整个排序。
整体的思路就是这么简单，我们需要解决的问题有两个：
如何用数列构建出一个大顶堆；
取出堆顶的数字后，如何将剩余的数字调整成新的大顶堆。
构建大顶堆 & 调整堆
构建大顶堆有两种方式：
方案一：从 0 开始，将每个数字依次插入堆中，一边插入，一边调整堆的结构，使其满足大顶堆的要求；
方案二：将整个数列的初始状态视作一棵完全二叉树，自底向上调整树的结构，使其满足大顶堆的要求。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/eu7ux3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/sort-algorithms/os5lwi/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 选择排序实现
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
//选择排序取前k个数
vector<int>res;
for(int i=0;i<k;i++)
{
int minIndex=i;
for(int j=i+1;j<arr.size();j++)
if(arr[j]<arr[minIndex])
minIndex=j;
int temp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=temp;
//结果数组中加入这一轮最小的数
res.push_back(arr[i]);
}
return res;
}
};
快速排序
-
其实快速排序就是一个挖坑填数+分治的过程
-
该方法的基本思想是：
- 1．先从数列中取出一个数作为基准数。
- 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3．再对左右区间重复第二步，直到各区间只有一个数。
#include <iostream> #include <cstring> #include <vector> #include <map> #include <cmath> #include <set> #include <string> using namespace std; class Solution { public: //返回调整之后的中间值的坐标 int adjustIndex(vector<int>& arr, int start, int end) { //先选择一个基数，保存在flag里面，这个时候这个基数所在的位置arr[i]就可以看作是一个待填的坑， //因为他的值被保存了，arr[i]这个位置就可以放别的值 //我们最后的结果是要把比flag大的数放在flag的右边，比flag小的数放在flag的左边 int flag = arr[start]; int i = start, j = end; while (i < j) { //从基数的右边找到一个比flag小的数 while (i<j && arr[j]>=flag) j--; //把这个数填进坑arr[i]里 if (i < j) { arr[i] = arr[j]; i++; } //这个时候arr[j]被保存了 arr[j]又成了新的坑 //在左边找一个数填进arr[j]这个坑里 while (i < j && arr[i] < flag) i++; if (i < j) { arr[j] = arr[i]; j--; } //填完之后arr[i]的值又被保存了，所以arr[i]的位置成了新的坑，继续找数来填 } //退出的时候i=j，这个时候把flag的值填进这个位置即可 arr[i] = flag; return i; } void QuickSort(vector<int>& arr,int start,int end) { //如果左边的坐标已经大于等于右边的坐标，退出递归 if (start >= end) return; int mid = adjustIndex( arr, start, end); //对左半部分进行快排 QuickSort(arr, start, mid - 1); QuickSort(arr, mid+1, end); } }; int main() { Solution* solution = new Solution(); vector<int> arr = { 7,2,4,5,1,6,9 }; solution->QuickSort(arr,0,arr.size()-1); for (int i = 0; i < arr.size(); i++) cout << arr[i]; return 0; }
-
cosmos 开发是什么-icode9专业技术文章分享07-09
-
Cosmos 示例-icode9专业技术文章分享07-09
-
安装Cosmos SDK-icode9专业技术文章分享07-09
-
ubuntu 安装 cosmos-icode9专业技术文章分享07-09
-
cosmos 开发能做到跨链吗-icode9专业技术文章分享07-09
-
app 未公示个人信息的收集范围 的解决办法-icode9专业技术文章分享07-09
-
测试人员在 Scrum 中的角色是什么？07-08
-
Dify + TiDB Vector，快速构建你的AI Agent07-07
-
有没有什么开源的py项目可以对图像进行分类-icode9专业技术文章分享07-06
-
feign默认connecttimeout和readtimeout是多少-icode9专业技术文章分享07-05
-
idea控制台，日志太多，导致部分想看得日志被刷走 搜不到-icode9专业技术文章分享07-05
-
The server selected protocol version Tls10 is not accepted by client preferences [TLs12]-icode9专业技术文章分享07-05
-
怎么清理项目缓存-icode9专业技术文章分享07-05
-
安装 Eyoucms详细图文教程-icode9专业技术文章分享07-04
-
ueditor 复制文章时，图片的链接是一个下载图片地址，该如何处理？-icode9专业技术文章分享07-04
