归并排序，快速排序，堆排序(小数之和，TOPK问题。。)

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

• 前言
• 一、小数和(归并)
• 二、快速排序
• • 3.ToK(堆）
• 总结

#define _CRT_SECURE_NO_WARNINGS 1
#include
using std::cout;
using std::cin;
bool is_true(int* nums, int* ret, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (nums[i] != ret[i])
		{
			return false;
		}
	}
	return true;
}
void merge(int* nums, int left, int mid, int right)
{
	if (left >= right)
	{
		return;
	}
	int* ret = (int*)malloc(sizeof(int) * (right - left + 1));
	int i = left;
	int j = mid + 1;
	int indx = 0;
	while (i <= mid && j <= right)
	{
		nums[i] < nums[j] ? ret[indx++] = nums[i++] : ret[indx++] = nums[j++];
	}
	while (i <= mid)
	{
		ret[indx++] = nums[i++];
	}
	while (j <= right)
	{
		ret[indx++] = nums[j++];
	}
	memcpy(nums + left, ret, sizeof(int) * (right - left + 1));
	free(ret);
}
//递归版本
void process1(int* nums, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int mid = (left + right) >> 1;
	process1(nums, left, mid);
	process1(nums, mid + 1, right);
	merge(nums, left, mid, right);

}
//非递归版本
void process2(int* nums, int left, int N)
{
	int MergSize = 1;
	//循环不变量：进行merge的左边,右边都是有序的。
	while (MergSize < N)
	{
		int i = 0;
		while (i < N)
		{
			//左组i....mid
			int mid = i + MergSize - 1;
			if (mid >= N)
			{
				break;
			}
			//右组mid+1....right
			int right = fmin(N - 1, mid + MergSize);
			merge(nums, i, mid, right);
			i = right + 1;
		}
		if (MergSize > N / 2)
		{
			break;
		}
		MergSize <<= 1;
	}
}
//题目1.在一个个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和，求数组小和
//如:
//例子: [1,3,4,2,5]
//1左边比1小的数:没有
//3左边比3小的数: 1
//4左边比4小的数: 1、3
//2左边比2小的数: 1
//5左边比5小的数: 1、 3、4、2
//所以数组的小和为1+1+3+1+1+3+4+2=16
int merge1(int* nums, int left, int mid, int right)
{
	if (left >= right)
	{
		return 0;
	}
	int count = 0;
	int* ret = (int*)malloc(sizeof(int) * (right - left + 1));
	int i = left;
	int j = mid + 1;
	int indx = 0;
	while (i <= mid && j <= right)
	{
		if (nums[i] < nums[j])
		{
			ret[indx++] = nums[i++];
			count =count+ (right - j + 1)*nums[i-1];
		}
		else
		{
			ret[indx++] = nums[j++];
		}
	}
	while (i <= mid)
	{
		ret[indx++] = nums[i++];
	}
	while (j <= right)
	{
		ret[indx++] = nums[j++];
	}
	memcpy(nums + left, ret, sizeof(int) * (right - left + 1));
	free(ret);
	return count;
}

int process3(int* nums, int left, int right)//改动版本
{
	if (left >= right)
	{
		return 0;
	}
	int mid = (left + right) >> 1;
	return process3(nums, left, mid)
		+ process3(nums,mid+1, right)
		+ merge1(nums, left,mid, right);
}
int main()
{
	//int n = 1000;
	int n = 5;
	int nums[5] = { 1,3,4,2,5};
	int a	= process3(nums, 0, 4);
	printf("%d", a);
}

