C++快速排序

C++快速排序 快速排序

• 双指针递归，假设以小明为目标，将其的成绩排名第几，在全班中求出
• i和j同时，一个往左，一个往右
• 如果key(小明的成绩) <(data[j]) 小于其他同学

while (i < j&&key < data[j])
		{
			j--;
		}

就将大于的成绩的同学的位置，原封不动，将其指针往左移动

直到，终于有一个不满足 key

得到一个同学的成绩是小于小明的，

那么

data[i] = data[j]; // 将当前小明的成绩的左边第一个位置开始放置第n个比小明成绩小的
// 也就是说，比小明成绩小的，放到i的一列

如果小明的成绩大于从左边起头的同学

while (i < j&&key >= data[i])
		{
			i++;
		}
data[j] = data[i];

阐述一下data[i]=data[j]和data[j]=data[i]的意思

以test数据为例

int arr[12] = { 23,64,24,12,9,16,53,57,71,79,87,97 };

16 9 12 23 24 64 53 57 71 79 87 97

排序后的第一次结果

将16 第一个比 23 小的数，挪移到了最左边第一个下标为0

将97 第一个比23 大的数，挪移到了最右边最后一个下标

这就是这两行代码的意义

int sort(int *data, int left, int right) {
	// 递归函数，找到哨兵
	if (left >= right)return 0;
	int i = left;
	int j = right;
	int key = data[left];
	// 相当于找到data的一个小明，这个小明成绩排名第几
	
	while (i < j)
	{
		while (i < j&&key < data[j])
		{
			j--;
		}
		// 凡是比小明成绩高的,j--,原封不动，往左边移动
		data[i] = data[j];
		while (i < j&&key >= data[i])
		{
			i++;
		}
		// 凡是比小明成绩低的，i++，原封不动，让游标往中间靠
		// 只要j和i指针相遇了，就必然不满足i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/4749743.html