快速排序 《==》前后指针法

2023-12-28 11:46:43

1、快速排序：

快速排序是 Hoare 于 1962 年提出的一种二叉树结构的交换排序方法，其基本思想为： 任取待排序元素序列中
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止 。
快速排序目前有三个版本：
  • hoare 版本
  • 挖坑法
  • ???????前后指针法
本次是利用最后“前后指针版本”实现快速排序。
主要思想：
cur在探路找小
a[cur] < key
++prev
交换prev位置cur位置
1、最开始时prev和cur是相邻的
2、当cur遇到比key大的值以后，他们之间的值都是比key大的值
3、cur找小，找到小之后，跟++prev位置的值交换，相当于把大凡滚式往右边推同时把小的换到左边。 

// 前后指针法
// [left, right]
int PartSort3(int* a, int left, int right)
{
	

	int prev = left;
	int cur = left+1;
	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur) //++prev != cur意思是同位置没必要换，所以不等于时候要换
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

// 时间复杂度: O(logN*N)
// 空间复杂度：O(logN)

文章来源:https://blog.csdn.net/2301_78000015/article/details/135255704
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。