快速排序，對於相同元素的優化，c++
#include<iostream>
using namespace std;
void middl(int &p,int &q,int &r)//找樞軸，然後把樞軸位置都換到第一位,左中右，取中值，放在左邊第一個
{
if((p <= q && q <= r) || (r <= q && q <= p))
{
int term;
term = p;
p = q;
q = term;
}
else
if((r <= q && p<= r) || (q <= r && r <= p))
{
int term;
term = p;
p = r;
r = term;
}
}
void quicksort(int *a,int L,int R)//和樞軸相同的數可以和樞軸放一起來縮小下次快排的規模
{
if (L < R)
{
int mid = (L + R)/2;
middl(a[L],a[mid],a[R]);
int count1 = L, count2 = R;
int i = L, j = R, key = a[L];
while (i < j)//一趟快排的總控制
{
while (i < j && a[j] > key)j--;//控制j從後往前找第一比key小的
while (i < j)
{
if (a[j] == key)//在右邊找到和樞軸相同的數放到陣列最右端
{
int term;
term = a[count2];
a[count2] = a[j];
a[j] = term;//在右邊找到和樞軸相同的數放到陣列最右端
count2 --;
j--;
while (i < j && a[j] > key)j--;//找到和key相同的數移動後還要繼續找比key小的
}
else
{
a[i++] = a[j];//因為軸值已經記錄為key，而a[0]為軸值
break;//加個break是為了一旦找到比key值小的就不再迴圈
}
}
while (i < j && a[i] < key)i++;//控制i從右往左找第一個比key大的
while (i < j)
{
if(a[i] == key)//在左邊找到的和key相同的值放到陣列最左端
{
int term;
term = a[count1];
a[count1] = a[i];
a[i] = term;//在左邊找到的和key相同的值放到陣列最左端
count1 ++;
i++;
while (i < j && a[i] < key)i++;
}
else
{
a[j--] = a[i];
break;
}
}
}
a[i] = key;//現在a[i]裡面值並不是key而是最近比key大或者小的值，但是已經賦值給了i或者j最近變動的地方，所以要複製key，也沒有事情
int pivot = i;//用一個變數儲存當前樞軸位置，因為下邊ij都變了，
for(int t1 = L;t1 < count1;t1 ++)//最左邊與key值相同的數，與i左邊的值交換
{
int term;
term = a[--i];
a[i] = a[t1];
a[t1] = term;
}
//for(int t2 = count2;t2 < R;t2 ++)//這迴圈有錯，改後為
for(int t2 = R;t2 > count2;t2 --)//最左邊與key值相同的數，與i左邊的值交換
{
int term;
term = a[++j];
a[j] = a[t2];
a[t2] = term;
}
quicksort(a,L,pivot - count1 - 1 + L);
quicksort(a,pivot + R - count2 + 1,R);
}
}
int main()
{
int num;
cout<<"請輸入排序的規模！"<<endl ;
cin>> num;
int *a = new int[num];
int i;
for(i = 0;i < num;i++)
{
cin>>a[i];
}
cout<<"輸出原始陣列！"<<endl;
for(i = 0;i < num;i++)
{
cout<<a[i]<< " ";
}
cout<<endl;
quicksort(a,0,num - 1);
for(i = 0;i < num;i++)
{
cout<<a[i]<< " ";
}
cout<<endl;
return 0;
}