#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include
using std::cin;
using std::cout;
using std::endl;
void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
int GetMid(int* nums, int left, int right)//三数取中
{
	int mid = (left + right) / 2;
	if (nums[left] > nums[right])
	{
		if (nums[mid] <= nums[right])
		{
			return nums[right];
		}
		if (nums[mid] >= nums[left])
		{
			return nums[left];
		}

	}
	else if (nums[left] <= nums[right])
	{
		if (nums[mid] >= nums[right])
		{
			return nums[right];
		}
		if (nums[mid] <= nums[left])
		{
			return nums[left];
		}
	}
	return nums[mid];
}
int process(int* nums, int left, int right)
{
	if (left >= right)
	{
		return left;
	}
	int target = GetMid(nums, left, right);     //快排优化,三数取中,使区间划分更加的均衡
	int i = left - 1;
	int j = right + 1;
	int indx = left;
	while (indx < j)
	{
		if (nums[indx] < target)
		{
			swap(&nums[indx++], &nums[++i]);
		}
		else if (nums[indx] == target)
		{
			indx++;
		}
		else
		{
			swap(&nums[--j], &nums[indx]);
		}
	}
	return i + 1;
}
void QucikSort(int* nums, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int m = process(nums, left, right);
	QucikSort(nums, left, m - 1);//区间[left,m-1]
	QucikSort(nums, m + 1, right);//区间[m+1,right]
}
int main()
{
	int nums[] = { 6,2,1,5,4,-1,3,4,2,12,3,-213,0 ,23,1,32,321 };
	int n = 17;

	QucikSort(nums, 0, n - 1);
	for (int i = 0; i < n; i++)
	{
		printf("%dn", nums[i]);
	}
}

#define _CRT_SECURE_NO_WARNINGS 1
#include
using std::cout;
using std::cin;
using std::endl;
void swap(int& a, int& b)
{
	if (&a == &b)
	{
		return;
	}
	a = a ^ b;
	b = b ^ a;
	a = b ^ a;
}
void HeapDown(int* nums,int indx,int n)//向下调整
{
	int i = indx;//当前节点
	int leftChild = i * 2 + 1;//左孩子
	while (leftChild < n)
	{
		leftChild = leftChild + 1 < n && nums[leftChild] > nums[leftChild + 1] ? leftChild + 1 : leftChild;
		if (nums[leftChild] >= nums[i])
		{
			break;
		}
		swap(nums[leftChild], nums[i]);
		i = leftChild;
		leftChild = i * 2 + 1;
	}

}
void HeapUp(int* nums,int indx,int n)//向上调整
{
	int i = indx;
	while ( nums[i]< nums[(i-1)/ 2])
	{
		swap(nums[i], nums[(i - 1) / 2]);
		i = (i - 1) / 2;
	}

}
//1.题目1
//已知一个几乎有序的数组。
//几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k， 并且k相对于数组长度来说是比较小的。
//请选择- -个合适的排序策略，对这个数组进行排序。
//2.题目2
//TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
//比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
//对于Top - K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
//
//用数据集合中前K个元素来建堆
//前k个最大的元素，则建小堆
//前k个最小的元素，则建大堆
//用剩余的N - K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
//
//将剩余N - K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
void HeapSort(int* nums, int n);
void test2()
{
	int n = 100000;
	int* nums = new int[n];
	for (int i = 0; i < n; i++)
	{
		nums[i] = rand() % n + 1;
	}
	//求最大前10个元素
	int k = 10;
	int* ret = new int[k];
	for (int i = 0; i < k; i++)
	{
		ret[i] = nums[i];
		//HeapUp(ret, i, k);
	}
	for (int i = 0; i
		HeapUp(ret, i, k);
	}
	//建小堆
	for (int i = k ; i < n; i++)
	{
		if (nums[i] > ret[0])
		{
			ret[0] = nums[i];
			HeapDown(ret, 0, k);
		}
	}
	HeapSort(ret, k);
	for (int i = 0; i < k; i++)
	{
		printf("%dn", ret[i]);
	}

}
void HeapSort(int* nums, int n)
{
	for (int i = n - 1; i > 0; i--)
	{
		swap(nums[0], nums[i]);
		HeapDown(nums, 0, i);
	}
}
void test1()
{

	int nums[] = { 5,1,3,8,32,23,1,2,231,3,21,31,23,34,3,43,423,4,-1321,22913,213};
	int n = sizeof(nums) / sizeof(int);
	for (int i = n-1; i >=0; i--)
	{
		HeapDown(nums, i,n);
	}//建堆
	for (int i = n-1; i>0; i--)
	{
		swap(nums[0], nums[i]);
		HeapDown(nums, 0, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%dn", nums[i]);
	}

}
//题目1:
int main()
{
	test2();
}