方便记忆的排序算法

class Algorithm
{
public:
	static void qsort(vector<int> & vec, int l, int h)
	{
		if (l >= h)
			return;
		int mid = partition(vec, l, h);
		qsort(vec, l, mid - 1);
		qsort(vec, mid + 1, h);
	}

private:
	static int partition(vector<int> & arr, int l, int h)
	{
		int key = arr[l];
		while (l < h)
		{
			while (l < h && arr[h] >= key)
				--h;
			arr[l] = arr[h];
			while (l < h && arr[l] <= key)
				++l;
			arr[h] = arr[l];
		}
		arr[l] = key;
		return l;
	}
};

class Algorithm
{
public:
	static void HeapSort(vector<int> & arr, int n)
	{
		for (int i = n / 2 - 1; i >= 0; --i)
		{
			Adjust(arr, n, i);
		}
		for (int i = n - 1; i >= 1; --i)
		{
			swap(arr[0], arr[i]);
			Adjust(arr, i, 0);
		}
	}
private:
	static void Adjust(vector<int> & arr, int length, int index)
	{
		int left = 2 * index + 1;
		int right = left + 1;
		int max = index;
		if (left<length && arr[left]>arr[max])
			max = left;
		if (right<length && arr[right]>arr[max])
			max = right;
		if (max != index)
		{
			swap(arr[max], arr[index]);
			Adjust(arr, length, max);
		}
	}
};

class LRUCache
{
public:
	unordered_map<int, list<pair<int,int>>::iterator> mp;
	list<pair<int,int>> cache;
	int capacity;
	LRUCache(int capacity)
	{
		this->capacity = capacity;
	}

	int get(int key)
	{
		auto ite = mp.find(key);
		if (ite == mp.end())
			return -1;
		auto node = *(ite->second);
		cache.erase(ite->second);
		cache.push_front(node);
		mp[key] = cache.begin();
		return ite->second->second;
	}

	void put(int key, int value)
	{
		auto ite = mp.find(key);
		auto node = make_pair(key, value);
		if (ite == mp.end())
		{
			cache.push_front(node);
			if (cache.size() > capacity)
			{
				mp.erase(cache.back().first);
				cache.pop_back();
			}
		}
		else
		{
			cache.erase(ite->second);
			cache.push_front(node);
		}
		mp[key] = cache.begin();
	}
};