汽油价格网_注册公司需要交多少税_营销网店推广的软文_互动营销案例

说明：本文是作者之前在学习<<数据结构与算法之美>>一书时的学习笔记，并用C语言将相关排序算法和二分查找实现。

递归

递归需要满足的3个条件：

• 待求解问题的解可以分解为几个子问题的解。(子问题就是数据规模更小的问题)
• 待求解问题与分解之后的子问题，只有数据规模不同，求解思路完全相同
• 存在递归终止条件

如何编写递归代码：1、写出递推公式；2、找到终止条件。

在实际编写代码时，一般不用递归，而是将递归代码转换成非递归的，因为递归有可能会导致堆栈溢出。而且有可能导致重复计算(比如斐波那契数列，如果用递归代码实现，则有重复计算)。

尾递归：递归调用是最后一个要执行的语句，并且没有其他局部变量参与最后一个语句的执行。

排序算法

可以把排序算法分为原地排序算法(在原数据存储空间上完成排序操作)和非原地排序算法(需要额外的非常量级的数据存储空间才能完成排序)。

原地排序并不与O(1)空间复杂度划等号。一个排序算法是原地排序算法，但它的空间复杂度可能并不是O(1)。但是，反过来说，一个排序算法的空间复杂度为O(1)，则它肯定是原地排序算法。

我们还可以根据算法的稳定性，将排序算法分为稳定排序算法和不稳定排序算法。稳定排序算法是指排序后，相等的元素之间原本的顺序不会改变的排序算法。而不稳定排序算法是指，经过排序之后，相等元素之间原有的先后顺序有可能会被改变。

冒泡排序(bubble sort)

冒泡排序：通过重复遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作重复进行的，直到没有再需要交换的元素为止。

#include <stdio.h>
void bubbleSort(int arr[], int n)
{int i,j,temp;int swapped;//外层循环控制排序的轮数for (i = 0;i < n-1;i++){swapped = 0;// 每轮开始时，设置交换标志为0// 内层循环负责进行元素的比较和交换for (j = 0;j < n-i-1;j++){// 如果当前元素大于下一个元素，则交换它们if (arr[i] > arr[j+1]){temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;swapped = 1; // 发生了交换，设置交换标志位1}}// 如果在某次遍历中没有发生交换，则提前结束排序if (swapped == 0){break;}}
}

• 冒泡排序是原地排序算法吗？
  • 由于冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，因此，空间复杂度是O(1)，因此，冒泡排序是一个原地排序算法。
• 冒泡排序是稳定排序算法吗？
  • 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序的稳定性，在冒泡的过程中，我们对两个大小相等的相邻的元素不做交换，这样就能保证相同大小的元素，在排序前后原有的先后顺序不会改变，因此，冒泡排序是稳定排序算法。
• 冒泡排序的时间复杂度
  • 在最好的情况下，待排序的数据已经是有序的了，那么只需要进行一遍冒泡操作，就可以结束了，因此，最好的时间复杂度为O(n)。
  • 在最坏的情况下，要排序的数据刚好是倒序排列的，则需要进行n次冒泡操作，因此，最坏时间复杂度为O(n^2)。

插入排序(insertion sort)

将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，在已排序部分找到相应的位置并插入。

#include <stdio.h>
void insertionSort(int arr[], int n)
{int i,key,j;// 初始时，已排序部分是arr[0],因此未排序部分的索引是从i=1开始的。for (i = 1; i < n;i++){key = arr[i]; // 选择未排序的第一个元素j = i - 1;// 将选中的元素与已排序的元素进行比较，如果已排序的元素大于选中的元素，则将其向后移动while (j >= 0 && arr[j] > key){arr[j+1] = arr[j];j--;}// 将选中的元素插入到正确的位置arr[j+1] = key;}
}

• 插入排序是原地排序算法吗？
  • 是原地排序算法。它的空间复杂度是O(1)
