关于排序的一些小问题

LongDz / 2023-07-30 / 原文

快速排序模板

void quick_sort(int a[],int l,int r)
{
if(l>=r)return;
int i = l - 1 , j =  r + 1;
x = q[l+r>>1];
while(i < j)
{
do i++ ; while (a[i]< x);
do j-- ; while(a[j] > x);
if(i < j) swap(a[i],a[j]);
quick_sort(a,l,j),quick_sort(a,j+1,r);
}
}

在手写快排的时候，经常犯的几个问题,问题代码

void quick_sort(int a[],int l,int r)
{
if(l>=r)return;
int i = l  , j =  r ;//这里直接跳转看while
x = l+r>>1;//这里就直接取中点位置，但要考虑到数组是在变化的
while(i <= j)//会死循环
{
 while (a[i]<= a[x]);i++ ;//这么写容易陷入无限循环，a[i]==a[x]时
 while(a[j] >= a[x]); j-- ;//一样的，还有注意,a[x]是可能会变得，如果swap设涉及到中点的数组那么，中间值就不一定是原数组了
if(i < j) swap(a[i],a[j]);
quick_sort(a,l,j-1),quick_sort(a,j,r);//q[j] <= x,就乱套了
}
}

归并排序模板

void merge_sort(int q[],int l,int r)
{
	if(l>=r)return;
	int mid = l + r >> 1;
	merge_sort(q,l,mid);merge_sort(q,mid+1,r);
	int i = l,k = 0,j = mid+1;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])tmp[k++]=a[i++];
        	else   tmp[k++]=a[j++];
	}
	 while(i<=mid)tmp[k++]=a[i++];
    	while(j<=r)tmp[k++]=a[j++];
    	for( i = l,j =0;i<=r;i++,j++) a[i]=tmp[j];
}

归并排序就是先分区间在和区间