快速排序: 不稳定
最优时间复杂度 : O(nlogn)
平均时间复杂度 : O(nlogn)
最差时间复杂度 : O(n ^ 2)
*/
#include
using namespace std;
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
int AdjustArray(int s[], int l, int r) //返回调整后基准数的位置
{
int i, j;
int x = s[r];
for (i = l - 1, j = l; j < r ;j++)
if (s[j] < x)
{
i++;
}
swap(s[i +1], s[r]);
return i+1;
}
void quickSort(int s[], int l, int r)
{
if (l < r)
{
int i = AdjustArray(s, l, r);//先成挖坑填数法调整s[]
quickSort(s, l, i - 1); // 递归调用
quickSort(s, i + 1, r);
}
}
int main(){
int r[8] = { 10, 3, 5, 1, 9, 34, 54, 565 };
quickSort(r, 0, 7);
for (int q = 0; q<8; q++)
cout << ' ' << r[q];
return 0;
}