1. Toy模板网首页
  2. > Toy博客

数据结构--八大排序

10月前 作者：龙里出生的蛋 分类：Toy博客 阅读(43) 违法举报

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

1.插入排序

1.1插入排序的思想

插入排序的思想跟摸牌很相似，从我们摸到第二张牌的开始，依次将摸到到牌依次有序的插入到手中，最后手牌变成了有序。
数据结构--八大排序
有了大致的思路，接下来就要细分插入排序的细节。
首先考虑某一趟的插入排序。为什么先考虑某一趟呢？因为当需要解决的问题比较复杂时先将问题简单化会有利于问题的解决。
某一趟的插入排序：
数据结构--八大排序
整个插入排序：我们回味一下过年打牌的情景，是不是只有从第二张牌开始我们才开始将摸到牌插到手中？所以end是从1开始到n-1结束。
完整代码：

void InsertSort(int* arr, int n)
{
	for (int i = 1; i < n ; i++)
	{
		int end = i;
		int x = arr[end];
		while (end > 0)
		{
			if (arr[end-1] > x)
			{
				//后移
				arr[end] = arr[end - 1];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end] = x;
	}
}

1.2插入排序的特点

特点：

  • 1.元素集合越接近有序，直接插入排序算法的时间效率越高
  • 2.时间复杂度:O(n^2)(情况最差时,即逆序转有序,最好的情况下为O(n));
  • 3.空间复杂度:O(1);
  • 4.稳定

2.希尔排序

2.1希尔排序的思想

希尔排序是1959 年由D.L.Shell 提出来的，希尔排序是继插入排序的一次大幅度的优化。希尔排序又叫缩小增量排序。
基本思想：
先将整个数组分成若干个子数组,通过对子数组进行排序,达到数组"基本有序",再对整个数组进行插入排序,即可达到有序。
实现方法：
1,先分组,间隔为Gap的数据为一组,然后对这组数据进行排序,再分组,再排,直到数组被分完。

2,然后再把Gap减小,继续分组,排序。

3,此时数组基本有序,然后将最后Gap减小为1,即进行直接插入排序,得到有序数组。
图示：
数据结构--八大排序
有了大致思想后就可以开始写代码了。还是用化繁琐为简单的思想来写代码。
先考虑gap=某一个值时，代码的实现。
当gap=某一个值时，第一组数据的插入排序。（下图）
数据结构--八大排序
当gap=某一个值时，多组数据的插入排序。（下图）
数据结构--八大排序
完整代码：

//希尔排序
void ShellSort(int* arr, int n)
{
	//多次预排序（gap>1）+直接插入（gap=1）
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//对多组数进行插入排序
		for (int j = gap; j < gap*2; j++)
		{
			//对一组数进行插入排序
			for (int i = j; i < n ; i += gap)
			{
				int end = i;
				int x = arr[end];
				while (end >0)
				{
					if (arr[end-gap] > x)
					{
						arr[end] = arr[end-gap];
						end = end - gap;
					}
					else
					{
						break;
					}
				}
				arr[end] = x;
			}
		}
	}
}

2.1希尔排序的特点

特点：

  • 1.希尔排序是对直接插入排序的优化。
  • 2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
  • 3.希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，这里不深究。
  • 4.时间复杂度O(N^1.5)、空间复杂度O(1)。
  • 5.稳定性：不稳定。
    希尔排序不稳定说明（图示）：
    数据结构--八大排序

3.选择排序

3.1选择排序

选择排序是我感觉最简单的排序，理解起来很简单，写起来也很容易。
基本思想：

  • 第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始(末尾)位置，

  • 然后选出次小(或次大)的一个元素，存放在最大(最小)元素的下一个位置，

  • 重复这样的步骤直到全部待排序的数据元素排完 。
    数据结构--八大排序
    完整代码：

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}
//选择排序
void SelectSort(int* arr, int sz)
{
	for (int i = 0; i < sz-1; i++)
	{
		int index = i;
		for (int j = i + 1; j < sz; j++)
		{
			if (arr[j] < arr[index])
			{
				index = j ;
			}
		}
		if (index != i)
		{
			Swap(&arr[i], &arr[index]);
		}
	}
}

