快速排序

下面通過示意圖來說明這種步驟思想

1、拿一個(gè)例子，把數(shù)組的第一個(gè)元素v作為分界的標(biāo)志點(diǎn) ，也稱為 "基準(zhǔn)"

2、進(jìn)行遍歷的過程也是將整個(gè)數(shù)組分成兩個(gè)部分的過程钾麸，比基準(zhǔn)值小的所有元素?cái)[放在基準(zhǔn)前面，比基準(zhǔn)值大的所有元素?cái)[在基準(zhǔn)的后面炕桨，因此這個(gè)過程要考慮這兩種情況饭尝，我們把當(dāng)前訪問的元素叫做e

2.1、如果當(dāng)前訪問的i位置元素 e<v,即比基準(zhǔn)值小的元素,此時(shí)應(yīng)該就把e放在小于基準(zhǔn)值v這部分后面,

把e放在小于v這范圍后, j++献宫，接著當(dāng)前訪問的位置 i++钥平，可以繼續(xù)討論下個(gè)位置元素

2.2、如果當(dāng)前訪問的i位置元素 e>v,即比基準(zhǔn)值大的元素姊途，此時(shí)應(yīng)該就把e放在大于基準(zhǔn)值v這部分后面

把e放在大于基準(zhǔn)值v這范圍后, 接著當(dāng)前訪問的位置 i++涉瘾，可以繼續(xù)討論下個(gè)位置元素

3、重復(fù)步驟2的操作捷兰，在這個(gè)數(shù)組遍歷完成后得到

4立叛、最后把數(shù)組 l位置和j位置交換，把基準(zhǔn)值v放到中間的位置贡茅，完成這個(gè)分區(qū)（partition）操作

5秘蛇、最后遞歸地把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序

具體實(shí)現(xiàn)

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);
}

總結(jié)：

三路快速排序

下面通過示意圖來說明這種步驟思想
三路快速排序的思想就是把整個(gè)數(shù)組分成三個(gè)部分 <v =v >v ,這個(gè)時(shí)候在遞歸的時(shí)候=v的部分就不需理會(huì)了其做，只需要考慮 < v 和 >v 部分進(jìn)行同樣的快速排序

分三種可能討論

1、 當(dāng)前追蹤位置元素 e == v 情況下
那么這個(gè)元素e赁还，直接納入==v 部分庶柿，相應(yīng)的 i++ 處理下一個(gè)元素

2、 當(dāng)前追蹤位置元素 e< v 情況下秽浇，那么這個(gè)元素e,納入<v部分的末端 lt 位置，此時(shí)lt+1位置元素與當(dāng)前 i 位置元素交換位置即可

相應(yīng)的索引lt++甚负，同時(shí)相應(yīng)的 i++ 處理下一個(gè)元素

相應(yīng)的索引gt--斑举，同時(shí)索引gt指向元素與當(dāng)前 i 指向的元素交換位置，那么追蹤的索引位置不需要指向下一個(gè)病涨， 處理下一個(gè)元素

具體實(shí)現(xiàn)

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);
}