快速排序算法及多线程试验

1）快速排序算法

算法实现：
选定一个起点/终点位置上的数A
小于数A的放在A左侧，大于的放在右侧
对A左侧和右侧数组递归的执行步骤2

// 分区函数
template<typename T>
int partition(T arr[], int length) {

	if (length <= 1)
		return 1;

	int i = 1;
	int j = length - 1;
	//select first
	T* pivot = arr;
	if (length == 2)
	{
		if (arr[0] > arr[1])
			std::swap(arr[0], arr[1]);
		return 1;
	}
	for (; i < j;)
	{
		while (i < j && arr[j] > *pivot)
		{
			j--;
		}
		if (i < j && arr[j] < *pivot)
		{
			std::swap(arr[j], *pivot);
			pivot = arr + j;
		}
		while (i < j && arr[i] < *pivot)
			i++;
		if (i < j && arr[i] > *pivot)
		{
			std::swap(arr[i], *pivot);
			pivot = arr+i;
		}
	}

	return i;

}

template<typename T>
void quickSort(T arr[], int length)
{
	if (length <= 1)
	{
		std::cout << *arr << std::endl;
		return;
	}
	
	else {
		int val = partition(arr, length);
		printarr(arr, length);
		
		quickSort(arr, val);
		quickSort(arr + val+1, length - val-1);
	}

}

2)上述快排算法实现了类型无关（模板实现），但其依赖于数组【】存储类型实现

问题：如何编写无关存储类型的快排？（兼容数组，vector,list等存储类型）

template<typename Iterator>
Iterator partition(Iterator begin, Iterator end)
{
    Iterator i = begin;
    //select end value
    auto val = *end;
    for (Iterator j=begin;j!=end;j++)
    {
        if (*j < val)
        {
            std::swap(*i, *j);
            i++;
            //printarr(begin, std::next(end));
        }
    }
    std::swap(*end, *i);
    //printarr(begin, std::next(end));
    return i;

}

template<typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
    if (begin == end)
        return ;
    else {
        Iterator val = partition(begin, end);
        if(val!=begin)
            quick_sort(begin, std::prev(val));
        if (val != end)
            quick_sort(std::next(val), end);
    }
    printarr(begin, std::next(end));
}

根据容器首尾指针进行排序，可兼容普通数组和容器

3）使用std中的分区算法std::partition？

较为丑陋的一种实现

template<typename Iterator>
void quick_sort(Iterator begin, Iterator end)
{
    if (begin == end)
        return ;
    if (std::distance(begin, end) <= 2)
    {
        auto value = *begin;
        Iterator val = std::partition(begin, end, [value](auto& a) {
            return a < value;
        });
        return;
    }

    else {
        //Iterator val = partition(begin, end);
        printarr(begin, end);
        auto value = *begin;
        Iterator val = std::partition(begin, end, [value](auto& a) {
            return a < value;
        });
        printarr(begin, end);


        quick_sort(begin, val); 
        if (val == begin)
            val++;
        quick_sort(val, end);
    }
    printarr(begin, end);
}

std::partition和自己实现的分区函数区别：
自定义分区函数会以选定分区值为节点，左侧小，右侧大
std分区函数以一个迭代器为标志，迭代器左侧小于，迭代器到尾迭代器大于等于选定分区值

std分区函数接收的第二个迭代器是尾迭代器（指向容器最后一个元素的下一个元素）

4） 如何使用多线程优化快排的速度？
经过测试，在万级的容器上，反而单线程快排速度较快，
不知道有什么说法