选择排序的小优化：
基本思想：上面的思路是每一趟确定一个数，那能不能一趟确定两个数呢？
数据结构--八大排序
老规矩先考虑某一趟的代码编写：
数据结构--八大排序
上面的代码对于大部分情况是可以完成排序的。但是对于一些情况是有问题的。
例如：
数据结构--八大排序
为了出现这种情况，所以必须加个判断语句。
数据结构--八大排序
完整代码：

//选择排序
void SelectSort(int* arr, int n)
{
	int beg = 0, end = n - 1;
	while (beg < end)
	{
		//找出最大、最小的下标
		int maxi = beg;
		int mini = beg;
		for (int i = beg; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		Swap(&arr[beg], &arr[mini]);
		if (maxi == beg)
		{
			maxi = mini;
		}
		Swap(&arr[end], &arr[maxi]);
		beg++;
		end--;
	}
}

3.2选择排序的特点

选择排序的特点：

  • 1.选择排序思考非常好理解，但是效率不是很好(不论数组是否有序都会执行原步骤)。实际中很少使用

  • 2.时间复杂度：O(N^2)（最好和最坏的情况下时间复杂度都是一样）

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

  • 4.稳定性：不稳定

  • 数据结构--八大排序

4.冒泡排序

4.1冒泡排序的思想

基本思想：
一趟过程中，前后两个数依次比较，将较大的数字往后推，下一次只需要比较剩下的n-1个数，如此往复。
数据结构--八大排序
动态图展示：
数据结构--八大排序
怎么编写冒泡排序的代码呢？咱们还是先把问题简单化，先考虑一趟冒泡排序的代码编写。
第一趟冒泡排序的编写：
数据结构--八大排序
怎么进行多趟的冒泡排序呢？
只需要控制i的最终大小即可。
当一趟循环下来i=n-2时，可以保证arr[n-1]的值是最大的；
当一趟循环下来i=n-3时，可以保证arr[n-2]的值是次大的；
当一趟循环下来i=n-4时，可以保证arr[n-3]的值是次次大的；
…
所以只需要在嵌套一层循环即可。

数据结构--八大排序
完整代码：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	for (int j = 0; j < n-1 ; j++)
	{
		for (int i = 0; i < n -1- j; i++)
		{
			if (arr[i] > arr[i+1])
			{
				Swap(&arr[i], &arr[i+1]);
			}
		}
	}
}

小伙伴到这是不是以为冒泡排序结束了？嘿嘿，其实还没有。不知道大家考虑过这样的情况过吗？
如下图：
数据结构--八大排序
答案是还要进行。这就是上面的冒泡排序缺点。
冒泡排序的小优化：
基本思想：
为了让冒泡排序知道数组数组是否有序，可以定义一个变量flag。当flag=1时，默认数组是无序的。当flag=0时，认为数组是有序的。
数据结构--八大排序
优化后的完整代码：

//冒泡排序
void BubbleSort(int* arr, int n)
{
	int flag = 1;
	for (int j = 0; j < n&&flag==1; j++)
	{
		flag = 0;
		for (int i = 1; i < n-j; i++)
		{
			if (arr[i-1] > arr[i])
			{
				Swap(&arr[i - 1], &arr[i]);
				flag = 1;
			}
		}
	}
}

4.2冒泡排序的特点

特点：

  • 非常容易理解的排序
  • 时间复杂度:O(N^2)
  • 空间复杂度:O(1)
  • 稳定性：稳定

5.快速排序

5.1快速排序的思想

5.1快速排序（递归）

基本思想：数据结构--八大排序
乍一看这个排序写起来毫无思路，所以我们一步一步看问题，一步一步解决问题。
先考虑第一个问题：将数组中第一个数放在正确的位置。

5.1.1快速排序（递归-Hoare）

第一个问题的基本思想：
数据结构--八大排序
第一个问题的基本步骤：
1、选出一个keyi，一般是最左边或是最右边的。
2、定义一个L和一个R，L从左向右走，R从右向左走。（需要注意的是：若选择最左边的数据作为key，则需要R先走；若选择最右边的数据作为keyi，则需要L先走）。
3、在走的过程中，若R遇到小于arr[keyi]的数，则停下，L开始走，直到L遇到一个大于arr[keyi]的数时，将L和R的内容交换，R再次开始走，如此进行下去，直到L和R最终相遇，此时将相遇点的内容与arr[keyi]交换即可。（选取最左边的值作为keyi）
经过一次单趟排序，最终使得key左边的数据全部都小于arr[keyi]，key右边的数据全部都大于arr[keyi]。
为什么要注意谁先走呢？以左值为keyi举例说明：
数据结构--八大排序

