数据结构之快速排序算法

快速排序的思想

• ​设置两个变量i、j，排序开始的时候：令i=0，j=length-1；
• ​以第一个数组元素作为比较，赋值给temp，即temp=nums[0]；
• ​从j开始向前扫描，找到第一个小于temp的值nums[j]，将nums[j]和nums[i]的值交换；
• 从i开始向后扫描，找到第一个大于temp的值nums[i]，将nums[i]和nums[j]的值交换；
• 重复第3、4步，直到i==j，将枢轴元素移到正确位置上，即将nums赋值给nums[i]。

快速排序的递归实现

int partition(int* nums, int left, int right)
{
	int temp = nums[left];
	while (left < right) 
	{
		while (left < right && temp < nums[right])right--;
		if (left < right)nums[left] = nums[right];
		while (left < right && nums[left] <= temp)left++;
		if (left < right)nums[right] = nums[left];
	}
	nums[left] = temp;
	return left;
}

void quitSort(int* nums, int left, int right)
{
	if (left < right)
	{
		int mid = partition(nums, left, right);
		quitSort(nums, left, mid - 1);
		quitSort(nums, mid + 1, right);
	}
}

int main()
{
	int nums[] = { 56,23,78,45,90,89,12,34,56,67,89,100 };
	int n = sizeof(nums) / sizeof(nums[0]);
	quitSort(nums, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%2d ", nums[i]);
	}
}

快速排序的非递归实现

void PrintInt(int* ar, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%5d", ar[i]);
	}
	printf("\n");
}

int partition(int* nums, int left, int right)
{
	int temp = nums[left];
	while (left < right)
	{
		while (left < right && temp < nums[right])right--;
		if (left < right)nums[left] = nums[right];
		while (left < right && nums[left] <= temp)left++;
		if (left < right)nums[right] = nums[left];
	}
	nums[left] = temp;
	return left;
}

//借助队列或者栈进行操作
void QuitSort(int* nums, int left, int right)
{
	std::queue<int>qu;
	qu.push(left);
	qu.push(right);

	while (!qu.empty())
	{
		int sleft = qu.front(); qu.pop();
		int sright = qu.front(); qu.pop();
		int mid = partition(nums, sleft, sright);
		if (sleft < mid)
		{
			qu.push(sleft);
			qu.push(mid-1);
		}
		else if(mid<sright)
		{
			qu.push(mid+1);
			qu.push(sright);
		}
	}
}

int main()
{
	int ar[] = { 56,23,78,45,90,89,12,34,56,67,89,100 };
	int n = sizeof(ar) / sizeof(ar[0]);
	PrintInt(ar, n);
	QuitSort(ar, 0, n - 1);
	PrintInt(ar, n);
	return 0;
}