quick sort（c++）以及k选取

#include<iostream>
#include<vector>
using rank = int;
using namespace std;

int dash = 0;
int swap(vector<int>&arr,int lo, int hi)
{
	dash = arr[lo];
	arr[lo] = arr[hi];
	arr[hi] = dash;
}
//version A 勤于拓展，懒于交换。
//每次选取lo为pivot备份，进行排序，
//将pivot放在对应于已经排序完的有序序列中的位置
int partation_LUG(vector<int>& arr, int lo, int hi)
{
	int pivot = arr[lo];
	while (lo < hi)
	{
		while (lo < hi && pivot <= arr[hi]) --hi;
		arr[lo++] = arr[hi];

		while (lo < hi && arr[hi] <= pivot) ++lo;
		arr[hi--] = arr[lo];
		
		
		
	}
	arr[lo] = pivot;
    return lo;
}
//version B 勤于拓展，懒于交换。
//多次交换会使算法的不稳定性提高
int patration_advance(vector<int>& arr, int lo, int hi)
{

	int pivot = arr[lo];
	while (lo < hi)
	{
		while (lo < hi)
		{
			if (pivot < arr[hi]) hi--;
			else {
				arr[lo++] = arr[hi];
				break;
			}
		}
		while (lo < hi)
		{
			if (arr[lo] < pivot) lo++;
			else {
				arr[hi--] = arr[lo];
				break;
			}
		}
		arr[lo] = pivot;
		return lo;
	}
}
//LGU version
//G 向前滚动 不稳定
int patration_LGU(vector<int>& arr, int lo, int hi)
{

	int pivot = arr[lo];
	int mi = lo;
	for (int k = lo + 1; k <= hi; k++)
	{
		if (arr[k] < pivot)
		{
			swap(arr, ++mi, k);
		}
		
	}
	swap(arr, lo, mi);
	return mi;
}
//众数检验  
bool majEleCheck(vector<int>& arr, int maj)
{
	int occurrence = 0;
	for (int i = 0; i < arr.size(); i++)
	{
		if (arr[i] == maj)
		{
			occurrence++;
		}
	}
	return 2 * occurrence > arr.size();
}

void quickSort(vector<int>& arr, int lo, int hi)
{
	if (hi - lo <= 1) return;
	int pivot = partation(arr, lo, hi - 1);//partation为上述三种算法中的一种
	quickSort(arr, lo, pivot);
	quickSort(arr, pivot + 1, hi);

}
//k-选择的特例，众数选取，而众数一般为中位数
int majEleCandidate(vector<int>& arr)
{
	int maj;
	for (int c = 0, i = 1; i < arr.size(); i++)
	{
		if (0 == c)
		{
			maj = arr[i];
			c = 1;
		}
		else
		{
        maj == arr[i] ? c++ : c--;
		}
	}
	return maj;
}
bool majority(vector<int>& arr, int& maj)
{
	maj = majEleCandidate(arr);
	return majEleCheck(arr, maj);
}

//基于quicksort的k选取
//rank(pivot)=k则中，
//rank(pivot)<k,则将范围缩减到  rank(pivot)+1，hi
//rank(pivot)>k,则将范围缩减到  lo < rank(pivot)-1
void k_select_base_on_quickSort(vector<int>& arr, int k)
{
	for (int lo = 0, hi = arr.size() - 1; lo < hi;)
	{
		int i = lo, j = hi;
		int pivot = arr[lo];
		while (i < j)
		{
			while (i < j && pivot <= arr[j]) j--;
			arr[i] = arr[j];
			while (i < j && arr[i] <= pivot)i++;
			arr[j] = arr[i];
		}
		
		arr[i] = pivot;
		if (k <= i) hi = i - 1;
		if (i <= k) lo = i + 1;
	}


}
int main()
{



	return 0;
}