第一个问题的动态图演示（Hoare）：

数据结构--八大排序
代码(Hoare)：

//一趟快速排序
int Partion(int* arr, int left, int right)
{
	assert(arr);
	int keyi = left;

	while (left < right)
	{
		//左边是key值，让右边先走
		//右边找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

		//左边再走
		//左边找大
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}

		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);
	return left;
}

5.1.2快速排序（递归-挖坑法）

第一个问题的动态图演示（挖坑法）：
数据结构--八大排序
代码(挖坑法)：

//一趟快速排序(挖坑法)
int Partion2(int* arr, int left, int right)
{
	int key = arr[left];
	int pivot = left;
	while (left < right)
	{
		//右边先走，找小
		while (left < right && arr[right] >= key)
		{
			right--;
		}
		arr[pivot] = arr[right];
		pivot = right;

		//左边再走，找大
		while (left < right && arr[left] <= key)
		{
			left++;
		}
		arr[pivot] = arr[left];
		pivot = left;
	}
	arr[pivot] = key;
	return pivot;
}

5.1.3快速排序（递归-前后指针）

第一个问题的动态图演示（前后指针）：
数据结构--八大排序

代码（前后指针）：

//一趟快速排序(前后指针)
int Partion3(int* arr, int left, int right)
{
	assert(arr);

	int pre = left;
	int cur = pre + 1;
	int keyi = left;
	while (cur <= right)
	{
		if (arr[cur] < arr[keyi])
		{
			Swap(&arr[cur], &arr[++pre]);
		}
		cur++;
	}
	Swap(&arr[pre], &arr[keyi]);
	return pre;

}

第二个问题与第三个问题：
数据结构--八大排序
数据结构--八大排序
快速排序递归版代码（Hoare）：

//一趟快速排序
int Partion(int* arr, int left, int right)
{
	assert(arr);
	int keyi = left;

	while (left < right)
	{
		//左边是key值，让右边先走
		//右边找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

		//左边找大
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}

		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);
	return left;
}


//快速排序
void QuickSort(int* arr, int left, int right)
{
	assert(arr);

	if (left >= right)
	{
		return;
	}

	int keyi = Partion(arr, left, right);

	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi+1, right);

}

当待排序的数组内的值都是同一个值且数量很多时递归版快速排序容易出现栈溢出的情况，为了优化这一现象就有了非递归版快速排序。
快速排序的非递归算法基本思路：
 1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
 2、当栈不为空时，读取栈中的信息（一次读取两个：一个是L，另一个是R），然后调用某一版本的单趟排序，排完后获得了key的下标，然后判断key的左序列和右序列是否还需要排序，若还需要排序，就将相应序列的L和R入栈；若不需排序了（序列只有一个元素或是不存在），就不需要将该序列的信息入栈。
 3、反复执行步骤2，直到栈为空为止。
图示：
数据结构--八大排序

5.2快速排序（非递归）

快速排序非递归代码：

/快速排序（非递归）
void QuickSortNonR(int* arr, int left, int right)
{
	assert(arr);

	Stack ST;
	Init_Stack(&ST);
	Push_Stack(&ST, left);
	Push_Stack(&ST, right);
	while (!IsEmpty(&ST))
	{
		int end = Top_Stack(&ST);
		Pop_Stack(&ST);

		int begin = Top_Stack(&ST);
		Pop_Stack(&ST);

		//[begin,keyi-1] keyi [keyi+1,end]
		int keyi=Partion1(arr, begin, end);

		if (keyi + 1 < end)
		{
			Push_Stack(&ST, keyi + 1);
			Push_Stack(&ST, end);
		}

		if (begin < keyi - 1)
		{
			Push_Stack(&ST, begin);
			Push_Stack(&ST, keyi - 1);
		}
	}
	Destroy_Stack(&ST);
}

5.3快速排序的特点

1.快速排序很怪，为什么呢？这个排序排乱序的数组贼快，但是排有序数组慢的离谱。
比如：
数据结构--八大排序
为了避免最坏情况的发生，做了个三数取中的小优化
优化代码：

