• 猿创征文｜【算法】一文吃透常见排序算法

    需要云服务器等云产品来学习Linux的同学可以移步/-->腾讯云<--/-->阿里云<--/-->华为云<--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。

    目录

     一、常见排序算法 

    二、直接插入排序

    1、直接插入排序思想

    2、直接插入排序代码

    二、希尔排序

    1、希尔排序思想

    2、希尔排序代码

    三、选择排序

    1、选择排序思想

    2、选择排序的代码

    四、堆排序

    1、堆排序思想

    2、堆排序代码

    五、冒泡排序

    1、冒泡排序思想

    2、冒泡排序代码

    六、快速排序

    1、hoare版

    1.1hoare版单趟排序动图

    1.2代码

    1.3思想

    1.4三数取中，优化选key

    1.5小区间优化，减少递归次数

    2、挖坑法

    2.1挖坑法单趟排序动图

    2.2挖坑法思想

    2.3挖坑法代码

    3、前后指针法

    3.1前后指针法单趟排序动图

    3.2前后指针法思想

    3.3前后指针法代码

    4、快排的非递归方法

    4.1非递归的思想

    4.2非递归代码

    七、归并排序

    1、归并排序的递归方法

    1.1归并排序的思想

    1.2归并排序代码

    2、归并排序的非递归

    2.1归并排序的非递归思想

    2.2归并排序的非递归代码

    八、计数排序

    1、计数排序的思想

    2、计数排序代码

     一、常见排序算法 

    类别

    排序方法

    时间复杂度

    空间复杂度

    稳定性

    适用场景

    平均

    最好

    最坏

    插入排序

    直接插入排序

    O(N^2)

    O(N)有序场景

    O(N^2)逆序场景

    O(1)

    稳定

    数据有序或接近有序，

    时间O(N^2)中最强排序

    希尔排序

    O(N^(1.3))

    O(N)有序场景

    O(N^2)每两个数进行一次比较并交换

    O(1)

    不稳定

    插入排序怕大量无序不重复数据，希尔是插入的改良

    选择排序

    直接选择排序

    O(N^2)

    ~~

    ~~

    O(1)

    不稳定例如89855

    最差排序

    堆排序

    O(N*logN)

    ~~

    ~~

    O(1)

    不稳定

    1、首次建堆可以用于找最大/最小。2、top k问题

    交换排序

    冒泡排序

    O(N^2)

    ~~

    ~~

    O(1)

    稳定

    ”那你先写个冒泡排序吧“

    快速排序

    O(N*logN)

    ~~

    O(N^2)有序场景

    O(logN)

    不稳定

    官方库采用的排序算法，遇事不决用快排

    归并

    归并排序

    O(N*logN)

    ~~

    ~~

    O(N)

    稳定

    外排序

    非比较排序

    计数排序

    O(N+range)

    ~~

    ~~

    O(range)

    稳定

    适合排序数据范围小的数据，不能排序浮点数

    二、直接插入排序

    1、直接插入排序思想

    扑克牌玩过吧，扑克牌抽牌，边抽边排的思想。

    虽然直接插入排序是一个N^2的算法，但可以认为它是所有算法中最优的。当直接插入排序遇到重复数据较多、有序、接近有序的数据时，时间复杂度将会降为O(N)。

    直接插入排序的缺点就是时间复杂度过大，针对大量无序不重复数据，排序吃力，所以就有了希尔排序。

    2、直接插入排序代码

    1. void InsertSort(int* arr, int size)//插入排序O(N^2)
    2. {
    3. 	for (int i = 0; i < size - 1; ++i)
    4. 	{
    5. 		int end = i;//end是最后一个有序数字的下标
    6. 		int tmp = arr[end + 1];
    7. 		while (end >= 0)
    8. 		{
    9. 			if (arr[end] > tmp)
    10. 			{
    11. 				arr[end + 1] = arr[end];
    12. 				--end;
    13. 			}
    14. 			else
    15. 				break;
    16. 		}
    17. 		arr[end + 1] = tmp;//最后把tmp放到数组end+1位置处
    18. 	}
    19. }

    二、希尔排序

    1、希尔排序思想

    希尔排序是直接插入排序的改进，gap可以除三加一，也可以除二。每次循环gap是变化的。

    gap大于1，称为预排序。希尔排序的预排序是将gap间隔的数据分为一组，进行直接插入排序，让数组接近有序。

    gap越大，数组内的数字跳的越快，但排完还不是有序。gap越小，数字跳的越慢，但排完越接近有序。希尔排序gap先大后小。

    在数据均不相等的情况下，数据较少，希尔排序优于O(N*logN),反之，希尔排序劣于O(N*logN)

    2、希尔排序代码

    1. void ShellSort(int* arr, int size)//希尔排序(N^1.3)
    2. {
    3. 	int gap = size;
    4. 	while (gap > 1)//gap等于1时说明已经有序，退出循环
    5. 	{
    6. 		gap = gap / 3 + 1;
    7. 		for (int i = 0; i < size - gap; ++i)
    8. 		{
    9. 			int end=i;//end是数组最后一个元素的下标
    10. 			int tmp = arr[end + gap];
    11. 			while (end >= 0)
    12. 			{
    13. 				if (arr[end] > tmp)
    14. 				{
    15. 					arr[end + gap] = arr[end];
    16. 					end -= gap;
    17. 				}
    18. 				else
    19. 					break;
    20. 			}
    21. 			arr[end + gap] = tmp;
    22. 		}
    23. 	}
    24. }

    三、选择排序

    1、选择排序思想

    以升序为例，选择排序每次遍历数组，选出最大的那个数。可以认为它是最菜的排序算法。

    以下代码为选择排序的优化，遍历一次选出最大和最小的数字。

    2、选择排序的代码

    1. void CelectSort(int* arr, int size)//选择排序
    2. {
    3. 	int begin = 0, end = size - 1;
    4. 	while (begin < end)
    5. 	{
    6. 		int min = begin, max = begin;
    7. 		for (int i = begin+1; i <=end; ++i)
    8. 		{
    9. 			if (arr[i] > arr[max])
    10. 				max = i;
    11. 			if (arr[i] < arr[min])
    12. 				min = i;
    13. 		}
    14. 		if (max == begin)
    15. 		{
    16. 			max = min;
    17. 		}
    18. 		Swap(&arr[begin], &arr[min]);
    19. 		Swap(&arr[end], &arr[max]);
    20. 		++begin;
    21. 		--end;
    22. 	}
    23. }

    注意：一趟遍历选出最大和最小的写法，需要考虑max==begin的情况。防止max在初始位置，但该点的值被min换走的情况。

    四、堆排序

    1、堆排序思想

    1、以升序为例：先找到最后一个非叶节点，采用向下调整算法，再找到倒数第二个非叶节点，重复向下调整算法，把一个数组建成堆。这个时候，堆顶就是数组中最大的数。该步时间复杂度O(N)

    动图如下：

    2、将数组调整成大堆后，将堆顶数据（最大的数）和堆底数据进行互换，锁定这个最大的数。这个时候原有的堆形态被破坏，需要重新使用向下调整算法对这个数组重建堆。迭代锁定。该步时间复杂度O(N*logN)

    动图如下：

    2、堆排序代码

    1. void Adjustdown(int* arr, int size, int parent)//向下调整算法
    2. {
    3. 	int maxChild = 2 * parent + 1;
    4. 	while (maxChild
    5. 	{
    6. 		if (maxChild + 1 < size && arr[maxChild] < arr[maxChild + 1])
    7. 		{
    8. 			++maxChild;
    9. 		}
    10. 		if (arr[maxChild] > arr[parent])
    11. 		{
    12. 			Swap(&arr[maxChild], &arr[parent]);
    13. 		}
    14. 		parent = maxChild;
    15. 		maxChild = 2 * parent + 1;
    16. 	}
    17. }
    18. void HeapSort(int* arr, int size)//堆排序O(N*logN)
    19. {
    20. 	//初始化建堆O(N)
    21. 	for (int i = (size - 1 - 1) / 2; i >= 0; --i)
    22. 	{
    23. 		Adjustdown(arr, size, i);
    24. 	}
    25. 	//重建堆O(N*logN)
    26. 	for (int i = 0; i < size - 1; ++i)
    27. 	{
    28. 		Swap(&arr[0], &arr[size - 1 - i]);
    29. 		Adjustdown(arr, size-1-i, 0);
    30. 	}
    31. }

    五、冒泡排序

    1、冒泡排序思想

    一对一对地交换

    2、冒泡排序代码

    1. void BubbleSort(int* arr, int size)//冒泡排序(N^2)
    2. {
    3. 	for (int i = 0; i < size - 1; ++i)//趟数
    4. 	{
    5. 		int flag = 0;
    6. 		for (int j = 0; j < size - 1 - i; ++j)
    7. 		{
    8. 			if (arr[j] > arr[j + 1])
    9. 			{
    10. 				Swap(&arr[j], &arr[j + 1]);
    11. 				flag = 1;
    12. 			}
    13. 		}
    14. 		if (flag == 0)
    15. 			break;
    16. 	}
    17. }

    立个flag，当flag没变，说明一趟走完没有进行两两交换，数组已经有序，跳出循环结束排序。

    六、快速排序

    1、hoare版

    1.1hoare版单趟排序动图

    1.2代码

    1. //[left,right]
    2. int PartSort(int* arr, int left, int right)//单趟排完不是有序，只是key左边比key小，右边比key大
    3. {
    4. 	int keyi = left;//选left做key,keyi是下标
    5. 	while (left < right)
    6. 	{
    7. 		//我们选了left做key，那么右边先走。反之左边先走。
    8. 		while (left < right && arr[right] >= arr[keyi])//R找小
    9. 		{
    10. 			--right;
    11. 		}
    12. 		while (left < right && arr[left] <= arr[keyi])//L找大
    13. 		{
    14. 			++left;
    15. 		}
    16. 		Swap(&arr[left], &arr[right]);
    17. 	}
    18. 	int meet = left;//meet是left和right的相遇点下标
    19. 	Swap(&arr[meet], &arr[keyi]);
    20. 	return meet;
    21. }
    22. //[begin,end]
    23. void QuickSort(int* arr, int begin,int end)//快排
    24. {
    25. 	if (begin >= end)
    26. 		return;
    27. 	int keyi = PartSort(arr, begin, end);
    28. 	//[begin,keyi-1] key [keyi+1,end]
    29. 	QuickSort(arr, begin, keyi - 1);//快排
    30. 	QuickSort(arr, keyi + 1, end);//快排
    31. }

    1.3思想

    1、PartSort是单趟排序，我们先在数组中选择一个位置做key，一般是数组开头或末尾那个位置。

    上面代码中，是用数组首元素做key，为了保证小人相遇位置的值小于key，必须让右边的小人先行动。如果用数组末尾做key，那么需要左边的小人先走。

    右边小人一直走，遇到比key小的数则停下，左边小人再走，遇到比key大的数停下。再交换左右小人脚下的数字。交换完成后一直重复此步骤，直到左右小人相遇。

    将相遇点与keyi位置交换（注意我们是要改变数组，所以需要交换相遇点与keyi位置的值，而不是交换相遇点与key的值）

    单趟排序完成后，keyi左边的值都比key小，keyi右边的值都比key大。

    2、QuickSort中利用二叉树的递归，完成排序。

    该方法存在缺陷：

    1、递归层数过多有爆栈风险 2、面对有序或者接近有序的待排序数据，时间复杂度就变成了O(N^2)

    所以需要作如下优化：

    1.4三数取中，优化选key

    1、随机选key（听着就很随机，虽然不靠谱，但有的场景还是可以使用随即选key的方法）

    2、针对有序情况，选正中间数据做key（前提是知道有序）

    3、三数取中（选出左中右三数中间大小的做key）（三数取中后，对于缺陷2，直接由最坏情况变成最好情况）

    三数取中代码实现：

    1. int GetMidIndex(int* arr, int left, int right)//三数取中
    2. {
    3. 	int mid = left + (right-left) / 2;
    4. 	if (arr[left] >= arr[right])
    5. 	{
    6. 		if (arr[left] > arr[mid])
    7. 		{
    8. 			if (arr[mid] >= arr[right])
    9. 				return mid;
    10. 			else
    11. 				return right;
    12. 		}
    13. 		else
    14. 			return left;
    15. 	}
    16. 	else
    17. 	{
    18. 		if (arr[right] > arr[mid])
    19. 		{
    20. 			if (arr[mid] >= arr[left])
    21. 				return mid;
    22. 			else
    23. 				return left;
    24. 		}
    25. 		else
    26. 			return right;
    27. 	}
    28. }
    29. //[left,right]
    30. int PartSort(int* arr, int left, int right)//单趟排完不是有序，只是key左边比key小，右边比key大
    31. {
    32. 	int mid = GetMidIndex(arr, left, right);
    33. 	Swap(&arr[mid], &arr[left]);
    34. 	int keyi = left;//选left做key,keyi是下标
    35. 	while (left < right)
    36. 	{
    37. 		//我们选了left做key，那么右边先走。反之左边先走。
    38. 		while (left < right && arr[right] >= arr[keyi])//R找小
    39. 		{
    40. 			--right;
    41. 		}
    42. 		while (left < right && arr[left] <= arr[keyi])//L找大
    43. 		{
    44. 			++left;
    45. 		}
    46. 		Swap(&arr[left], &arr[right]);
    47. 	}
    48. 	int meet = left;//meet是left和right的相遇点下标
    49. 	Swap(&arr[meet], &arr[keyi]);
    50. 	return meet;
    51. }
    52. //[begin,end]
    53. void QuickSort(int* arr, int begin,int end)//快排
    54. {
    55. 	if (begin >= end)
    56. 		return;
    57. 	int keyi = PartSort(arr, begin, end);
    58. 	//[begin,keyi-1] key [keyi+1,end]
    59. 	QuickSort(arr, begin, keyi - 1);//快排
    60. 	QuickSort(arr, keyi + 1, end);//快排
    61. }

    三数取中后，我们继续进行下一个优化：

    1.5小区间优化，减少递归次数

    我们知道。二叉树的最后一层节点个数近乎占整棵树节点的一半，倒数第二层占25%，倒数第三层占12.5%。也就是说，后三层就占了整颗二叉树节点的87.5%。

    那么，我们可以在递归时加一个限制条件：当递归时，区间剩余元素少于8个时（可自定义剩余个数），改为使用插入排序来排序这些小区间。

    hoare版本最终代码：

    1. int GetMidIndex(int* arr, int left, int right)//三数取中
    2. {
    3. 	int mid = left + (right-left) / 2;
    4. 	if (arr[left] >= arr[right])
    5. 	{
    6. 		if (arr[left] > arr[mid])
    7. 		{
    8. 			if (arr[mid] >= arr[right])
    9. 				return mid;
    10. 			else
    11. 				return right;
    12. 		}
    13. 		else
    14. 			return left;
    15. 	}
    16. 	else
    17. 	{
    18. 		if (arr[right] > arr[mid])
    19. 		{
    20. 			if (arr[mid] >= arr[left])
    21. 				return mid;
    22. 			else
    23. 				return left;
    24. 		}
    25. 		else
    26. 			return right;
    27. 	}
    28. }
    29. //[left,right]
    30. int PartSort(int* arr, int left, int right)//单趟排完不是有序，只是key左边比key小，右边比key大
    31. {
    32. 	int mid = GetMidIndex(arr, left, right);
    33. 	Swap(&arr[mid], &arr[left]);
    34. 	int keyi = left;//选left做key,keyi是下标
    35. 	while (left < right)
    36. 	{
    37. 		//我们选了left做key，那么右边先走。反之左边先走。
    38. 		while (left < right && arr[right] >= arr[keyi])//R找小
    39. 		{
    40. 			--right;
    41. 		}
    42. 		while (left < right && arr[left] <= arr[keyi])//L找大
    43. 		{
    44. 			++left;
    45. 		}
    46. 		Swap(&arr[left], &arr[right]);
    47. 	}
    48. 	int meet = left;//meet是left和right的相遇点下标
    49. 	Swap(&arr[meet], &arr[keyi]);
    50. 	return meet;
    51. }
    52. //[begin,end]
    53. void QuickSort(int* arr, int begin,int end)//递归快排
    54. {
    55. 	if (begin >= end)
    56. 		return;
    57. 	if (end - begin <= 8)//小区间优化
    58. 	{
    59. 		InsertSort(arr+begin, end -begin + 1);//插入排序O(N^2)
    60. 		return;
    61. 	}
    62. 	else
    63. 	{
    64. 		int keyi = PartSort3(arr, begin, end);
    65. 		//[begin,keyi-1] key [keyi+1,end]
    66. 		QuickSort(arr, begin, keyi - 1);//快排
    67. 		QuickSort(arr, keyi + 1, end);//快排
    68. 	}
    69. }

    2、挖坑法

    2.1挖坑法单趟排序动图

    2.2挖坑法思想

    三数取中后，我们把数组最左边当成坑，并记录这个位置的值key（动态中坑的初始下标是0，key是6）

    同样的，右边小人先走，找到比key小的数字停下来，将脚下位置的数字填入坑中，同时，脚下变成了新的坑。

    左边小人再行动，找到比key大的数字停下来，将脚下位置的数字填入坑中，同时，脚下变成新的坑。

    循环上述过程，直到两小人相遇。相遇时，脚下必定是坑，那么把刚开始的key填入这个坑中。完成了单趟排序。

    挖坑法同样可以适用于三数取中和小区间优化。

    2.3挖坑法代码

    1. //挖坑法
    2. int PartSort(int* arr, int left, int right)
    3. {
    4. 	int mid = GetMidIndex(arr, left, right);
    5. 	Swap(&arr[mid], &arr[left]);
    6. 	int key = arr[left];//选left做key,key是值
    7. 	int hole = left;//坑
    8. 	while (left < right)
    9. 	{
    10. 		while (left < right && arr[right] >= key)//右边找小，填到左边坑
    11. 		{
    12. 			--right;
    13. 		}
    14. 		arr[hole] = arr[right];
    15. 		hole = right;
    16. 		while (left < right && arr[left] <= key)//左边找小，填到右边坑
    17. 		{
    18. 			++left;
    19. 		}
    20. 		arr[hole] = arr[left];
    21. 		hole = left;
    22. 	}
    23. 	arr[hole] = key;//最后把key放到坑里
    24. 	return hole;//返回最后的坑位
    25. }
    26. //[begin,end]
    27. void QuickSort(int* arr, int begin,int end)//递归快排
    28. {
    29. 	if (begin >= end)
    30. 		return;
    31. 	if (end - begin <= 8)//小区间优化
    32. 	{
    33. 		InsertSort(arr+begin, end -begin + 1);//插入排序O(N^2)
    34. 		return;
    35. 	}
    36. 	else
    37. 	{
    38. 		int keyi = PartSort3(arr, begin, end);
    39. 		//[begin,keyi-1] key [keyi+1,end]
    40. 		QuickSort(arr, begin, keyi - 1);//快排
    41. 		QuickSort(arr, keyi + 1, end);//快排
    42. 	}
    43. }

    3、前后指针法

    3.1前后指针法单趟排序动图

    3.2前后指针法思想

    prev指向初始位置，cur指向prev的下一个位置

    prev先走，cur后走，当cur遇到比key大的值，prev停下，cur继续走，直到cur遇到比key小的数，prev再往前走，prev向前走完后，交换cur与prev的值

    循环上述过程，直到cur>right，交换keyi和prev的值

    动图看起来就像是prev在后面推着key大的数字往前走，当然该方法也要用三数取中和小区间优化。

    3.3前后指针法代码

    1. int PartSort(int* arr, int left, int right)
    2. {
    3. 	int mid = GetMidIndex(arr, left, right);
    4. 	Swap(&arr[mid], &arr[left]);
    5. 	int keyi = left;//选left做key,keyi是下标
    6. 	int prev = left, cur = prev + 1;
    7. 	while (cur <= right)
    8. 	{
    9. 		if (arr[cur] < arr[keyi] && ++prev!=cur)
    10. 		{
    11. 			Swap(&arr[cur], &arr[prev]);
    12. 		}
    13. 		++cur;
    14. 	}
    15. 	Swap(&arr[prev], &arr[keyi]);
    16. 	return prev;
    17. }
    18. //[begin,end]
    19. void QuickSort(int* arr, int begin,int end)//快排
    20. {
    21. 	if (begin >= end)
    22. 		return;
    23. 	int keyi = PartSort(arr, begin, end);
    24. 	//[begin,keyi-1] key [keyi+1,end]
    25. 	if (end - begin <= 8)//小区间优化
    26. 	{
    27. 		InsertSort(arr+begin, end -begin + 1);//插入排序O(N^2)
    28. 		return;
    29. 	}
    30. 	else
    31. 	{
    32. 		QuickSort(arr, begin, keyi - 1);//快排
    33. 		QuickSort(arr, keyi + 1, end);//快排
    34. 	}
    35. }

    4、快排的非递归方法

    4.1非递归的思想

    从递归的方法可以看出，在第一次选出keyi时，可以对左右区间进行递归操作，重复选出keyi，不断对小区间进行排序，直至有序。同样的，非递归方法使用栈来模拟递归的过程，每次将左右区间的下标压入栈中，就执行了一次该区间的单趟排序。直到栈空，说明数组已经有序。

    4.2非递归代码

    1. void NonFQuickSort(int* arr, int begin, int end)//非递归快排，使用栈
    2. {
    3. 	ST st;//建立一个栈
    4. 	StackInit(&st);//初始化
    5. 	StackPush(&st, begin);//压栈
    6. 	StackPush(&st, end);//压栈
    7. 	while (!StackEmpty(&st))
    8. 	{
    9. 		int right = StackTop(&st);//访问栈顶元素
    10. 		StackPop(&st);//出栈
    11. 		int left = StackTop(&st);//访问栈顶元素
    12. 		StackPop(&st);//出栈
    13. 		int keyi = PartSort3(arr, left, right);//keyi是下标，单趟排序
    14. 		//[left,keyi-1] keyi [keyi+1,right]
    15. 		if (keyi + 1 < right)
    16. 		{
    17. 			StackPush(&st, keyi + 1);//压栈
    18. 			StackPush(&st, right);//压栈
    19. 		}
    20. 		if (left < keyi - 1)
    21. 		{
    22. 			StackPush(&st, left);//压栈
    23. 			StackPush(&st, keyi - 1);//压栈
    24. 		}
    25. 	}
    26. 	StackDestroy(&st);//销毁
    27. }

    七、归并排序

    1、归并排序的递归方法

    1.1归并排序的思想

    现在想对一组无序数组排序，那么将这个数组均分成左右两个部分，只要左区间有序，右区间有序，那就可以借助额外的空间，将左右两个数组中小的数不断尾插，形成有序，最后将额外空间中的数据拷贝回原数组即可。那么左右区间怎么才能有序呢？通过递归的方法，对左右区间不断均分至区间内仅剩一个数，开始归并。

    归并的缺点在于需要额外O(N)的空间，常用于解决磁盘的外排序。

    1.2归并排序代码

    1. void _MergeSort(int* arr, int begin, int end, int* tmp)
    2. {
    3. 	if (begin >= end)
    4. 		return;
    5. 	int mid = begin + (end - begin) / 2;//将左右区间二分
    6. 	//[begin,mid][mid+1,end]
    7. 	_MergeSort(arr, begin, mid, tmp);
    8. 	_MergeSort(arr, mid+1, end, tmp);
    9. 	//升序归并,取小的尾插，重新定义起始位置，防止begin和end被改变
    10. 	int begin1 = begin, end1 = mid;
    11. 	int begin2 = mid + 1, end2 = end;
    12. 	int i = begin;
    13. 	while (begin1 <= end1 && begin2 <= end2)
    14. 	{
    15. 		if (arr[begin1] <= arr[begin2])
    16. 		{
    17. 			tmp[i++] = arr[begin1++];
    18. 		}
    19. 		else
    20. 		{
    21. 			tmp[i++] = arr[begin2++];
    22. 		}
    23. 	}
    24. 	//左右区间必定有一个还没有尾插完
    25. 	while (begin1 <= end1)
    26. 	{
    27. 		tmp[i++] = arr[begin1++];
    28. 	}
    29. 	while (begin2 <= end2)
    30. 	{
    31. 		tmp[i++] = arr[begin2++];
    32. 	}
    33. 	//将tmp部分区域数据拷贝回原数组
    34. 	memcpy(arr + begin, tmp + begin, (end - begin + 1) * sizeof(int));
    35. }
    36. void MergeSort(int* arr, int size)
    37. {
    38. 	int* tmp = (int*)malloc(sizeof(int) * size);
    39. 	if (tmp == NULL)
    40. 	{
    41. 		perror("malloc fail");
    42. 		exit(-1);
    43. 	}
    44. 	_MergeSort(arr, 0, size - 1, tmp);
    45. 	free(tmp);
    46. }

    2、归并排序的非递归

    2.1归并排序的非递归思想

    因为递归版本是将数组内元素不断均分，直至区间内仅剩一个元素时，开始归并。那么非递归版本直接一一归并···两两归并····四四归并······直至整体有序。注意分类讨论边界问题：begin1是不可能越界的，当end1和begin2越界时，直接break即可；当end2越界时，修正end2=size-1继续进行归并。

    2.2归并排序的非递归代码

    1. void MergeSortNonR(int* arr, int size)
    2. {
    3. 	int* tmp = (int*)malloc(sizeof(int) * size);
    4. 	if (tmp == NULL)
    5. 	{
    6. 		perror("malloc fail");
    7. 		exit(-1);
    8. 	}
    9. 	int gap = 1;
    10. 	while (gap < size)
    11. 	{
    12. 		for (int j = 0; j < size; j += 2 * gap)
    13. 		{
    14. 			int begin1 = j, end1 = j + gap - 1;
    15. 			int begin2 = j + gap, end2 = j + 2 * gap - 1;
    16. 			//判断边界
    17. 			if (end1 >= size)
    18. 			{
    19. 				break;
    20. 			}
    21. 			if (begin2 >= size)
    22. 			{
    23. 				break;
    24. 			}
    25. 			if (end2 >= size)//修正end2，继续归并
    26. 			{
    27. 				end2 = size - 1;
    28. 			}
    29. 			int i = j;
    30. 			while (begin1 <= end1 && begin2 <= end2)
    31. 			{
    32. 				if (arr[begin1] <= arr[begin2])
    33. 				{
    34. 					tmp[i++] = arr[begin1++];
    35. 				}
    36. 				else
    37. 				{
    38. 					tmp[i++] = arr[begin2++];
    39. 				}
    40. 			}
    41. 			//还剩一个区间没有尾插完
    42. 			while (begin1 <= end1)
    43. 			{
    44. 				tmp[i++] = arr[begin1++];
    45. 			}
    46. 			while (begin2 <= end2)
    47. 			{
    48. 				tmp[i++] = arr[begin2++];
    49. 			}
    50. 			//将tmp数组中的数据拷贝回原数组
    51. 			memcpy(arr + j, tmp + j, sizeof(int) *(end2-j+1));//end2-j-1千万不可以写成2*gap，因为当end2被修正时没救不等于2*gap了
    52. 		}
    53. 		gap *= 2;;
    54. 	}
    55. 	free(tmp);
    56. 	tmp = NULL;
    57. }

    八、计数排序

    1、计数排序的思想

    计数排序适用于排序数组极差小的数据。此时range忽略，时间复杂度O(N)的话，也是一个非常强大的排序。

    1、找出数组中的最大值和最小值，求出range=max-min+1

    2、开辟range个空间并对这块区域初始化为0

    3、通过相对映射对每个数出现的频次计数（同时数据已经被排序）

    4、根据频次覆盖写入数据至原数组

    5、free临时空间

    2、计数排序代码

    1. void CountSort(int* arr, int size)//计数排序,时间O(N+range),空间O(range)
    2. {
    3. 	int min = arr[0], max = arr[0];
    4. 	//遍历找出最大、最小
    5. 	for (int i = 0; i < size; ++i)
    6. 	{
    7. 		if (arr[i] < min)
    8. 			min = arr[i];
    9. 		if (arr[i] > max)
    10. 			max = arr[i];
    11. 	}
    12. 	//malloc一个相对映射数组
    13. 	int range = max - min + 1;//malloc数组的元素个数
    14. 	int* Count = (int*)malloc(sizeof(int) * range);
    15. 	if (Count == NULL)
    16. 	{
    17. 		perror("malloc fail:");
    18. 		return;
    19. 	}
    20. 	memset(Count,0, sizeof(int) * range);
    21. 	//相对映射计数
    22. 	for (int i = 0; i < size; ++i)
    23. 	{
    24. 		++Count[arr[i] - min];
    25. 	}
    26. 	//将映射数据覆盖至原数组
    27. 	int j = 0;
    28. 	for (int i = 0; i < range; ++i)
    29. 	{
    30. 		while (Count[i]--)
    31. 		{
    32. 			arr[j++] = i + min;
    33. 		}
    34. 	}
    35. 	//释放malloc的空间
    36. 	free(Count);
    37. }
  • 相关阅读:
    DOM知识点总结
    IntelliJ IDEA远程调试：使用IDEA Remote Debug进行高效调试的指南
    Thinkphp资源源码付费下载站网站源码
    基于R语言分位数回归丨线性回归假设与分位数函数、线性分位数回归 、贝叶斯分位数回归、超越线性分位数回归等
    linux下统计当前目录子目录的个数
    找到了！宝藏公众号合集，新媒体运营小白必须学习
    嵌入式系统开发笔记91：认识ARM微控制器架构
    「Java开发指南」MyEclipse如何支持Spring Scaffolding？（三）
    怎么制作一个网站？怎样搭建一个高质量的网站？
    Apache DolphinScheduler的工作流传参
  • 原文地址：https://blog.csdn.net/gfdxx/article/details/126826128