快速排序和堆排序

只是方便记忆查看

快排:
#include <iostream>

using namespace std;

void sort(int *a, int left, int right)
{
	if (left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
	{
		return;
	}
	int i = left;
	int j = right;
	int key = a[left];

	while (i < j)                               /*控制在当组内寻找一遍*/
	{
		while (i < j && key <= a[j])
			/*而寻找结束的条件就是,1,找到一个小于或者大于key的数(大于或小于取决于你想升
			序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/
		{
			j--;/*向前寻找*/
		}

		a[i] = a[j];
		/*找到一个这样的数后就把它赋给前面的被拿走的i的值(如果第一次循环且key是
		a[left],那么就是给key)*/

		while (i < j && key >= a[i])
			/*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,
			因为排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/
		{
			i++;
		}

		a[j] = a[i];
	}

	a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
	sort(a, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
	sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
	/*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/
}

int main(int argc, char *argv[])
{
	int num[9] = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	int end = sizeof(num) / sizeof(int);
	sort(num, 0, end - 1);
	for (int i = 0; i < end; i++)
	{
		cout << num[i] << " ";
	}
	cout << endl;
	system("PAUSE");
	return 0;
}
堆排序:
#include <iostream>
#include <algorithm>
using namespace std;

void sink(int a[],int index,int n)
{
	int leftchild = 2*index + 1;//左节点下标
	int rightchild = 2*index +2;//右结点下标
	int present = index;//要调整的节点下标

	//下沉左边
	if(leftchild < n && a[leftchild] > a[present])
	{
		present = leftchild;
	}
	//下沉右边
	if(rightchild < n && a[rightchild] > a[present])
	{
		present = rightchild;
	}
	//如果下标不相等,证明被调换过了
	if(present != index)
	{
		int temp = a[index];
		a[index] = a[present];
		a[present] = temp;

		//继续下沉
		sink(a, present,n);
	}
}

void buildheap(int a[],int n)
{
	//堆是完全二叉树
	for(int i = n/2; i >= 0; i--)
	{
		sink(a,i,n);
	}
}

void sort(int a[],int n)
{
	//构建堆
	buildheap(a,n);
	for(int i = n - 1; i>0; i--)
	{
		//将堆顶元素与末位元素调换
		int temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		n--;//数组长度-1 隐藏堆尾元素
		sink(a,0,n);//将堆顶元素下沉 目的是将最大的元素浮到堆顶来
	}
}

int main()
{
	int data[8] = {4,6,3,2,1,5,8,0};
	int size = sizeof(data)/sizeof(int);
	sort(data,size);
	for(int i = 0; i < size; i++)
	{
		std::cout << data[i] << " ";
	}
	cout << endl;
	return 0;
}
暂无评论
发表新评论