//三数取中
int GetMidIndex(int* arr, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + (right - left) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		//arr[left]<arr[mid]   arr[mid]>arr[right]
		else if (arr[right] < arr[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	//arr[left] > arr[mid]
	else
	{
		if (arr[mid] > arr[right])
		{
			return mid;
		}
		///arr[left] > arr[mid]  arr[mid] < arr[right]
		else if (arr[left]>arr[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	return 1;
}
//一趟快速排序(Hoare)
int Partion1(int* arr, int left, int right)
{
	assert(arr);
	int keyi = left;

	while (left < right)
	{
		//左边是key值，让右边先走
		//右边找小
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}

		//左边找大
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}

		Swap(&arr[left], &arr[right]);
	}
	Swap(&arr[left], &arr[keyi]);
	return left;
}
//快速排序
void QuickSort(int* arr, int left, int right)
{
	assert(arr);
	int midi = GetMidIndex(arr, left, right);
	Swap(&arr[midi], &arr[left]);

	if (left >= right)
	{
		return;
	}

	int keyi = Partion2(arr, left, right);

	QuickSort(arr, left, keyi - 1);
	QuickSort(arr, keyi+1, right);
}

通过这样的优化如果快速排序遇到最坏情况，那么最坏情况直接变成最好情况。

  • 快排的时间复杂度： O(N*logN)
  • 空间复杂度： O(logN)
  • 稳定性：不稳定
    快速排序不稳定说明（图示）：
    数据结构--八大排序

6.堆排序

6.1堆排序的思想

基本思想：
数据结构--八大排序
上面排序的思想已经大致清楚了，那么怎么建堆呢？怎么把一个数组建成堆呢？
思路1：将数组中从第二个元素开始利用向上调整函数建堆。
数据结构--八大排序
向上调整代码：

//向上调整
void AjustUp(HeapDateType* arr, int child)
{
	assert(arr);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		//大于号是大堆，小于号是小堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[parent], &arr[child]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//构建大堆
//方法1
for (int i = 1; i < n; i++)
{
	AjustUp(a, i);
}

思路2：将数组中从倒数第一个非叶子节点开始利用向下调整函数建堆。
数据结构--八大排序
向下调整代码：

//向下调整
void AjustDown(HeapDateType* arr, int len, int parent)
{
	assert(arr);
	int child = parent * 2 + 1;

	while (child < len)
	{
		//大于号是大堆，小于号是小堆
		if (child + 1 < len && arr[child + 1] > arr[child])
		{
			child++;
		}

		//大于号是大堆，小于号是小堆
		if (arr[child] > arr[parent])
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//方法2
//n-1是最后一个叶子节点  (n-1-1)/2是最后一个叶子节点的父亲节点
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AjustDown(a, n, i);
}

堆排序代码：

void HeapSort(int* a, int n)
{
	assert(a);
	//构建大堆
	//方法1
	//for (int i = 1; i < n; i++)
	//{
	//	AjustUp(a, i);
	//}	//方法2
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AjustDown(a, n, i);
	}
	for (int end = n - 1; end > 0; end--)
	{
		Swap(&a[end], &a[0]);
		AjustDown(a, end, 0);
	}
}

6.2堆排序的特点

  • 时间复杂度：O（N*logN）
  • 空间复杂度：O(1)
  • 稳定性：不稳定
    数据结构--八大排序

7.归并排序

7.1归并排序（递归）

归并排序（递归）的思想
归并排序是采用分治法的一个非常典型的应用。其基本思想是：将已有序的子序合并，从而得到完全有序的序列，即先使每个子序有序，再使子序列段间有序。
数据结构--八大排序
将两个有序的数组归并成一个有序数组动态图：
数据结构--八大排序
数据结构--八大排序
递归版归并排序：
上面的图示其实已经可以看出有了写递归的影子了。想要对一个数组进行排序，就需要两个有序的子数组来归并，而这两个子数组想要有序也需要其自身的两个有序子数组来归并,就这样套娃模式就开始了，对付套娃还得是递归才行。
递归版归并排序写代码前分析：
数据结构--八大排序
数据结构--八大排序
递归版归并排序代码：

void _MergeSort(int* arr, int left, int right, int* temp)
{

	if (left >= right)
	{
		return;
	}
	int mid = (left + right) / 2;

	//递归
	_MergeSort(arr, left, mid, temp);
	_MergeSort(arr, mid+1, right, temp);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;

	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			temp[i++] = arr[begin1++];
		}
		else
		{
			temp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		temp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[i++] = arr[begin2++];
	}

	for (int i = left; i <= right; i++)
	{
		arr[i] = temp[i];
	}
}

//归并排序
void MergeSort(int* arr, int n)
{
	assert(arr);

	int* temp = (int*)malloc(sizeof(int) * n);
	if (temp == NULL)
	{
		perror("MergeSort::malloc");
		return;
	}
	_MergeSort(arr, 0, n - 1, temp);

	free(temp);
	temp = NULL;
}

7.2归并排序（非递归）

在上面我们知道快速排序有递归版与非递归版，那么归并排序有非递归吗？因为递归的缺点还是很明显的，在有非递归下最好还是使用非递归。其实是有非递归的归并排序的。但是这个写法需要注意的东西很多，直接上代码很容易看懵，所以且让我慢慢道来。
归并排序（非递归）的基本思想（图示）：
数据结构--八大排序
理想情况下的代码：

//归并排序（非递归）
void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int gap = 1;
	int* temp = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int i = 0; i <= n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;
			

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}
			while (begin1<=end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2<=end2)
			{
				temp[j++] = arr[begin2++];
			}
		}
		
		for (int j = 0; j <n; j++)
		{
			arr[j] = temp[j];
		}
		gap *= 2;
	}
	free(temp);
	   
}

