快排

#include<iostream>
#include<vector>
using namespace std;

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int x = q[(l + r) / 2], i = l - 1, j = r + 1;
	while (i < j)
	{
		do i++; while (q[i] < x);
		do j--; while (q[j] > x);
		if (i < j)
			swap(q[i], q[j]);
	}
	quick_sort(q,l,j);
	quick_sort(q,j+1,r);
}
const int N = 1e5 + 10;
int main()
{
	int n;
	cin >> n;
	int q[N];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &q[i]);
	}
	quick_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++)
		printf("%d ", q[i]);
}

Python版本：

def quik_sort(L, left, right):
    if left>right:
        return
    x = L[left]
    i = left
    j = right
    while i<j:
        while i<j and L[j]>=x:
            j-=1
        L[i]=L[j]
        while i<j and L[i]<=x:
            i+=1
        L[j]=L[i]
    L[i] = x
    quik_sort(L,left,i-1)
    quik_sort(L,i+1,right)


a = list(map(int, input().split()))

quik_sort(a, 0, len(a) - 1)

for x in a:
    print(x, end = ' ')
print()

快速选择：第k个数

#include <iostream>
using namespace std;
const int N = 100010;
int n, k;
int q[N];

int quick_sort(int l, int r, int k)
{
    if (l == r)
        return q[l];
    int x = q[l], i = l - 1, j = r + 1;
    while (i < j)
    {
        while (q[++i] < x)
            ;
        while (q[--j] > x)
            ;
        if (i < j)
            swap(q[i], q[j]);
    }
    int sl = j - l + 1; //为什么是j-l+1,从l到j的元素个数
    if (k <= sl)
        return quick_sort(l, j, k);
    return quick_sort(j + 1, r, k - sl);
}

int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
        cin >> q[i];
    cout << quick_sort(0, n - 1, k) << endl;

    return 0;
}

二分查找

#include<iostream>
#include<vector>
using namespace std;


//正常的只包含一个目标元素的二分查找
int binary_search(vector<int> nums, int target)
{
	int l = 0, r = nums.size() - 1;
	while (l <= r)
	{
		int mid = l + (r - l >> 1);
		if (nums[mid] == target)
			return mid;
		else if (nums[mid] < target)
			l = mid + 1;
		else
			r = mid - 1;
	}
	return -1;
}

//包含多个元素时候寻找左端点
int left_binary_search(vector<int> nums, int target)
{
	int left = 0, r = nums.size() - 1;
	while (left <= r)
	{
		int mid = left + (r - left >> 1);
		if (nums[mid] < target)
			left = mid + 1;
		else if (nums[mid] > target)
			r = mid - 1;

		//上面的操作是正常的查找
		//下面的是对于找到了target的时候
		//左边界，所以接着往左边查找
		else
			r = mid - 1;
	}
	if (left > nums.size() || nums[left] != target)
		return -1;
	return left;
}

//右边界的二分查找
int right_binary_search(vector<int> nums, int target)
{
	int left = 0, right = nums.size() - 1;
	while (left <= right)
	{
		int mid = left + (right - left >> 1);
		if (nums[mid] < target)
			left = mid + 1;
		else if (nums[mid] > target)
			right = mid - 1;

		else
			left = mid + 1;
	}
	if (right > nums.size() || nums[right] != target)
		return -1;
	return right;
}

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(3);
	v.push_back(3);
	v.push_back(3);
	v.push_back(4);
	int s1 = binary_search(v, 3);
	int s2 = left_binary_search(v, 3);
	int s3 = right_binary_search(v, 3);
	cout << "普通：" << s1 << endl;
	cout << "左边界： " << s2 << endl;
	cout << "右边界： " << s3 << endl;
}

双指针算法

#include<iostream>
#include<vector>
using namespace std;
//最长连续不重复子序列

const int N = 100010;
int a[N];//存放原来数组的数据
int s[N];//存放j到i中每个数字出现的次数，出现次数大于1就说明有重复数字
int n;

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	int res = 0;
	//下面才开始双指针的精髓
	//i指针一定是要遍历整个数组
	//s[a[j]] --;j++;就是要去除所有有重复的
	for (int i = 0, j = 0; i < n; i++)
	{
		s[a[i]]++;
		while (s[a[i]] > 1)
		{
			s[a[j]] --;
			j++;
		}
		res = max(res, i - j + 1);
	}
	cout << res << endl;
	return 0;
}