数据结构学习笔记（C++）：七种简单排序方法的代码整合

数据结构学习笔记（C++）：七种简单排序方法的代码整合 原理详见：

数据结构学习笔记：排序算法总结_代码骑士的博客-CSDN博客https://blog.csdn.net/qq_51701007/article/details/121467175?spm=1001.2014.3001.5501

 代码整合：

#include
#define MAXSIZE 100
using namespace std;

class Sort
{
public:
	Sort(int* a, int n);
	~Sort();
	void Insert();
	void Shell();
	void Bubble();
	void simpleSelect();
	int Partition(int first, int last);//快排划分
	void Quick(int first, int last);
	void  Sift(int k, int last);//堆调整
	void Heap();//堆排序
	void Merge(int first1, int last1, int last2);//归并1
	void Merge1(int first, int last);//递归
	void mergePass(int h);//归并2
	void Merge2();//归并非递归
	void Print();
private:
	int a[MAXSIZE];
	int length;
};

Sort::Sort(int*Data,int n)
{
	length = n;
	for (int i = 0; i < length; i++)
		a[i] = Data[i];
}
Sort::~Sort()
{

}
void Sort::Insert()//a是待排数组，aLen是待排数组长度
{
	for (int i = 1; i < length; i++)//从下标1开始，因为下标0默认排好
	{
		int temp = a[i];//摸牌手抓牌

		for (int j = i - 1; j >= 0 && temp < a[j]; j--)
		{
			a[j + 1] = a[j];//把比temp大的数依次往后移动一位
			//cout << a[j] << ' ';
			a[j] = temp;//将temp插入到原a[j]的位置
		}
	}
}

void Sort::Shell()
{
	int i = 0, j = 0, d, temp;//设置增量与暂存值

	for (d = length / 2; d >= 1; d = d / 2)//增量为d进行直接插入排序，增量 = 1，进行的是最后一次插入
	{
		for (i = d; i < length; i++)//进行一趟希尔排序
		{
			temp = a[i];//抓牌

			for (j = i - d; j >= 0 && temp < a[j]; j = j - d)
			{
				a[j + d] = a[j];//后移
				cout << a[j] << ' ';
				a[j] = temp;//空出来的位置插入temp
			}
		}
	}
}

void Sort::Bubble()
{
	int temp;//交换时的临时存储变量

	for (int i = 1; i <= length - 1; i++)//总趟数：n-1
	{
		for (int j = 0; j < length - i; j++)//每进行一趟就排好一个，那么每次相邻比较的次数就是aLen - i次
		{
			if (a[j] > a[j + 1])
			{
				cout << a[j + 1] << ' ';
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

void Sort::simpleSelect()
{
	int index, temp;

	for (int i = 0; i < length - 1; i++)//进行n-1次选择
	{
		index = i;//待排序列的首元素下标

		for (int j = i + 1; j < length; j++)//在无序数列中选择一个最小的
		{
			if (a[j] < a[index])//indext表示最小元素下标（是随无序数列中j变化的）
				index = j;//找到最小值下标（这是一个过程……）
		}
		if (index != i)
		{
			temp = a[index];
			a[index] = a[i];
			a[i] = temp;
		}
	}
}

int Sort::Partition(int first, int last)//快排划分
{
	int i = first, j = last, temp;
	
	while (i < j)
	{
		while (i < j && a[i] <= a[j]) j--;
		if (i < j)
		{
			temp = a[i];//Swap
			a[i] = a[j];
			a[j] = temp;
			cout << a[i] << ' ';
			i++;//前游标后移
		}
		while (i < j && a[i] <= a[j]) i++;
		if (i < j)
		{
			temp = a[i];//Swap
			a[i] = a[j];
			a[j] = temp;
			cout << a[j] << ' ';
			j--;//后游标前移
		}
	}
	return i;//返回轴值位置
}

void Sort::Quick(int first, int last)
{
	int pivot;//定义轴值
	if (first >= last) return;
	else
	{
		pivot = Partition(first, last);
		
		Quick(first, pivot-1);

		Quick(pivot+1,last);
	}
}

void  Sort::Sift(int k, int last)//堆调整
{
	int i, j, temp;
	i = k; j = 2 * i + 1;
	while (j <= last)
	{
		if (j < last && a[j] < a[j + 1])j++;//j指向孩子中最大的结点
		if (a[i] > a[j])break;//符合堆性质，结点所在子树不用调整
		else
		{
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i = j;
			j = 2 * i + 1;
		}
	}
}

void Sort::Heap()//堆排序
{
	int i, temp;
	for (i = ceil(length / 2) - 1; i >= 0; i--)//ceil()取整函数
	{
		Sift(i, length - 1);
	}
	for (i = 1; i < length; i++)
	{
		temp = a[0];
		a[0] = a[length - i];
		a[length - i] = temp;
		Sift(0, length - i - 1);
	}
}


void Sort::Merge(int first1, int last1, int last2)//归并1
{
	int* temp = new int[length];
	int i = first1, j = last1 + 1, k = first1;
	while (i <= last1 && j <= last2)
	{
		if (a[i] <= a[j])temp[k++] = a[i++];
		else temp[k++] = a[j++];
	}
	while (i <= last1)
		temp[k++] = a[i++];
	while (j <= last2)
		temp[k++] = a[j++];
	for (i = first1; i <= last2; i++)
		a[i] = temp[i];
	delete[]temp;
}

void Sort::Merge1(int first,int last)//递归
{
	if (first == last) return;//自顶向下只有一个记录时，排序结束
	else
	{
		int mid = (first + last) / 2;
		Merge1(first, mid);//归并排序前半个
		Merge1(mid + 1, last);//归并排序后半个
		Merge(first, mid, last);//合并成一个
	}
}

void Sort::mergePass(int h)//归并2
{
	int i = 0;
	while (i + 2 * h <= length)
	{
		Merge(i, i + h - 1, i + 2 * h - 1);
		i = i + 2 * h;
	}
	if(i+h> n;

	cout << "输入待排元素：" << endl;
	for (int i = 0; i < n; i++)
		cin >> Data[i];

	Sort Sor(Data, n);

	cout << "选择排序方式：" << endl;
	cout << "1-插入排序" << endl;
	cout << "2-希尔排序" << endl;
	cout << "3-冒泡排序" << endl;
	cout << "4-快速排序" << endl;
	cout << "5-简单选择排序" << endl;
	cout << "6-堆排序" << endl;
	cout << "7-归并排序" << endl;
	int flag = 0;

	cin >> flag;

	switch (flag)
	{
	case 1:Sor.Insert();
		break;
	case 2:Sor.Shell();
		break;
	case 3:Sor.Bubble();
		break;
	case 4:Sor.Quick(0, n - 1);
		break;
	case 5:Sor.simpleSelect();
		break;
	case 6:Sor.Heap();
		break;
	case 7:Sor.Merge2();
		break;
	}

	cout << "排完的序列为：" << endl;

	Sor.Print();

	return 0;
}

 运行结果：