在进行单趟排序的过程中可能会出现以上两种情况，第一种就是像图中左边一样，[0, end] 中有比 end+1 更小的数据，end的下标最终会停在大于或等于0的位置。第二种情况就像图中右边一样，end+1 比 [0, end] 中的所有数据都小，end的下标就会自减到-1的位置，这种情况就可能会造成数组越界访问。所以在单趟排序时，要控制end大于等于0。

② 在整体排序中对end的控制1.

在整体排序时，应该限制end，让end小于n-1，此时end最大的位置只会在n-2处，end+1=n-1，符合在数组内操作。若让end小于n，此时end最大的位置出现在n-1处，end+1=n，这样就会出现数组越界的问题。所以对于整体排序，要让end小于n-1。

1.1.2. | 代码实现 |


void InsertSort(int* p, int sz)
{
	for (int i = 0; i < sz - 1; i++)
	{
		int end = i;
		int tmp = p[end + 1];
 
		while (end >= 0)
		{
			if (p[end] > tmp)
			{
				p[end + 1] = p[end];
				end--;
			}
			else
			{
				break;
			}
		}
 
		p[end + 1] = tmp;
	}
}

1.1.3. | 特性总结 |

1. 元素集合越接近有序，直接插入排序算法的时间效率越高。

2. 时间复杂度：O(N^2) ---- [ 最好情况：顺序 O(N)；最坏情况：逆序 O(N^2) ]

3. 空间复杂度：O(1)

4. 稳定性：稳定

1.2. 希尔排序

1.2.1. | 排序原理 |

希尔排序是优化后的直接插入排序。希尔排序分为两个大步骤，第一步，先对数据进行预排序，即把间隔为gap的数据分为一组，对每组数据进行直接插入排序。第二步，将预排序后的序列进行插入排序。

gap不是固定不变的，随着序列中数据个数的个数不同，gap也会随之改变(在实现单趟排序时我们暂且先把gap视为固定值)。

1.2.2. | 代码实现 |

先用代码实现一组数据的排序。


int gap = 3;
 