• 插入排序是稳定排序算法吗？
  • 对于未排序区间的某个元素，如果在已排序区间存在于它值相同的元素，我们选择将它插入到已排序区间值相同元素的后面，这样就可以保持值相同元素原有的前后顺序不变，因此，插入排序是稳定排序算法。
• 插入排序的时间复杂度
  • 在最好情况下，如果是已经排序好的，则时间复杂度是O(n)。
  • 在最坏情况下，时间复杂度是O(n^2)。

选择排序(selection sort)

选择排序(selection sort)的实现思路类似于插入排序，也将整个数组划分为已排序区间和未排序区间。不同点在于：选择排序每次从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

#include <stdio.h>void selectionSort(int arr[], int n)
{int i, j, min_idx, temp;// 移动未排序数组的边界(初始时，未排序区间是整个数组,已排序区间的大小为0)for (i = 0; i < n-1; i++){// 找到未排序区间的最小元素的索引min_idx = i;for (j = i+1; j< n;j++){if (arr[j] < arr[min_idx]){min_idx = j;}}// 交换找到的最小元素与未排序区间的第一个元素temp = arr[min_idx];arr[min_idx] = arr[i];arr[i] = temp;}
}

• 选择排序是原地排序算法吗？

  • 是原地排序

• 选择排序是稳定排序算法吗？

  • 选择排序不是稳定排序算法。

  比如，原始数据是5,8,5,2,9
  按照上面的实现，经过第一次选择排序的交换后，最小的元素2可能会与第一个5交换位置，因此两个5的相对位置就被打破了。
  

• 选择排序的时间复杂度

  • 最好和最坏情况下，时间复杂度都是O(n^2)。

归并排序(merge sort)

归并排序是一种高效的排序算法，采用分治法的一个典型应用。它将数组分为两半，对每一半递归地进行归并排序，然后将两个排序号的半部分合并在一起。

归并排序的主要步骤：

1、分解：将当前序列平均分成两半，对每一半递归地进行归并排序

2、解决：在分解的子序列中进行排序

3、合并：将两个已排序的子序列合并成一个最终的排序序列

#include <stdio.h>
#include <stdlib.h>void merge_sort(int arr[], int n)
{mergeSort(arr, 0, n-1);
}// l是数组的左边界,r是数组的右边界
void mergeSort(int arr[], int l, int r)
{// 递归终止条件if (l >= r){return;}// 找到中间点int m = l+(r-1)/2;// 递归地排序两半mergeSort(arr, l, m);mergeSort(arr, m+1, r);// 合并两个已排序的半部分merge(arr, l, m, r);
}// 合并两个子数组的函数
void merge(int arr[], int l, int m, int r)
{int i,j,k;int n1= m-l+1; // 左子数组的大小int n2= r -m; // 右子数组的大小// 创建临时数组int L[n1], R[n2];// 拷贝数据到临时数组for (i = 0; i< n1; i++){L[i] = arr[l + i];}for (j = 0; j < n2; j++){R[j] = arr[m+1+j];}// 合并临时数组回到原数组 arr[l...r]i = 0; // 初始索引第一个子数组j = 0; // 初始索引第二个子数组k = l; // 初始索引合并子数组while (i < n1 && j < n2){if (L[i] <= R[j]){arr[k] = L[i];i++;}else{arr[k] = R[j];j++;}k++;}// 如果L[]中还有剩余元素，拷贝剩余元素while (i < n1){arr[k] = L[i];i++;k++;}// 如果R[]中还有剩余元素，拷贝剩余元素while (j < n2){arr[k] = L[j];j++;k++;}
}

• 归并排序是原地排序算法吗？
  • 归并排序不是原地排序算法，它需要O(n)的额外存储空间。
• 归并排序是稳定排序算法吗？
  • 通过merge函数可以确定，归并排序是稳定排序算法。
