快速排序

下面通过示意图来说明这种步骤思想

1、拿一个例子，把数组的第一个元素v作为分界的标志点 ，也称为 "基准"

2、进行遍历的过程也是将整个数组分成两个部分的过程，比基准值小的所有元素摆放在基准前面，比基准值大的所有元素摆在基准的后面，因此这个过程要考虑这两种情况，我们把当前访问的元素叫做e

2.1、如果当前访问的i位置元素 e<v,即比基准值小的元素,此时应该就把e放在小于基准值v这部分后面,

把e放在小于v这范围后, j++，接着当前访问的位置 i++，可以继续讨论下个位置元素

2.2、如果当前访问的i位置元素 e>v,即比基准值大的元素，此时应该就把e放在大于基准值v这部分后面

把e放在大于基准值v这范围后, 接着当前访问的位置 i++，可以继续讨论下个位置元素

3、重复步骤2的操作，在这个数组遍历完成后得到

4、最后把数组 l位置和j位置交换，把基准值v放到中间的位置，完成这个分区（partition）操作

5、最后递归地把小于基准值元素的子数列和大于基准值元素的子数列排序

具体实现

template<typename T>
int __patrttion(T arr[],int l,int r)
{
    T v = arr[l];
    int j = l;
    for(int i=l+1;i<=r;i++)
    {
        if(arr[i] < v)
            swap(arr[j+1],a[i]);
        j++;
    }
    swap(arr[l],arr[j]);
    return j;
}

template<typename T>
void __quickSort(T arr[],int l,int r)
{
    if(l>=r)
        return;
    int p = __patrttion(arr,l,r);

    __quickSort(arr,l,p-1);
    __quickSort(arr,p+1,r);
}

总结：

三路快速排序

下面通过示意图来说明这种步骤思想
三路快速排序的思想就是把整个数组分成三个部分 <v =v >v ,这个时候在递归的时候=v的部分就不需理会了，只需要考虑 < v 和 >v 部分进行同样的快速排序

分三种可能讨论

1、 当前追踪位置元素 e == v 情况下
那么这个元素e，直接纳入==v 部分，相应的 i++ 处理下一个元素

2、 当前追踪位置元素 e< v 情况下，那么这个元素e,纳入<v部分的末端 lt 位置，此时lt+1位置元素与当前 i 位置元素交换位置即可

相应的索引lt++，同时相应的 i++ 处理下一个元素

相应的索引gt--，同时索引gt指向元素与当前 i 指向的元素交换位置，那么追踪的索引位置不需要指向下一个， 处理下一个元素

具体实现

template<typename T>
void __quickSort3Ways(T arr[],int l ,int r)
{
    if(r-l <= 15)
    {
        insertionTestSort(arr,l,r);
        return;
    }

    swap(arr[l],arr[rand()%(r-l+1)+1] );
    T v = arr[l];

    int lt = l;
    int gt = r+1;
    int i = l;
    while(i < gt)
    {
        if(arr[i] < v)
        {
            swap(arr[i],arr[lt+1]);
            i++;
            lt++;
        }
        else if(arr[i] > v)
        {
            swap(arr[i],arr[gt-1]);
            gt--;
        }
        else
        {
            i++;
        }
    }

    swap(arr[l],arr[lt]);
    __quickSort3Ways(arr,l,lt-1);
    __quickSort3Ways(arr,gt,r);
}

template<typename T>
void quickSort3Ways(T arr[],int n)
{
   srand(time(NULL));
    __quickSort3Ways(arr,0,n-1);
}