快速排序和堆排序

/ C++ / 没有评论 / 392浏览

快速排序使用分治法来把一个序列分为小于基准值和大于基准值的两个子序列。递归地排序两个子序列,直至最小的子序列长度为0或者1,整个递归过程结束,详细步骤为:

#include <stdio.h>

void exchange(int *p, int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

int quickSort(int arr[],int left, int right)
{
	if (left >= right)
	{
		return 0;
	}
	int i, j, temp;
	temp = arr[left];
	i = left;
	j = right;
	while (i != j)
	{
		while (i < j && arr[j] >= temp)
		{
			j--;
		}
		exchange(&arr[i], &arr[j]);
		while (i < j && arr[i] <= temp)
		{
			i++;
		}
		exchange(&arr[i], &arr[j]);
	}	
	quickSort(arr,i + 1, right);
	quickSort(arr,left, i - 1);
	return 1;
}

int main()
{
	int arr[9] = { 5,1,4,6,7,4,3,5,11 };

	quickSort(arr,0, 8);
	for (int i = 0; i <= 8; i++)
	{
		printf("%d ", arr[i]);
	}
	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;
}