三路快速排序算法

 1 /**************************************三路快速排序算法实现***********************************/
 2 template<typename T>
 3 void __quickSort3Ways (T arr[], int left, int right)
 4 {
 5     if (right - left <= 40) {                  /* 对递归到数据量较小时使用插入排序 */
 6         __insertSortMG<T>(arr, left, right);
 7         return;
 8     }
 9 
10     std::swap(arr[left], arr[std::rand() % (right - left + 1) + left]);  // 随机化找到一个元素作为"基准"元素 
11     T v = arr[left];
12 
13     int lt = left;       // 将<v的分界线的索引值lt初始化为第一个元素的位置（也就是<v部分的最后一个元素所在位置）
14     int gt = right + 1;  // 将>v的分界线的索引值gt初始化为最后一个元素right的后一个元素所在位置（也就是>v部分的第一个元素所在位置）     
15     int i = left + 1;    // 将遍历序列的索引值i初始化为 left+1
16     
17     while (i < gt) {     // 循环继续的条件
18         if (arr[i] < v) {
19             std::swap(arr[i], arr[lt + 1]);  // 如果当前位置元素<v，则将当前位置元素与=v部分的第一个元素交换位置 
20             i++;                             // i++  考虑下一个元素
21             lt++;                            // lt++  表示<v部分多了一个元素
22         }
23         else if (arr[i] > v) {               // 如果当前位置元素>v，则将当前位置元素与>v部分的第一个元素的前一个元素交换位置
24             std::swap(arr[i], arr[gt - 1]);  // 此时i不用动，因为交换过来的元素还没有考虑他的大小
25             gt--;                            // gt--  表示>v部分多了一个元素
26         }
27         else {              //  如果当前位置元素=v   则只需要将i++即可，表示=v部分多了一个元素
28             i++;
29         }
30     }
31 
32     std::swap(arr[left], arr[lt]);   // 上面的遍历完成之后，将整个序列的第一个元素(也就是"基准"元素)放置到合适的位置 
33                                      // 也就是将它放置在=v部分即可
34     __quickSort3Ways<T>(arr, left, lt - 1); // 对<v部分递归调用__quickSort3Ways函数进行三路排序
35     __quickSort3Ways<T>(arr, gt, right);    // 对>v部分递归调用__quickSort3Ways函数进行三路排序
36 }
37 
38 template<typename T>
39 void quickSort3Ways (T arr[], int count)
40 {
41     std::srand(std::time(NULL));               /* 种下随机种子 */
42     __quickSort3Ways<T>(arr, 0, count - 1);    /* 调用__quickSort3Ways函数进行三路快速排序 */
43 }
44 /***********************************************************************************************/