排序算法
void quick_sort(int a[],int left,int right)
{
int i=left+1,j=right+1;
int key=a[left];
if(left >=right) return ;
while(1)
{
while(a[j] > key) j--;
while(a[i] < key && i<j) i++;
if(i >= j) break;
swap(&a[i],&a[j]);
if(a[i] == key)
j--;
else
i++;
}
swap(&a[left],&a[j]);
if(left <i-1)
quick_sort(a,left,i-1);
if(j+1<right)
quick_sort(a,j+1,right);
}
int main()
{
int a[]={0,-1,11,-14,5,15,-4,14};
int size=sizeof(a)/sizeof(a[0]);
printf("size:%d\n",size);
quick_sort(a,0,size);
printf("size:%d\n",size);
for (int i=0;i<size;i++)
printf("%d\t",a[i]);
printf("\n");
return 0;
}
输出size的值，为什么调用quick_sort后size的值改变了，数组a中又增加了一些无意思的数据
-14 -4 -1 0 5 8 11 14 15 9 -1076835776 -1076835688 1699484 1576096 134514176 -1076835688 1699484 1 -1076835644 -1076835636 1579048
而size的值变为15
算法，内存
[解决办法]
void quick_sort(int a[],int left,int right)
{
int i=left,j=right;//不需要+1
int key=a[left];
if(left >=right) return ;
while(1)
{
while(a[j] > key && i<j) j--;//这里最好补上i<j
while(a[i] < key && i<j) i++;
if(i >= j) break;
swap(&a[i],&a[j]);
if(a[i] == key)
j--;
else
i++;
}
a[j]=key;//这句写错了，不是swap，是赋值
if(left <i-1)
quick_sort(a,left,i-1);
if(j+1<right)
quick_sort(a,j+1,right);
}
int main()
{
int a[]={0,-1,11,-14,5,15,-4,14};
int size=sizeof(a)/sizeof(a[0]);
printf("size:%d\n",size);
quick_sort(a,0,size-1);//参数传递错误，下标是0 - size-1
printf("size:%d\n",size);
for (int i=0;i<size;i++)
printf("%d\t",a[i]);
printf("\n");
return 0;
}
void QuickSort(Type a[], int left, int right)
{
if(left < right)
{
int i = left, j = right, key = a[left];
do{
while(i < j && a[j] >= key)
j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] < key)
i++;
if(i < j) a[j--] = a[i];
}while(i != j);
a[i] = key;
QuickSort(a, left, i-1);
QuickSort(a, i+1, right);
}
}
