Javasript学习笔记

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/9d928ed00a12202296eab592443349c2.png)

**递归法**

```c++
#include <iostream>

using namespace std;

int binarySearch(int* nums, int target, int left, int right)
{
	//二分查找
	if(left>right) return -1;
	int mid = (left+right)/2;
	if(nums[mid] == target) return mid;
	if(nums[mid] < target) return binarySearch(nums, target, mid+1, right);
	if(nums[mid] > target) return binarySearch(nums, target, left, mid-1);
}
int search(int* nums, int numSize, int target)
{
	return binarySearch(nums, target, 0, numSize-1);
}

int main()
{
	int nums[7] = {-1 ,2, 5, 6, 7, 8, 9};
	int index = search(nums, 7, 5);
	cout<<index<<endl;
	return 0;
}
```

二分搜索算法

**快速排序**是冒泡排序的进阶版本，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和父换是从网端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，就像它的名字一样，速度更快。

设数组长度为N，详细过程为:

- 在一开始，排序范围是整个数组
- 排序之前，我们选择整个排序范围内的**第一个元素**作为**基准**，对排序范围内的元素进行快速排序
- 先从最右边向左看，依次将每一个元素与**基准元素**进行比较，如果发现比基准元素小，那么就与左边遍历位置上的元素（一开始是基准元素的位置)进行交换，此时保留右边当前遍历的位置。
- 交换后，转为从左往右开始遍历元素，如果发现比基准元素大，那么就与之前保留的右边遍历的位置上的元素进行交换，同样保留左边当前的位置，循环执行上一个步骤。
- 当左右遍历撞到一起时，本轮快速排序完成，最后在最中间的位置就是基准元素的位置了。
- 以基准位置为中心，划分左右两边，以同样的方式执行快速排序。

比如下面的数组:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/5462c526b3e5da4e7063a45798ed9bc2.png)

首先我们选择第一个元素4作为基准元素，一开始左右指针位于两端:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/e0ccbac22882cff0c029f149e89c196a.png)

此时从右往左开始看，直到遇到一个比4小的元素，首先是6，肯定不是，将指针往后移动:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/1b8811a86ec960582fc6b83963c6fe0c.png)

此时继续让3和4进行比较，发现比4小，那么此时直接将3交换（其实直接覆盖过去就行了）到左边指针所指向的元素位置:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/fcc5fef36f7b121078b08ed0d9435688.png)

此时我们转为从左往右看，如果遇到比4大的元素，就交换到右边指针处，3肯定不是了，因为刚刚才缓过来，接着就是2:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/f7782956aa69753e1ea87c3666f1117b.png)

2也没有4大，所以说继续往后看，此时7比4要大，那么继续交换:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/09472da5a6f6370381532e8eefa74352.png)

接着，又开始从右往左看:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/ce39a5d71e121ffef4150c7d8fc2d1f6.png)

此时5是比4要大的，继续向前，发现1比4要小，所以说继续交换:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/2da63f8d669fc06ed8fb9e7d2e319de2.png)

接着又转为从左往右看，此时两个指针撞到一起了，排序结束，最后两个指针所指向的位置就是给基准元素的位置了:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/47d61472b6e162d9f7bf48c2600312cc.png)

本轮快速排序结束后，左边不一定都是有序的，但是一定比基准元素小，右边一定比基准元素大。接着我们以基准为中心，分成两个部分再次进行快速排序:

![](https://picgo-img-repo.oss-cn-beijing.aliyuncs.com/img/de78c61de1d74890a8c178d204338772.png)

这样，我们最后就可以使得整个数组有序了，当然快速排序还有其他的说法，有些是左右都找到了再交换，我们这里的是只要找到就丢过去。既然现在思路已经清楚了，我们就来尝试实现一下快速排序吧:

```c++
void quickSort(int arr[], int start, int end) {
    if (start >= end) return;
    int left = start, right = end, pivot = arr[left];
    while (left < right) {
        while (left < right && arr[right] >= pivot) right--;
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) left++;
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    quickSort(arr, start, left - 1);
    quickSort(arr, left + 1, end);
}

int main() {
    int arr[] = {3, 5, 7, 2, 9, 0, 6, 1, 8, 4};
    quickSort(arr, 0, 9);
    for (auto x: arr) {
        printf("%d", x);
    }
    return 0;
}
```

这样，我们就实现了快速排序。我们还是来分析一下快速排序的稳定性，快速排序是只要遇到比基准小或者大的元素就直接交换，比如原数组就是2,2,1，此时第一个元素作为基准，首先右边1会被丢过来，变成:1,2,1，然后从左往右，因为只有遇到比基准2更大的元素才会换，所以说最后基准会被放到最后一个位置: 1,2,2，此时原本应该在前面的2就跑到后面去了，所以说快速排序算法，是一种**不稳定的**排序算法。