for (i = 0; i < sz - gap; i += gap)
{
	int end = i;
	int tmp = p[end + gap];
 
	while (end >= 0)
	{
		if (p[end] > tmp)
		{
			p[end + gap] = p[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
 
	p[end + gap] = tmp;
}

预排序要对所有分组的数据进行直接插入排序，所以要在一组排序代码的基础上再套一层循环来控制end，即控制其他组数据进行直接插入排序。

(gap的数值取多少，待排序列就会被分为多少组)


int gap = 3;
 
for (int j = 0; j < gap; j++)
{
	for (int i = j; i < sz - gap; i += gap)
	{
		int end = i;
		int tmp = p[end + gap];
 
		while (end >= 0)
		{
			if (p[end] > tmp)
			{
				p[end + gap] = p[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
 
		p[end + gap] = tmp;
	}
}

上述代码是对每一组数据分别进行直接插入排序，一组排完后再排下一组。

可将以上代码优化为只用两层循环(实际代码效率并无改变)：


int gap = 3;
 
for (int i = 0; i < sz - gap; i++)
{
	int end = i;
    int tmp = p[end + gap];
 
	while (end >= 0)
	{
		if (p[end] > tmp)
		{
			p[end + gap] = p[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
 
	p[end + gap] = tmp;
}

上述优化后的代码可以理解为，间隔为gap的数据依次多组并排，各组的数据都齐头并进的在进行插入排序，各组的直接插入排序没有先后之分，最后几乎同时完成插入排序。

实现完以上代码后，希尔排序只差临门一脚。上文提到gap的数值不是固定不变的，以上的待排序列有10个元素，gap取3符合情理，但是如果待排序列有1000个数据，gap还能取3吗？显然是不能的。可以看出gap的取值应该与待排序列的数据个数有关。

| gap取值的意义 |

gap越大，大的数据可以越快的跳到后面，小的数据可以越快的跳到前面，但预排序后整体序列没那么接近有序。

gap越小，数据跳的越慢，但预排序后整体序列越接近有序。

这里对gap的控制的大思路是，既然gap与数据个数有关，那么索性初始让gap等于数据个数，然后再用一层循环来控制gap，进行多组预排序，让gap从数据个数变到1(当gap大于1时，就是预排序；当gap等于1时，这一次就是在进行整体序列的直接插入排序了)，让 gap/=3+1 (加1是为了保证gap最后一次取值为1)。


void ShellSort(int* p, int sz)
{
	int gap = sz;
 
	while (gap > 1)
	{
		gap = gap / 3 + 1;
 
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int tmp = p[end + gap];
 
			while (end >= 0)
			{
				if (p[end] > tmp)
				{
					p[end + gap] = p[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
 
			p[end + gap] = tmp;
		}
	}
}

1.2.3. | 特性总结 |

1. 希尔排序是对直接插入排序的优化。

2. 时间复杂度：O(N^1.3) ---- [ 不好算，记结论即可 ]

3. 空间复杂度：O(1)

4. 稳定性：不稳定

二、选择排序

选择排序的基本思想：

每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.1. 直接选择排序

2.1.1. | 排序原理 |

通过遍历待排序列，选出最小的数据，将最小的数据与第一个数据交换，再次遍历待排序列，选出次小的数据，将次小的数据与第二个数据交换。如此反复，直到将序列中所有数据都置于正确的位置为止。

可以对直接选择排序进行优化。

通过一次遍历选出最大的数据和最小的数据，将最大的数据与末尾的数据交换，将最小的数据与第一个数据交换，再次进行遍历，选出次大和次小的数据，将次大的数据和倒数第二个数据交换，将次小的数据与第二个位置的数据交换，如此反复，直到将序列中所有数据都置于正确的位置为止。

2.1.2. | 代码实现 |


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void SelectSort(int* p, int sz)
{
	int begin = 0;
	int end = sz - 1;
 
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
 
		for (i = begin + 1; i <= end; i++)
		{
			if (p[i] > p[maxi])
			{
				maxi = i;
			}
 
			if (p[i] < p[mini])
			{
				mini = i;
			}
		}
 
		Swap(&p[begin], &p[mini]);
		Swap(&p[end], &p[maxi]);
 
		begin++;
		end--;
	}
}

以上代码存在一个小bug，当待排序列为 [ 100, 6, 1, 3, 2, 7, 0, 5 ] 时，会出现以下问题。

由于maxi与begin处于同一位置，执行 Swap(&p[begin], &p[mini]); 将mini位置上的数据与begin位置上的数据交换，实际上maxi位置上的数据也被交换到了mini位置上。上述代码以为最大的数据仍然在maxi的位置上，实际上最大的数据已经不在maxi位置上了，已经被换到mini的位置上了，继续执行 Swap(&p[end], &p[maxi]); 将maxi位置上的数据与end位置上的数据交换，就会出现上述错误。

为解决这一问题，我们只需要在执行完 Swap(&p[begin], &p[mini]); 后，在执行 Swap(&p[end], &p[maxi]); 前，判断一下maxi与begin是否处于同一位置，若处于同一位置则将maxi修正一下，将mini的位置赋值给maxi即可解决上述问题。


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void SelectSort(int* p, int sz)
{
	int begin = 0;
	int end = sz - 1;
 
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
 
		for (i = begin + 1; i <= end; i++)
		{
			if (p[i] > p[maxi])
			{
				maxi = i;
			}
 
			if (p[i] < p[mini])
			{
				mini = i;
			}
		}
 
		Swap(&p[begin], &p[mini]);
 
		if (maxi == begin)
		{
			maxi = mini;
		}
 
		Swap(&p[end], &p[maxi]);
 
		begin++;
		end--;
	}
}

2.1.3. | 特性总结 |

1. 直接选择排序思想非常好理解，但是效率不是很好。实际中很少使用。

2. 时间复杂度：O(N^2) ---- [ 最好情况：O(N^2)；最坏情况：O(N^2)；数据的顺序对其时间复杂度没有影响 ]

3. 空间复杂度：O(1)

4. 稳定性：不稳定

2.2. 堆排序

2.2.1. | 排序原理 |

对一组待排序列使用堆排序，首先要对该序列进行建堆操作(使用向下调整建堆，排升序建大堆，排降序建小堆)，建完堆后，将堆顶的数据换到数组的末尾，并对换完数据的类堆进行向下调整操作，将类堆调整为堆，继续将堆顶元素换到数组的倒数第二个位置，再继续将换完数据的类堆向下调整成堆，如此反复，直到将序列排完序为止。

2.2.2. | 代码实现 |


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(int* p, int sz, int parent)
{
	int Child = parent * 2 + 1;
 
	while (Child < sz)
	{
		if (Child + 1 < sz && p[Child + 1] > p[Child])
		{
			Child++;
		}
 
		if (p[Child] > p[parent])
		{
			Swap(&p[Child], &p[parent]);
			parent = Child;
			Child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(int* p, int sz)
{
	int i = 0;
	for (i = (sz - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(p, sz, i);
	}
 
	for (i = 1; i < sz; i++)
	{
		Swap(&p[0], &p[sz - i]);
		AdjustDown(p, sz - i, 0);
	}
}

2.2.3. | 特性总结 |

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

三、交换排序

交换排序的基本思想：

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

3.1. 冒泡排序

3.1.1. | 排序原理 |

对待排序列的数据两两比较，将大的数据换到后面。每一趟冒泡只能将一个数归至其正确位置上，第一趟冒泡只能将最大的数归位至最后一位，第二趟冒泡只能将次大的数归位至倒数第二位，以此类推。若有n个待排数据，则只需将n-1个数据归位，即执行n-1趟冒泡排序，完成n-1趟冒泡后，剩下那一个数据自然就处于他正确的位置上了。

3.1.2. | 代码实现 |


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void BubbleSort(int* p, int sz)
{
	int end = sz;
	while (end >= 2)
	{
		int flag = 1;
 
		int i = 0;
		for (i = 1; i < end; i++)
		{
			if (p[i - 1] > p[i])
			{
				flag = 0;
				Swap(&p[i - 1], &p[i]);
			}
		}
 
		if (flag)
		{
			break;
		}
 
		end--;
	}
}

3.1.3. | 特性总结 |

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度：O(N^2) ---- [ 加了flag优化后最好情况是顺序有序，时间复杂度为：O(N) ]

3. 空间复杂度：O(1)

4. 稳定性：稳定

3.2. 快速排序

3.2.1. | 排序原理 |

快速排序的基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后在左右子序列中重复该过程，直到所有元素都排列在相应位置上为止。

本篇博客提供三种实现方法(hoare版本，挖坑版本，前后指针版本) (推荐使用挖坑版本实现快速排序)

① hoare版本

② 挖坑版本

③ 前后指针版本

3.2.2. | 代码实现 |


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
int GetMidIndex(SortDataType* p, int left, int right)
{
	int mid = left + (right - left) / 2;
 
	if (p[left] < p[mid])
	{
		if (p[mid] < p[right])
		{
			return mid;
		}
		else if (p[left] > p[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else //p[left] > p[mid] 或 p[left] = p[mid]
	{
		if (p[mid] > p[right])
		{
			return mid;
		}
		else if (p[left] < p[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
 
void QuickSort(SortDataType* p, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
 
	int mid = GetMidIndex(p, begin, end);
	Swap(&p[begin], &p[mid]);
 
	// hoare版本
	/*int keyi = begin;
	int left = begin;
	int right = end;
	while (left < right)
	{
		while (left < right && p[right] >= p[keyi])
		{
			right--;
		}
		while (left < right && p[left] <= p[keyi])
		{
			left++;
		}
		if (left < right)
		{
			Swap(&p[left], &p[right]);
		}
	}
	int meeti = left;
	Swap(&p[meeti], &p[keyi]);
	QuickSort(p, begin, meeti - 1);
	QuickSort(p, meeti + 1, end);*/
 
 
	// 挖坑版本
	int key = p[begin];
	int hole = begin;
	int left = begin;
	int right = end;
 
	while (left < right)
	{
		while (left < right && p[right] >= key)
		{
			right--;
		}
		p[hole] = p[right];
		hole = right;
 
		while (left < right && p[left] <= key)
		{
			left++;
		}
		p[hole] = p[left];
		hole = left;
	}
	p[hole] = key;
 
	QuickSort(p, begin, hole - 1);
	QuickSort(p, hole + 1, end);
 
 
	// 前后指针版本
	/*int keyi = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		if (p[cur] < p[keyi] && ++prev != cur)
		{
			Swap(&p[prev], &p[cur]);
		}
		cur++;
	}
	Swap(&p[prev], &p[keyi]);
	QuickSort(p, begin, prev - 1);
	QuickSort(p, prev + 1, end);*/
}

加入三数取中法来选key可优化快速排序，可以避免对最坏的情况(即有序)进行排序。

对三数取中算法的详解可以参考我的另一篇博客《快速排序算法 ( 挖坑法 ) + 三数取中算法详解》

3.2.3. | 特性总结 |

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN) ---- [ 空间的消耗来自于递归过程中在栈中开辟的空间，递归深度为logN，所以空间复杂度为：O(logN) ]

4. 稳定性：不稳定

四、归并排序

4. 归并排序

归并排序的基本思想：

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列之间有序。若将两个有序序列合并成一个有序序列，称为二路归并。

4.1. | 排序原理 |

在两个有序子序列中取数值小的数据尾插到一个新数组中，最后再将排好序的数据拷贝至原序列中。若子序列无序则递归分成子问题求解，当将子序列的数据递归分至只有一个数据时，此时可认为该子序列有序，从而可以开始进行归并。

4.2. | 代码实现 |


void _MergeSort(SortDataType* p, int begin, int end, SortDataType* tmp)
{
	if (begin >= end)
	{
		return;
	}
 
	int mid = begin + (end - begin) / 2;
	//[begin,mid] [mid,end]
 
	_MergeSort(p, begin, mid, tmp);
	_MergeSort(p, mid + 1, end, tmp);
 
	//程序执行到这[begin,mid] [mid,end]两区间已有序，可进行归并
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
 
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (p[begin1] <= p[begin2])
		{
			tmp[i++] = p[begin1++];
		}
		else
		{
			tmp[i++] = p[begin2++];
		}
	}
 
	//上面while循环结束后，两个区间必定有一个区间还有元素，此时将剩下的那个区间全部转移至tmp中
	while (begin1 <= end1)
	{
		tmp[i++] = p[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = p[begin2++];
	}
 
	//将数据归并到tmp后，要将数据从tmp中拷贝回原数组中
	memcpy(p + begin, tmp + begin, (end - begin + 1) * sizeof(SortDataType));
}
 
void MergeSort(SortDataType* p, int n)
{
	SortDataType* tmp = (SortDataType*)malloc(n * sizeof(SortDataType));
	if (tmp == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
 
	_MergeSort(p, 0, n - 1, tmp);
 
	free(tmp);
	tmp = NULL;
}

4.3. | 特性总结 |

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(N) ---- [ 执行单趟归并排序需要借助第三方数组实现，所以空间复杂度为：O(N) ]

4. 稳定性：稳定

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/神奇cpp/article/detail/850780