思想
确定主元素，利用主元素进行数组划分，小于主元素的元素在主元素左边，大于主元素的在右边，利用递归排序。这里用到了分治思想
代码一
int partition(int a[], int p, int q)
{
int pivot = a[p];
int i = p;
int j = i + 1;
int temp;
while (j <= q)
{
if(pivot > a[j])
{
temp = a[i+1];
a[i+1] = a[j];
a[j] = temp;
i++;
}
j++;
}
temp = a[i];
a[i] = a[p];
a[p] = temp;
return i;
}
void Quick_sort(int a[],int p,int q)
{
if (p < q)
{
int i = partition(a,p,q);
Quick_sort(a,p,i-1);
Quick_sort(a,i+1,q);
}
}
int main(void)
{
int a[] = {2,3,1,7,6,5,0};
int p = 0;
int q = sizeof(a) / sizeof(int) - 1;
Quick_sort(a,p,q);
int i;
for(i=0;i<=q;i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
代码二
//平均时间复杂度 O(NlogN)
#include<stdio.h>
int partition(int *a, int L, int R)
{
int i = L;
int j = R;
int x = a[L];
while(i < j)
{
//从右往左找出比x小的元素
while (i < j && a[j] > x)
j--;
if (i < j)
a[i++] = a[j];
//从左往右找出比x大的元素
while ( i < j && a[i] < x)
i++;
if(i < j)
a[j--] = a[i];
}
//将主元素插入
a[i] = x;
return i;
}
void Quick_sort(int * a,int L, int R)
{
if (L < R)
{
int p = partition(a,L,R);
Quick_sort(a ,L,p - 1);
Quick_sort(a,p + 1,R);
}
}
int main(void)
{
int a[] = {4,4,4,4,4,4,4};
int L = 0;
int R = sizeof(a) / sizeof(int) - 1;
Quick_sort(a,L,R);
int i;
for(i = 0;i <= R; i++)
printf("%d ",a[i]);
printf("\n");
return 0;
}
