9.9日记录

1.常见排序算法的复杂度

1.快速排序

1.1快速排序为什么快

从名称上就能看出，快速排序在效率方面应该具有一定的优势。尽管快速排序的平均时间复杂度与“归并排序”和“堆排序”相同，但通常快速排序的效率更高，主要有以下原因。

• 出现最差情况的概率很低：虽然快速排序的最差时间复杂度为 O(N的平方) ，没有归并排序稳定，但在绝大多数情况下，快速排序能在 O(nlog⁡N) 的时间复杂度下运行。
• 缓存使用效率高：在执行哨兵划分操作时，系统可将整个子数组加载到缓存，因此访问元素的效率较高。而像“堆排序”这类算法需要跳跃式访问元素，从而缺乏这一特性。
• 复杂度的常数系数小：在上述三种算法中，快速排序的比较、赋值、交换等操作的总数量最少。这与“插入排序”比“冒泡排序”更快的原因类似。

 1.2基准数优化

快速排序在某些输入下的时间效率可能降低。举一个极端例子，假设输入数组是完全倒序的，由于我们选择最左端元素作为基准数，那么在哨兵划分完成后，基准数被交换至数组最右端，导致左子数组长度为n-1，右子数组长度为0， 如此递归下去，每轮哨兵划分后都有一个子数组的长度为0，分治策略失效，快速排序退化为“冒泡排序”的近似形式。

为了尽量避免这种情况发生，我们可以优化哨兵划分中的基准数的选取策略。例如，我们可以随机选取一个元素作为基准数。然而，如果运气不佳，每次都选到不理想的基准数，效率仍然不尽如人意。

需要注意的是，编程语言通常生成的是“伪随机数”。如果我们针对伪随机数序列构建一个特定的测试样例，那么快速排序的效率仍然可能劣化。

为了进一步改进，我们可以在数组中选取三个候选元素（通常为数组的首、尾、中点元素），并将这三个候选元素的中位数作为基准数。这样一来，基准数“既不太小也不太大”的概率将大幅提升。当然，我们还可以选取更多候选元素，以进一步提高算法的稳健性。采用这种方法后，时间复杂度劣化至O(N)方  的概率大大降低。

2.冒泡排序

​

3.选择排序

void selectNum(vector<int>& nums) {//选择排序时间复杂度O(N)的平方 空间复杂度01int 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;}
};