那怎在非理想进行非递归归并排序呢？首先就要考虑非理想情况下与理想情况下的差别有哪些。
我们仔细观察会发现理想情况下的begin1、end1、begin2、end2是不会出现越界的，而非理想情况下end1、begin2、end2是会出现越界的。
数据结构--八大排序
所以只需要对这三种情况分别处理下就好了
第一种修正方式图示：
数据结构--八大排序
非递归归并排序代码（第一种）：

/归并排序（非递归）
void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int gap = 1;
	int* temp = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int i = 0; i <= n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;
			//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);
			
			//end1、begin2、end2越界
			if (end1 >= n)
			{
				end1 = n - 1;
			}
			//begin2、end2越界不进行归并
			if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			//printf("[%d,%d] [%d,%d] ", begin1, end1, begin2, end2);

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}
			while (begin1<=end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2<=end2)
			{
				temp[j++] = arr[begin2++];

			}
		}
		for (int j = 0; j <n; j++)
		{
			arr[j] = temp[j];
		}
		gap *= 2;
		//printf("\n");
	}

	free(temp);
	   
}

第二种修正方式：
数据结构--八大排序
非递归归并排序代码（第二种）：

//归并排序（非递归）法2
void MergeSortNonR(int* arr, int n)
{
	assert(arr);
	int gap = 1;
	int* temp = (int*)malloc(sizeof(int) * n);
	while (gap < n)
	{
		for (int i = 0; i <= n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;

			int j = begin1;

			//end1或者begin2越界
			if (end1 >= n||begin2>=n)
			{
				break;
			}
			//end2越界
			if (end2 >= n)
			{
				end2 = n - 1;
			}

			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] < arr[begin2])
				{
					temp[j++] = arr[begin1++];
				}
				else
				{
					temp[j++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[j++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[j++] = arr[begin2++];

			}
			for (int j = i; j <=end2; j++)
			{
				arr[j] = temp[j];
			}
		}
	
		gap *= 2;
	}

	free(temp);

}

7.2归并排序的特点

  • 1.时间复杂度：O(N*logN)
  • 2.空间复杂度：O(N)
  • 3.稳定性：不稳定

8.计数排序

8.1计数排序的思想

图示：
数据结构--八大排序文章来源地址https://www.toymoban.com/news/detail-432448.html

//计数排序
void CountSort(int* arr,int n)
{
	assert(arr);

	int max = arr[0], min = arr[0];
	//找出最大、最小数
	for (int i = 0; i < n; i++)
	{
		arr[i] = arr[i];
		if (arr[i] < min)
		{
			min = arr[i];
		}
		if (arr[i] > max)
		{
			max = arr[i];
		}
	}
	int rang = max - min + 1;
	int* temp = (int*)malloc(sizeof(int) * rang);
	//初始化temp数组
	memset(temp, 0, sizeof(int) * rang);

	//开始在temp数组里计数
	for (int i = 0; i < n; i++)
	{
		temp[arr[i] - min]++;
	}

	//排序arr
	int j = 0;
	for (int i = 0; i < rang; i++)
	{
		while (temp[i])
		{
			arr[j++] = i + min;
			temp[i]--;
		}
	}
	free(temp);
}

