【Practical】插入排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【Practical】插入排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1993字，纯文字阅读大概需要3分钟。

内容图文

#include <iostream>

using namespace std;

void Display(int *a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		cout << a[i] << " ";
	}
	cout << endl;
}

void Swap(int *x, int *y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

void BubbleSort1(int *a, int n)
{
	// Judge.
	if (n < 2)
	{
		return;
	}

	int tmp = 0;

	for (int i = n - 1; i > 0; --i)
	{
		bool isSwap = false;
		for (int j = 0; j < n - 1; ++j)
		{
			if (a[j] > a[j + 1])
			{
				tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				isSwap = true;
			}
		}
		if (isSwap == false)
		{
			return;
		}
	}
}

void BubbleSort2(int *a, int n)
{
	if (n < 2)
	{
		return;
	}

	bool isSwap = false;

	int tmp = 0;
	for (int j = 0; j < n - 1; ++j)
	{
		if (a[j] > a[j + 1])
		{
			tmp = a[j];
			a[j] = a[j + 1];
			a[j + 1] = tmp;
			isSwap = true;
		}
	}

	if (isSwap == false)
	{
		return;
	}

	BubbleSort2(a, --n);
}

void SelectionSort1(int *a,int n)
{
	if (n < 2)
	{
		return;
	}

	int left = 0;
	int right = n - 1;

	while (left < right)
	{
		int minpos = left;
		int maxpos = left;

		for (int i = left + 1; i <= right; ++i)
		{
			if (a[i] < a[minpos])
			{
				minpos = i;
			}
			else if (a[i] > a[maxpos])
			{
				maxpos = i;
			}
		}

		if (minpos != left)
		{
			Swap(&a[minpos], &a[left]);
		}

		if (maxpos == left)
		{
			maxpos = minpos;
		}

		if (maxpos != right)
		{
			Swap(&a[maxpos], &a[right]);
		}

		++left;
		--right;
	}
}

void SelectionSort2(int *a, int n)
{
	if (n < 2)
	{
		return;
	}

	int minpos = 0;
	int maxpos = 0;
	for (int j = 1; j < n; ++j)
	{
		if (a[j] < a[minpos])
		{
			minpos = j;
		}
		else if (a[j] > a[maxpos])
		{
			maxpos = j;
		}
	}

	if (minpos != 0)
	{
		Swap(&a[minpos], &a[0]);
	}

	if (maxpos == 0)
	{
		maxpos = minpos;
	}

	if (maxpos != n - 1)
	{
		Swap(&a[maxpos], &a[n - 1]);
	}

	SelectionSort2(a + 1, n - 2);
}

void InsertionSort(int *a, int n)
{
	if (n < 2)
	{
		return;
	}
	
	for (int i = 1; i < n; ++i)
	{
		int pos = i;
		for (int j = i - 1; j >= 0; --j)
		{
			if (a[j] > a[i])
			{
				pos = j;
			}
		}

		if (pos != i)
		{
			int tmp = a[i];
			for (int j = i - 1; j >= pos; --j)
			{
				a[j + 1] = a[j];
			}
			a[pos] = tmp;
		}

	}
}

int main()
{
	int arr[] = { 44,3,38,5,47,15,36,26,27,2,46,4,19,50,48 };
	int len = sizeof(arr) / sizeof(int);

	Display(arr, len);

	// BubbleSort1(arr, len);
	// BubbleSort2(arr, len);
	// SelectionSort1(arr, len);
	// SelectionSort2(arr, len);
	InsertionSort(arr, len);

	Display(arr, len);

	return 0;
}

内容总结

以上是互联网集市为您收集整理的【Practical】插入排序全部内容，希望文章能够帮你解决【Practical】插入排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---