快速排序之三路快速排序

之前介绍了快速排序和优化版的快速排序

下面再来介绍一种 【三路快速排序】

【代码实现】

//三路快速排序
        template<typename T>
        static void quickSort3Ways(T arr[], int n)
        {
            __quickSort3Ways(arr, 0, n-1);
        }
        template<typename T>
        static void __quickSort3Ways(T arr[], int l, int r)
        {
            if( l >= r) return;
            int i = l + 1;
            int lt = l;
            int gt = r + 1;
            T v = arr[l];
            while(i < gt)
            {
                if(arr[i] == v)
                {
                    i++;
                }
                else if(arr[i] < v)
                {
                    swap(arr[lt + 1], arr[i]);
                    lt++;
                    i++;
                }
                else if(arr[i] > v)
                {
                    swap(arr[i], arr[gt - 1]);
                    gt--;
                }
            }
            swap(arr[l], arr[lt]);
            __quickSort3Ways(arr, l, lt - 1);
            __quickSort3Ways(arr, gt, r);
        }

           

【测试】