• 选择排序的时间复杂度
  • 归并排序在最好、最坏和平均情况下的时间复杂度均为O(n *logn)，其中n是数组的长度。

快速排序(quick sort)

快速排序也利用了分治算法思想。

如果要排序数组中下标从p到r的数据，那么，我们选择p到r之间的任意一个数据作为pivot(分区点，一般选择最后一个或第一个)，然后遍历从p到r的数据，将小于pivot的放到左边，将大于或等于pivot的放到右边，将pivot放到中间。经过这一步骤处理之后，从p到r的数据就被分成了3个部分。假设pivot现在所在位置的下标是q，那么从p到q-1的数据都小于pivot，中间是pivot，从q+1到r的数据都大于或等于pivot。

根据分治的处理思想，分区完成后，我们递归地排序下标从p到q-1的数据和下标q+1到r的数据，直到待排序区间大小缩小为1，这就说明数组中所有的数据都有序了。

伪代码如下：

quick_sort(A, n)
{quick_sort_c(A, 0, n-1);
}// 快速排序递归函数，p，r为下标
quick_sort_c(A,p,r)
{if p >= r then return;q = partition(A, p, r); // 分区quick_sort(A, p, q-1);quick_sort(A, q+1, r);
}partition(A,p,r)
{pivot=A[r];i=p;for j=p to r do {if A[j] < pivot{swap A[i] with A[j];i++;}}swap A[i] with A[r];return i;
}

C语言实现：

#include <stdio.h>void swap(int *a, int *b)
{int t = *a;*a = *b;*b = t;
}int partition(int array[], int low, int high)
{int pivot = array[high]; // pivotint i = low; // index of smaller elementfor (int j = low; j <=high;j++){// if current element is smaller than pivotif (array[j] < pivot){swap(&array[i], &array[j]);i++;}}swap(&array[i], &array[high]);return i;
}void quickSort(int array[], int low, int high)
{if (low >= high){return;}// pi is partitioning indexint pi = partition(array, low, high);// separately sort elements before partition and after partitionquickSort(array, low, pi - 1);quickSort(array, pi + 1, high);
}

• 快速排序是原地排序算法吗？

  • 快速排序是原地排序算法。最好空间复杂度O(logn)。最坏空间复杂度O(n)。

• 快速排序是稳定排序算法吗？

  • 快速排序是不稳定排序算法

    比如对于原始数据是6,8,7,6,3,5,9,4来说，
    假如以最后一个元素作为pivot，在经过第一次分区操作之后，两个6的相对先后顺序会发生改变，因此，快排不是稳定排序算法。
    

• 选择排序的时间复杂度

  • 最好时间复杂度：O(n *logn)；最坏时间复杂度O(n^2)。

利用快排的分区方法可以用来求在无序数组中求第K大(或者第K小)，且时间复杂度是O(n)。比如对于4,2,5,12,3这样的数据，从小到大的排序为2,3,4,5,12。因此第2小的元素是3。

思路：选择数组A[0, n-1]中的最后一个元素A[n-1]作为pivot，对数组A[0,n-1]进行原地分区，这样数组就分成了3部分：A[0, p-1]、A[p]、A[p+1, n-1]。

如果K = p+1，那么A[p]就是第K小元素；如果K>p+1，就说明第K小元素出现在A[p+1, n-1]中，我们再按照上面的思路递归地在A[p+1,n-1]中查找。如果K<p+1，就在A[0, p-1]里继续查找。

上面的这个算法也叫快速选择(quick select)算法

