快速排序三指针分区法
有相同元素值的快速排序——三分法三分法有三个指针，一个向右扫描比主元小的元素指针，
一个记录与主元相等元素的指指，另一个是从右向左扫描
比主元大的元素指针。
将数组分为四个区，小于主元区，等于主元区，未知区，
与大于主元区 #include <iostream>
using namespace std;
void swap(int arr[], int a, int b)
{
int temp = arr;
arr = arr;
arr = temp;
}
void quick_sort(int arr[], int left, int right)
{
if(left >= right)
return;
int e = left + 1; //记录等于主元的指针
int sp = left + 1; //扫描小于主元元素指针
int bigger = right; //扫描大于主元元素指针
int pivot = arr; //主元
while(sp <= bigger)
{
while(sp <= bigger && arr < pivot)
{
e++;
sp++;
}
while(sp <= bigger && arr == pivot)
{
swap(arr, e, sp);
e++;
sp++;
}
while(sp <= bigger && arr > pivot)
bigger--;
if(sp < bigger)
swap(arr, bigger, sp);
}
swap(arr, bigger, left);
quick_sort(arr, left, bigger-1);
quick_sort(arr, bigger+1, right);
}
int main()
{
int arr = {5, 1, 2, 4, 3, 6, 1, 1, 2, 2};
quick_sort(arr, 0, 9);
for(int i = 0; i<10; i++)
cout << arr << "\t";
return 0;
}
页:
[1]