Implementation of heap sort and quick sort principle

"I love computer technology"

                                                                                 ----2021.8.25

Heap sort :

#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)
	{
		// Avoid array length out of bounds , Do not execute if it exceeds the limit 
		assert(_count + 1 <= capacity);
		data[_count + 1] = item;
		_count++;
		// After insertion   May destroy the structure of the heap   So do the backtracking operation 
		percolate_up(_count);


	}
	// Considering the index location ,k Value must be greater than 1 Can have a parent node 
	void percolate_up(int k)
	{
		while (k > 0 && data[k / 2] < data[k])// Compare with its parent node , Make sure that the parent nodes are all large 
		{
			swap(data[k / 2], data[k]);
			k = k / 2;
		}
	}
	T extractMax()
	{
		assert(_count > 0);
		T ret = data[1];
		swap(data[1], data[_count]);// Delete the first   Let it swap with the first one 
		_count--;
		percolate_down(1);
		return ret;
	}
	void percolate_down(int k)
	{
		while (2 * k <= _count)
		{
			int j = 2 * k;
			// Select the largest of the left and right nodes 
			if (j + 1 <= _count && data[j + 1] > data[j])
			{
				j = j + 1;
			}
			if (data[k] >= data[j])
			{
				break;
			}
			// Exchange when you are younger than it 
			swap(data[k], data[j]);
			k = j;
		}
	}
};
// Push sort implementation 
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);// Enter your capacity 
	heapSort(a, 10);
	for (int i = 1; i <= 10; ++i)
	{
		cout << a[i] << " ";
	}
}

Quick sort :

#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)
	{
		// If key When the value is set to the leftmost   Be sure to start from right to left    Conversely, if key Value on the right   Search from right 
		while (v[j] >= base && i < j)// If decreasing, change to while(v[j]<=base&&i<j){j--;}
		{
			j--;
		}
		while (v[i] <= base && i < j)// If increasing, change to 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 << " ";
	}
}