#include <stdio.h>void swap(int *a, int *b)
{int t = *a;*a = *b;*b = t;
}int partition(int array[], int low, int high)
{int pivot = array[high]; // pivotint i = low; // index of smaller elementfor (int j = low; j <=high;j++){// if current element is smaller than pivotif (array[j] < pivot){swap(&array[i], &array[j]);i++;}}swap(&array[i], &array[high]);return i;
}int quickSelect(int arr[], int low, int high, int k)
{if (k > 0 && k <= high - low + 1){int index = partition(arr, low, high);// 因为下标是从0开始的，所以是k-1if (index -low == k-1){return arr[index];}if (index - low > k-1){return quickSelect(arr, low, index - 1, k);}return quickSelect(arr, index + 1,high, k-index + low -1);}// 如果K的在数组长度的范围之外，则返回INT_MAX表示没找到return INT_MAX
}

3种线性排序

桶排序、计数排序、基数排序这三种排序算法的时间复杂度是O(n)，因此也称为线性排序(linear sort)。之所以能做到线性的时间复杂度，主要是因为它们都不是基于比较的排序算法，排序的过程不涉及元素之间的比较操作。

三种线性排序对待排序的数据有严苛的要求。

桶排序

桶排序(bucket sort)的核心处理思想是先定义几个有序的“桶”，将要排序的数据分到这几个“桶”中，对每个“桶”里的数据单独进行排序，再把每个“桶”里的数据按照顺序依次取出，组成的序列就是有序的了。

这里需要注意几点：

• 待排序数据要容易划分为m个“桶”，并且“桶”与“桶”之间有着天然的大小顺序，这样每个“桶”内的数据都排序完后，桶与桶之间的数据不需要再进行排序了。
• 数据在各个“桶”之间的分布要比较均匀。如果数据经过划分之后，有些“桶”里的数据非常多，有些“桶”的数据非常少，很不平均，那么“桶”内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被集中划分到一个桶里，那么桶排序就退化为时间复杂度是O(nlogn)的排序算法了。

计数排序

计数排序(counting sort)是桶排序的一种特殊情况。当要排序的n个数据所处的范围并不大的时候，如最大值是k，我们就可以把数据划分为k个桶，每个桶内的数据都是相等的，省掉了桶内排序的时间。

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。

基数排序有两种方法：

1、最高位优先(MSD, Most Significant Digit first)：从最高位开始进行排序。

2、最低位优先(LSD, Least Significant Digit first)：从最低位开始进行排序

排序算法总结

排序算法	是否原地排序	是否稳定排序	平均时间复杂度
冒泡排序	是	是	O(n^2)
插入排序	是	是	O(n^2)
选择排序	是	否	O(n^2)
快速排序	是	否	O(nlogn)
归并排序	否	是	O(nlogn)
桶排序	否	是	O(n+k)，k为数据范围
计数排序	否	是	O(n)
基数排序	否	是	O(dn)，d为数据维度

二分查找(Binary Search)

二分查找，也称折半查找，是一种在有序数组中查找某一特定元素的搜索算法。其核心思想是将查找区间不断地折半，通过将待查找的元素与区间中间位置的元素进行比较，缩小查找范围，直到找到目标元素或确定目标元素不存在为止。二分查找的时间复杂度为O(logn)，其中n是数组的长度，这使得它在处理大规模数据时效率远高于线性查找O(n)。

int binarySearch(int* nums, int numsSize, int target){if (nums == NULL || numsSize == 0) {return -1;}int low = 0;int high = numsSize - 1;int mid;while (low <= high) { // 结束的条件是 low > highmid = low + (high - low) / 2;// 防止溢出if (nums[mid] == target) {return mid; // 找到目标，返回索引} else if (nums[mid] < target) {low = mid + 1; // 在右半部分继续查找} else {high = mid - 1; // 在左半部分继续查找}}return -1;// 未找到目标，返回-1
}

这里需要注意几点：

1. 为什么while循环的条件中是 <=，而不是 < ?
   因为初始化 high = numsSize - 1，即最后一个元素的索引，而不是numsSize。这两者的区别是前者的搜索范围相当于两端都是闭区间[low, high]，而后者相当于是左闭右开区间[low, high)，因为索引numsSize是越界的。
2. 为什么 low = mid + 1和high = mid - 1？
   因为我们上面的代码搜索区间是两端闭区间[low, high]，所以当发现mid不是我们要找的target时，由于mid已经找过了，所以需要从这个搜索范围中扣除。因此需要去[mid + 1, high]或者[left, mid - 1]中去查找。
3. 上面我们mid的取值是 mid = low + (high - low) / 2。为什么不用 mid = (low + high) / 2呢？因为如果low和high比较大的话，两者之和就有可能会溢出。所以将mid的计算方式改成 mid = low + (high - low) / 2。更进一步，我们还可以优化，将这里除以2的操作转化成位运算 mid = low + ((high-low)>>1)。因为相比除法运算，计算机处理位运算要快得多。

二分查找的局限性

1. 二分查找依赖的是顺序表结构，即数组。
2. 二分查找针对的是有序数据，因此只能用在插入、删除操作不频繁，一次排序多次查找的场景中。
3. 数据量太小不适合二分查找，与直接遍历相比效率提升不明显。但是有一个例外，就是数据之间的比较操作非常费时时，比如数组中存储的都是长度超过300的字符串，那还是使用二分查找来尽量减少比较操作吧。
4. 数据量太大也不适合二分查找，因为数组需要连续的空间，若数据量太大，往往找不到存储如此规模数据的连续内存空间。

二分查找变体问题

上述的二分查找是非常简单的一种二分查找：在不存在重复元素的有序数组中，查找值等于给定值的元素。还有几种二分查找的变体问题，比如如下四个：

• 查找第一个值等于给定值的元素
• 查找最后一个值等于给定值的元素
• 查找第一个值大于或等于给定值的元素
• 查找最后一个值小于或等于给定值的元素

查找第一个值等于给定值的元素 & 查找最后一个值等于给定值的元素

LeetCode-34-在排序数组中查找元素的第一个和最后一个位置

题目描述:
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

第一种解法

题解，这里找右边界和左边界是类似的，这里只讲一个左边界：

• 如果当前看到的元素恰好等于 target，那么当前元素有可能是target出现的第1个位置，由于我们要找第1个位置，此时我们应该向左边继续查找。当然, 我们此时可以记下这个元素的位置；
• 如果当前看到的元素严格大于target，那么当前元素一定不是要找的 target出现的第1个位置，第1个位置肯定出现在mid的左边，因此就需要在 [left, mid - 1]区间里继续查找；
  如果当前看到的元素严格小于target，那么当前元素一定不是要找的 target出现的第1个位置，第1个位置肯定出现在mid的右边，因此就需要在 [mid + 1, right] 区间里继续查找。

总结一句话就是：如果查找左边界值，就压缩待查找的区间右边界；如果查找右边界值，就压缩待查找的区间左边界。

// 查找第一个值等于给定值的元素
int searchLeftRange(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;int result = -1;while (left <= right) {mid = left + ((right - left) >>1);if (nums[mid] == target) {result = mid;right = mid - 1; } else if (nums[mid] < target){left = mid + 1;} else {right = mid - 1;}}return result;
}// 查找最后一个值等于给定值的元素
int searchRightRange(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;int result = -1;while (left <= right) {mid = left + ((right - left) >>1);if (nums[mid] == target) {result = mid;left = mid + 1; } else if (nums[mid] < target){left = mid + 1;} else {right = mid - 1;}}return result;
}

第二种解法

上面是一种解法，下面是另一种思路：

// 查找第一个值等于给定值的元素
int searchLeftRange(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;while (left <= right){mid = left + ((right - left) >>1);if (nums[mid] > target){right = mid - 1;}else if (nums[mid] < target){left = mid + 1;}else{if ((mid == 0) || (nums[mid -1] != target)){return mid;}else{right = mid - 1;}}}return -1;
}

nums[mid]与要找的target的大小关系有3中：大于、小于和等于。对于nums[mid] > target和nums[mid] < target的情况，都很好理解，这里不做解释。

对于nums[mid]==target，因为我们是要查找的是第一个值等于给定值的元素，当nums[mid]等于要查找的值时，我们需要确认一下nums[mid]是不是第一个值等于要查找的元素，怎么确认呢？

如果mid等于0，即这个元素已经是数组的第一个元素了，那么它肯定是我们要查找的第一个值等于给定值的元素；如果mid不等于0，但nums[mid]的前一个元素nums[mid-1]不等于target，那么也说明nums[mid]就是第一个元素。

如果经过检查之后发现，nums[mid]前面的一个元素nums[mid-1]也等于target，就说明此时的nums[mid]不是我们要查找的第一个值，那么我们就更新right=mid-1，因为要查找的元素肯定出现在[left, mid-1]区间。

类似的，查找最后一个值等于给定值的元素的代码如下。

// 查找最后一个值等于给定值的元素
int searchRightRange(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;while (left <= right){mid = left + ((right - left) >>1);if (nums[mid] > target){right = mid - 1;}else if (nums[mid] < target){left = mid + 1;}else{if ((mid == numsSize -1) || (nums[mid +1] != target)){return mid;}else{low = mid + 1;}}}return -1;
}

查找第一个值大于或等于给定值的元素

题目描述：
给定一个有序的数组，查找第一个大于等于给定值的元素的下标。例如对于数组[3,4,6,7,10].如果查找第一个大于等于5的元素，则是6，所以返回下标2。

其实仔细想想，这个题目就是查找左边界。所以和【查找第一个值等于给定值的元素】那题的解题思路是一样的，只是那题是在等于目标值时，更新结果。但是本题则是在大于等于目标值时更新。具体请见代码：

// 查找第一个大于等于target的值的下标(相当于查找左边界那题)
int searchFirstGETargetIndex(int *nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;int result = -1;while (left <= right) {mid = left + ((right - left) >>1);if (nums[mid] >= target) {result = mid;right = mid - 1;} else {left = mid + 1;}}return result;
}

思路同上面的第二种解法：

// 查找第一个大于等于target的值的下标(相当于查找左边界那题)
int searchFirstGETargetIndex(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;while (left <= right){mid = left + ((right - left) >>1);if (nums[mid] >= target){// 如果mid是第一个元素或者前面一个元素小于要查找的值target，则nums[mid]就是我们要查找的第一个大于或等于给定值的元素if ((mid == 0) || (nums[mid -1] < target)){return mid;}// 如果nums[mid-1]也大于或等于要查找的值target,则说明要查找的元素在[low, mid-1]区间else{right = mid - 1;}}else{// 如果nums[mid] < target，那么要查找的值肯定在[mid+1, right]区间left = mid + 1;}}return -1;
}

查找最后一个值小于或等于给定值的元素

与上题类似，这个题目其实是【查找最后一个值等于给定值的元素】的变形。

// 查找最后一个小于等于target的值的下标(相当于查找右边界那题)
int searchLastLETargetIndex(int *nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;int result = -1;while (left <= right) {mid = left + ((right - left) >>1);if (nums[mid] <= target) {result = mid;left = mid + 1;} else {right = mid - 1;}}return result;
}

解法二：

// 查找最后一个小于等于target的值的下标(相当于查找右边界那题)
int searchLastLETargetIndex(int* nums, int numsSize, int target) {int left = 0;int right = numsSize - 1;int mid;while (left <= right){mid = left + ((right - left) >>1);if (nums[mid] > target){right = mid - 1;}else{if ((mid == numsSize -1) || (nums[mid +1] > target)){return mid;}else{low = mid + 1;}}}return -1;
}

参考文献

1、https://book.douban.com/subject/35474931/
2、https://github.com/labuladong/fucking-algorithm
3、https://leetcode-cn.com/tag/binary-search/