8.2计数排序的特点

  • 1.计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费，并且计数排序只适用于整型排序，不适用与浮点型排序。
  • 2.时间复杂度：O(N+range)
  • 3.空间复杂度：O(range)
  • 4.稳定性：不稳定

到了这里，关于数据结构--八大排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构--八大排序】之快速排序

    【数据结构--八大排序】之快速排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 前言： 前面，我花费

    2024年02月08日
    浏览(51)
  • 数据结构--八大排序

    数据结构--八大排序

    插入排序的思想跟摸牌很相似，从我们摸到第二张牌的开始，依次将摸到到牌依次有序的插入到手中，最后手牌变成了有序。 有了大致的思路，接下来就要细分插入排序的细节。 首先考虑某一趟的插入排序。为什么先考虑某一趟呢？因为当需要解决的问题比较复杂时先将问

    2024年02月02日
    浏览(43)
  • 【数据结构】八大排序算法

    【数据结构】八大排序算法

    目录 一、直接插入排序 二、希尔排序 三、选择排序  3.1、简单选择排序  3.2、快速选择排序(Top K问题) 四、堆排序 五、冒泡排序 六、快速排序   1、递归版本      1.1 hoare 法      1.2 挖坑法      1.3 前后指针法   2、非递归版本   3、快速排序的优化      3.1 三数取中

    2024年02月09日
    浏览(89)
  • 【数据结构】八大排序 (三）

    【数据结构】八大排序 (三）

    目录 前言： 快速排序 快速排序非递归实现 快速排序特性总结 归并排序 归并排序的代码实现 归并排序的特性总结 计数排序 计数排序的代码实现 计数排序的特性总结 前文快速排序采用了递归实现，而递归会开辟函数栈帧，递归的深度越深，占用栈区的空间就越大， 栈区的

    2024年02月01日
    浏览(45)
  • 【数据结构】八大排序(二)

    【数据结构】八大排序(二)

    😛作者：日出等日落 📘 专栏：数据结构 在最黑暗的那段人生，是我自己把自己拉出深渊。没有那个人，我就做那个人。                                                                                                                                     

    2024年02月03日
    浏览(34)
  • 【数据结构】八大排序（一）

    【数据结构】八大排序（一）

    目录 前言： 直接插入排序 直接插入排序代码实现 直接插入排序特性总结 希尔排序 希尔排序代码实现 希尔排序特性总结 直接选择排序 直接选择排序代码实现 直接选择排序特性总结 堆排序 堆的向下调整算法 建堆 堆排序代码实现 堆排序特性总结 排序即使得一串记录，按照

    2024年02月03日
    浏览(36)
  • 【数据结构】八大排序详解

    【数据结构】八大排序详解

    🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。 🐌 个人主页：蜗牛牛啊 🔥 系列专栏：🛹数据结构、🛴C++ 📕 学习格言：博观而约取，厚积而薄发 🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与

    2024年02月13日
    浏览(38)
  • 「数据结构」八大排序1

    「数据结构」八大排序1

    🎇 个人主页 ：Ice_Sugar_7 🎇 所属专栏 ：初阶数据结构 🎇 欢迎点赞收藏加关注哦！ 插排就是将一个元素插入一个有序序列中合适的位置，分为 直接插入排序 和 希尔排序 流程如下： ①保存待插入的值：假设某一趟中有序序列最后一个元素下标为end，先 保存（end+1）位置的

    2024年02月03日
    浏览(36)
  • 【数据结构】八大排序(一)

    【数据结构】八大排序(一)

    😛作者：日出等日落 📘 专栏：数据结构         珍惜自己的时间，利用好每一份每一秒。做事不放过没一个细节，小心谨慎，细致，能够做到这些，还有什么是不可能的呢? 目录 ​编辑 ✔排序的概念： ✔排序的应用： ✔常见的排序算法： ✔常见排序算法的实现： ✔插入

    2024年02月03日
    浏览(58)
  • （数据结构）八大排序算法

    （数据结构）八大排序算法

       排序 (Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个 数据元素 （或记录）的任意序列，重新排列成一个有序的序列。 介绍 ：将待排的数，和有序的数比较，直到一个合适的位置，然后进行插入。 示图 ： 将待排数4，与有序数对比，然后插入到

    2023年04月21日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包