【数据结构与算法】排序算法（选择排序，冒泡排序，插入排序，希尔排序）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】排序算法（选择排序，冒泡排序，插入排序，希尔排序）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

基本概念这了就不浪费时间解释了，这四种都是很简单的排序方式，本专栏后续文章会出归并排序，计数排序，快速排序，堆排序，桶排序等排序算法，今天这篇文章中给出选择排序，冒泡排序，插入排序和希尔排序的实现；

选择排序

void SelectSort(int* pArr, int nCount)
{
	for (size_t i = 0; i < nCount - 1 ; i++) {
		int nMinIndex = i ;
		for (size_t j = i + 1; j < nCount; j++) {
			if (pArr[j] < pArr[nMinIndex]) {
				nMinIndex = j;
			}
		}
		if (nMinIndex != i) {
			swap(&pArr[i], &pArr[nMinIndex]);
		}
	}
}

冒泡排序

void InsertSort(int * pArr, int nCount)
{
	for (size_t i = 1; i < nCount; i++) {
		int Value = pArr[i];
		int nIndex = i - 1;
		while (nIndex >= 0 && pArr[nIndex] > Value) {
			pArr[nIndex + 1] = pArr[nIndex--];
		}
		pArr[nIndex + 1] = Value;
	}
}

插入排序

void InsertSort(int * pArr, int nCount)
{
	for (size_t i = 1; i < nCount; i++) {
		int Value = pArr[i];
		int nIndex = i - 1;
		while (nIndex >= 0 && pArr[nIndex] > Value) {
			pArr[nIndex + 1] = pArr[nIndex--];
		}
		pArr[nIndex + 1] = Value;
	}
}

希尔排序

void ShellSort(int * pArr, int nCount)
{
	int Interval = nCount / 2;
	while (Interval > 0) {
		for (size_t i = 1; i < nCount; i += Interval) {
			int Value = pArr[i];
			int nIndex = i - Interval;
			while (nIndex >= 0 && pArr[nIndex] > Value) {
				pArr[nIndex + Interval] = pArr[nIndex];
				nIndex -= Interval;
			}
			pArr[nIndex + Interval] = Value;
		}
		Interval /= 2;
	}
}