1.常见排序算法的复杂度
1.快速排序
1.1快速排序为什么快
从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。
- 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 O(N的平方) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 O(nlogN) 的时间复杂度下运行。
- 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
- 复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。
1.2基准数优化
快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为n-1，右子数组长度为0， 如此递归下去，每轮哨兵划分后都有一个子数组的长度为0，分治策略失效，快速排序退化为“冒泡排序”的近似形式。
为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。
需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。
为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至O(N)方 的概率大大降低。
2.冒泡排序
3.选择排序
void selectNum(vector<int>& nums) {//选择排序时间复杂度O(N)的平方 空间复杂度01
int n = nums.size();
for (int i = 0; i < n-1; i++) {
int k = i;//用k记录未排序区间的最小元素
for (int j = i + 1; j < n; j++) {
if (nums[j] < nums[k]) {
k = j;
}
}
swap(nums[i],nums[k]);
}
}
4.插入排序
void insertSort(vector<int>& nums) {
//外循环
for (int i = 1; i < nums.size(); i++) {
//内循环
int base = nums[i];
int j = i - 1;
while (j>=0&&nums[j] > base) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = base;
}
}
5.归并排序:
void merge(vector<int>& nums, int num1[], int left, int right,int mid){//合并
int l_pos = left;//左半区
int r_pos = mid + 1;//右半区
int pos = left;//临时存储的数组
while(l_pos<=mid&&r_pos<=right) {
if (nums[l_pos] < nums[r_pos]) {
num1[pos++] = nums[l_pos++];
}
else {
num1[pos++] = nums[r_pos++];
}
}
//合并剩余的左半区
while (l_pos <= mid) {
num1[pos++] = nums[l_pos++];
}
//合并剩余的右半区
while (r_pos <=right) {
num1[pos++] = nums[r_pos++];
}
while (left <= right) {//最后 将临时数组中的元素拷贝到目标数组中
nums[left] = num1[left];
left++;
}
}
void msort(vector<int>& nums,int num1[],int left,int right) {//分治
if (left < right) {
int mid = (left + right) / 2;
msort(nums,num1,left,mid);
msort(nums, num1, mid + 1, right);
merge(nums,num1,left,right,mid);
}
}
void merge_sort(vector<int> &nums) {//入口函数
int* num1 = (int*)malloc(nums.size()*sizeof(int));
if (num1) {
msort(nums,num1,0,nums.size()-1);
free(num1);
}
}
2.leetCode.58最后一个单词的长度
给你一个字符串
s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
双指针yyds，一个指针指向最后一个字符串的最后一个字符，另一个指针指向第一个，相减即可。
class Solution {
public:
int lengthOfLastWord(string s) {
int i=s.size()-1;
while(s[i]==' '){
i--;
}
int j=i-1;
while(j>=0&&s[j]!=' '){
j--;
}
return i-j;
}
};
