堆排序和快速排序原理实现

"I love computer technology"

                                                                                 ----2021.8.25

堆排序:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include <assert.h>
using namespace std;
template<typename T>
class MaxHeap
{
private:
	T* data;
	int _count;
	int capacity;
public:
	MaxHeap(T cap)
	{
		data = new T[cap + 1];
		_count = 0;
		this->capacity = cap;
	}
	~MaxHeap()
	{
		delete[]data;
	}
	int size()
	{
		return _count;
	}
	bool isEmpty()
	{
		return _count == 0;
	}
	void insert(T item)
	{
		//避免数组长度越界,若越界则不执行
		assert(_count + 1 <= capacity);
		data[_count + 1] = item;
		_count++;
		//进行插入操作后 可能破坏堆的结构 所以进行上溯操作
		percolate_up(_count);


	}
	//考虑到索引位置的问题,k值必须大于1才能有父节点
	void percolate_up(int k)
	{
		while (k > 0 && data[k / 2] < data[k])//与其父节点进行比较，确保父节点都是大的
		{
			swap(data[k / 2], data[k]);
			k = k / 2;
		}
	}
	T extractMax()
	{
		assert(_count > 0);
		T ret = data[1];
		swap(data[1], data[_count]);//删除第一个 让它和第一个进行交换
		_count--;
		percolate_down(1);
		return ret;
	}
	void percolate_down(int k)
	{
		while (2 * k <= _count)
		{
			int j = 2 * k;
			//选取左右节点中最大的
			if (j + 1 <= _count && data[j + 1] > data[j])
			{
				j = j + 1;
			}
			if (data[k] >= data[j])
			{
				break;
			}
			//比它小就交换
			swap(data[k], data[j]);
			k = j;
		}
	}
};
//推排序实现
template<typename T1>
void heapSort(T1 arr[], int n)
{
	MaxHeap<T1> maxHeap = MaxHeap<T1>(n);
	for (int i = 0; i < n; i++)
	{
		maxHeap.insert(arr[i]);
	}
	for (int j = n - 1; j >= 0; j--)
	{
		arr[j] = maxHeap.extractMax();
	}

}
int main()
{

	int a[10] = { 3,5,2,4,9,10,11,13,16,2 };
	//heapSort(a, 10);//输入你的容量
	heapSort(a, 10);
	for (int i = 1; i <= 10; ++i)
	{
		cout << a[i] << " ";
	}
}

快速排序:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
template<class T>
void quickSort(int left, int right, vector<T>& v)
{
	if (left >= right) { return; }
	int i = left, j = right;
	int base = v[left];
	while (i < j)
	{
		//假如key值设置为最左侧时 一定要先从右往左  反之若key值在右侧 则从右往搜索
		while (v[j] >= base && i < j)//若递减则改为while(v[j]<=base&&i<j){j--;}
		{
			j--;
		}
		while (v[i] <= base && i < j)//若递增则改为whike(v[j]>=base&&i<j){i++}
		{
			i++;
		}
		swap(v[i], v[j]);
	}
	v[left] = v[i];
	v[i] = base;
	quickSort(left, i - 1, v);
	quickSort(i + 1, right, v);
}
int main()
{
	vector<int> v = { 6,1,2,7,9,3,4,5,10,8 };
	quickSort(0, v.size() - 1, v);
	for (auto it : v)
	{
		cout << it << " ";
	}
}