当前位置：首页 > news >正文

力扣-排序算法

news 来源：原创 2024/9/20 15:36:46

排序算法，一般都可以使用std：：sort（）来快速排序。

这里介绍一些相关的算法，巩固记忆。

快速排序

跟二分查找有一丢丢像。

首先选择一个基准元素，一般就直接选择第一个。然后两个指针，一个指向第一个，一个指向最后一个。第一个现在是空，就从最后一个开始，跟基准元素做判断，小于基准元素的就放到第一个位置，然后第一指针往后移。按这种顺序直到两个指针相遇，相遇的位置放入基准元素。然后从基准元素劈开两半，再按相同方法排序。
void quicksort(vector<int> nums,int l,int r){if(l+1>=r)return;int first=l,last=r-1;int key=nums[first];while(first<=last){while(first<last&&nums[last]>=key)last--;nums[first]=nums[last];while(first<last&&nums[first]<=key)first++;nums[last]=nums[first];}nums[first]=key;quicksort(nums,l,first);quicksort(nums,first+1,r);
}

归并算法

归并算法是一种分治算法，先分再治。比如说8个数字。先分成4个4个，然后4个内部再继续分，分成2个2个。2个排好序后合并，4个排好序后再合并。
void merge_sort(vector<int> &nums,int l,int r,vector<int>& temp){if(l+1>=r)return ;int m=(l+r)/2;merge_sort(nums,l,m,temp);merge_sort(nums,m+1,r,temp);int a=l,b=m,i=l;while(a<m||b<r){if(nums[a]<nums[b])nums[i++]=nums[a++];elsenums[i++]=nums[b++];}for(i=l;i<r;i++)nums[i]=temp[i];
}

插入排序

首先是一个数，本来就有序。接着两个数进行排序。接着三个数。

所谓插入，比如说八个数进行排序，其实前七个已经有序，这个时候只需要把第八个插入到前七个数的合适位置即可。怎么插入，就从后往前，一个一个比较，如果小于就往前移。
void insert_sort(vector<int>& nums,int n){int i,j;for(i=0;i<n;i++){for(j=i;j>0;j--){if(nums[j]>nums[j-1])swap(nums[j],nums[j-1]);}}
}

冒泡排序

相邻两个数比较，大的往后移，每一轮最大的数将会移到最后。

可以进行一个优化，可能出现一种情况，从第二轮过后，其实数组已经是有序的了，但是按照算法步骤来走的话，即使已经排好序了，但仍是会进行后边的比较，知道全部比较完成

因此，我们可以对代码进行优化，如果发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。

解决方式：可以通过一个标志位来进行判断
void bubble_sort(vector<int>& nums,int n){int flag=false;int i,j;for(i=1;i<n;i++){flag=false;for(j=1;j<n-i+1;j++){if(nums[j]<nums[j-1]){swap(nums[j],nums[j-1]);flag=true;}     }if(flag==false)return ;}
}

选择排序

选择最小的数跟第一个数交换，按照同样的方法对后面的n-1个进行排序。
void select_sort(vector<int>& nums,int n){int i,j;for(i=0;i<n;i++){int m=i;for(j=i+1;j<n;j++){if(nums[j]<nums[m]){m=j;}}swap(nums[i],nums[m]);}
}

215.数组中的第K个元素

215. 数组中的第K个最大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:
输入: [3,2,1,5,6,4], k = 2输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4输出: 4
提示：

1 <= k <= nums.length <=
<= nums[i] <=

题解

可以利用快速排序的思想来解决这个问题。

选择一个数，然后将大于它的数字往后移，小于的往前移。如果这个刚好是第k位，直接返回。如果不是，大于k，则对前面做相同的排序，如果不是就对后面做相似的排序。这里的k指的是第k大，因此从小到大排就是第n-k位。

class Solution {
public:int quickselect(vector<int> &nums,int l,int r,int k){if(l==r)return nums[k];int p=nums[l],i=l-1,j=r+1;while(i<j){do i++; while (nums[i] < p);do j--; while (nums[j] > p);if(i<j)swap(nums[i],nums[j]);}if(k<=j) return quickselect(nums,l,j,k);else return quickselect(nums,j+1,r,k);}int findKthLargest(vector<int> &nums, int k) {int n=nums.size();return quickselect(nums,0,n-1,n-k);}
};

347.前k个高频元素

347. 前 K 个高频元素

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：

1 <= nums.length <=
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

题解

可以使用桶排序，使用STL库中的unordered_map，提供了一种基于哈希表的键值对容器。

可以对每一个数字出现的次数进行计算并且存储。
    unordered_map<int,int> m;for(int num:nums) m[num]++;
接着进行排序，然后再定义一个新的数组用来存储要返回的数组。
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;for(int num:nums) m[num]++;vector<pair<int,int>> s;for(auto t:m)s.push_back({t.second,t.first});sort(s.begin(),s.end());vector<int> ans;int t=s.size()-1;while(k--){ans.push_back(s[t--].second);}return ans;}
};
排序这里也有一个库可以使用。

<priority_queue> 是标准模板库（STL）的一部分，用于实现优先队列。

优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> m;for(int num:nums) m[num]++;priority_queue<pair<int,int>> s;for(auto i:m) s.emplace(i.second,i.first);vector<int> ans;while(k--){ans.push_back(s.top().second);s.pop();}return ans;}
};
不得不说如果熟悉使用STL库，真的省事很多。