当前位置：首页 » 《随便一记》 » 正文

【C语言实现】常见八大排序万字详解_SimplexXx0的博客

17 人参与  2022年03月29日 11:26  分类 : 《随便一记》  评论

点击全文阅读


文章目录

    • 插入排序
    • 希尔排序
    • 选择排序
    • 堆排序
    • 冒泡排序
    • 快速排序
      • 1.Hoare版本（左右指针法）
      • 2.挖坑法
      • 3.前后指针法
      • 4.快排非递归写法
    • 归并排序
    • 计数排序

八种排序的动图展示讲解

插入排序

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。 按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序 。类似打扑克牌插入
1.思想：

假设一组数有n个元素，前n-1个已有序，记第n-1个位置为end，
用一个临时变量x记录第n个元素的值，x依次从end开始依次往前比，比x大的往后挪，找到比x小的停下，把x插入到它的后面。类似于打扑克牌。

2.图解：

单趟排序
在这里插入图片描述
整组排序

按照单趟排序方法对整组进行多趟排序

在这里插入图片描述3.代码实现

void InsertSort(int*a, int n)
{
	for(int i = 0; i < n-1;i++)
	{
		int end = i;
		int tem = a[end+1];
		while(end > 0)
		{
			if(a[end] > tem)//比tem大往后挪
			{
				a[end+1] = a[end];
				end--;
			}
			else//比tem小停止
			{
				break;
			}				
		}
		a[end+1] = tem;//在后面把tem插入
	}
}

4.性能分析

  • 时间复杂度：O(N^2)
  • 空间复杂度: O(1)
  • 稳定性：稳定

希尔排序

希尔排序也是一种插入排序，是直接插入排序算法的一种更高效的改进版本，又称“缩小增量排序”。希尔排序是非稳定排序算法。

1.思想：

把一个数组分成gap组，gap也是每组相邻两个元素之间的间距。对每一组进行直接插入排序（又称预排序），使整个数组接近有序。完成预排序后，使gap=1，也就是在最后对整个数组进行一次单趟排序，数组有序，完成排序。
可以进行多次预排序，使数组更加接近有序（具体做法:完成一趟预排序后，改变gap再次进行预排序）
gap越小，排的越慢，数组越接近有序。

2.图解
在这里插入图片描述

3.代码实现

void ShellSort(int* a, int n)
{

	for (int gap = n / 2; gap > 0; gap /= 2)//改变gap，进行多次预排序
	{
		for (int i = 0; i < n - gap; i++)//每次对一个数在其本组上进行单趟插入排序，
		//i++相当于全部的组轮序着排，并不是一组先排完后再排另一组
		{
			int end = i;//这里开始和插入排序一模一样，只是把间距变成了gap
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
						end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}

}

4.性能分析

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

选择排序

选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。

1.思想：

  • （一次找一个数）遍历找到最小的数放到最边上

  • （一次找两个数）遍历数组，找出最大的数和最小的数，分别放到最两边，再对中间的无序数组再选最大最小，放到中间无序数列的两头

2.图解
一次选一个数

在这里插入图片描述
一次选两个数

选出小的放左边，大的放右边，图像应该比较好想象。

3.代码实现

void SelectSort(int* a, int n)
{
	int begin = 0; int end = n - 1;
	while (begin < end)
	{
		int min = begin; int max = end;
		for (int i = begin; i <= end; i++)
		{
			if (a[i] < a[min])
				min = i;         //mini记录查找过程中最小值的位置下标
			if (a[i] > a[max])
				max = i;         //maxi记录查找过程中最大值的位置下标
		}
		
		Swap(&a[min], &a[begin]);  //把找到的最小值放到数组最左边
		if (max = begin)
			min = max;
		Swap(&a[max], &a[end]);     //把找到的最大值放到数组最右边
	}
	//控制范围，对剩下中间的数再进行选择、排序
	++begin;
	--end;	
}

代码注解

代码中两个Swap函数之间的if条件判断，是为了防止出现一次选两个数的特殊情况而做的修正。如果max的位置和begin位置相同，那min和begin交换后，max位置的原始值已经变了，如果不修正就进行max和end交换会发生错误。

在这里插入图片描述

Swap(&a[min], &a[begin]); 
	if (max = begin)
		min = max;
Swap(&a[max], &a[end]);

堆排序

1.思想：

需要用到二叉树大小堆的概念。堆的逻辑结构是一棵完全二叉树，物理结构是数组。给我们一个数组，要排升序，我们就要把数组建成大堆；排降序，就建小堆。这里我们用向下调整AdjustDown()来建一个大堆（父节点比任何一个子节点大叫大堆）
在这里插入图片描述

完成一棵树（或子树）的堆排序操作图解

在这里插入图片描述

向下调整的代码实现

void Swap(int* x,int* y)//交换函数
{
	int tem = *x;
	*x = *y;
	*y = tem;
}

void AdjustDown(int*a,int n,int root)
{
	int child = root*2 + 1;
	int parent = root;
	for(child < n)
	{	//找到两个孩子中大的那一个
		if(a[child+1]<n && a[child+1]>a[child])
			child++;
		if(a[child]>a[parent])
		{
			Swap(&a[child],&a[parent]);
			parent = child;//交换完后再往下对比
			child = parent*2 - 1;
		}

对于要调一棵树，需要先保证把它的子树全部调成堆。所以我们可以从最后一棵子树的父亲开始调整，调完一棵子树再从此父节点依次往前一个结点调，最后完成整棵树的堆排序。

在这里插入图片描述

调完堆后就可以对堆里的数据进行排序了
思路：把堆顶数据和最后一棵子树调换位置，对除了尾结点的前n-1棵树进行调堆

在这里插入图片描述

void HeapSort(int* a, int n)//堆排序
{	//排升序，先把数组建成大堆
	int parent = (n - 1 - 1) / 2;  //建大堆时，从最后一个孩子的父亲开始调
	for (int i = parent; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int end=n-1;end>=0;end--)
	{
		Swap(&a[0], &a[end]);//堆顶和最后一个孩子交换，前n-1个再调整成大堆
		AdjustDown(a, end, 0);
	}

}

冒泡排序

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

1.思想

依次比较两个相邻的元素，前一个比后一个大则交换，否则继续比较下一对（升序），一趟完之后最大的数就被排在了最后面。再对前面的数继续排序，完成整组排序。

2.图解

单趟冒泡排序
在这里插入图片描述

在这里插入图片描述
3.代码实现

void BbubleSort(int* a, int n)
{
	assert(a);
	int end = n;
	while (end > 0)
	{
		int exchange = 0;
		for (int i = 0; i < end - 1; i++)
		{
			if (a[i] > a[i + 1]) //当判断条件为if(a[i-1]>a[i]),循环条件为for(int i=1;i<end;i++)
			{
				exchange = 1;//判断是否交换过，如果一趟内未发生交换，则数组已有序，不用再排
				Swap(&a[i], &a[i + 1]);
			}
		}
		end--;
		if (exchange == 0)//如果一趟内没有发生交换，则表明数组已有序，跳出循环
		{
			break;
		}
	}

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

1.思想

这里是引用快速排序算法通过多次比较和交换来实现排序，其排序流程如下：

  • 任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序序列分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程划分各自的子序列，直到所有元素都排列在相应位置上为止。
  • 重复上述过程，可以看出，这是一个递归定义，类似二叉树的前序遍历。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。采用了分而治之的思想（分成小区间，让各自区间各自排序）
    **2.三数取中**

三数取中法：如何有效地选择基准值做key？

一般我们选最左/右边或随机选择的值来做key，不免会发生选到的就是最大值或最小值的情况，这样排序的效率就会很低。我们拿最左/右边的值和中间的值，三个值比较，取中间的不大不小的值来做key就可以解决这个问题。

int MidIndex(int* a,int left, int right)
{
	//int mid = left + right/2;  
	int mid = left + ((right - left) >> 1);//二进制往右移一位相当于除二，移两位相当于除四
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else
		{
			return a[left] < a[right] ?  right : left;
		}
	}
	else //(a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return a[right] > a[left] ? left : right;
		}
	}
}

通过基准值划分为左右子区间的常见方法

1.Hoare版本（左右指针法）

思想：

一般选最左/右边的值作为基准值key，

  • 左指针left从头开始找比key小的值，找到停下；
  • 然后右指针right从尾开始往前走，找到比key大的值，找到停下；
  • 交换此时left 和 right 的值。交换完重复步骤继续找、交换。
  • 当最后left 和 right 相遇时，把相遇位置的值和key交换。此时key的左边全部为比key小的，右边全部为比key大的。完成区间划分

使用原则

（因为最后一步要把相遇位和key交换，这样能保证key的左边比key小，key的右边比key大）

  • 选最左边的做基准值，右指针先走→（右边先走找小于key的值，一直找如果找不到，走到 left 相遇停下，left位是比key小的，保证了相遇位比key值小）

  • 选最右边的做基准值，左指针先走→（同上理，能保证相遇位比key大）

代码实现

int partition1(int* a, int left, int right)//单趟排序
{
	int mid = MidIndex(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//把中间数位置换为left

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
			right--;
		while (left < right && a[left] <= a[keyi])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;

特殊场景

这里是引用像这两种情况left 和 right 找不到相应的值就会一直走，导致越界，为了防止越界，要在while循环里加判断条件 left < right

递归程序缺陷：递归深度太深会导致栈溢出

2.挖坑法

挖坑法是左右指针法的一种变形
思想：

  • 将第一个值作为基准值保存到临时变量key里，形成一个坑位pivot
  • 假设选左边做坑，那右边先走，找到小，放进坑里，右就变成了新的坑
  • 然后左边走，找到大，放到坑里，左变成新的坑。然后右边走，重复步骤。
  • 相遇停下的时候把key值填到pivot坑中

图解

在这里插入图片描述
代码实现

int partition2(int* a, int left,int right)
{
	int mid = MidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		while(left<right && a[right] > key)
			right--;
		a[pivot] = a[right];
		pivot = right;

		while (left < right && a[left] < key)
			left++;
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}

3.前后指针法

思想：

  • 初始时，prev指针指向序列开头，cur指针指向prev的后一个位置，取基准值key
  • cur找小，找到小后，++prev往后一步，把 cur 和 prev 交换（相当于找到小的往前放）
  • cur 走完整个序列，把 prev 和 key 交换。

图解：
在这里插入图片描述

代码实现

int partition3(int* a, int left, int right)
{
	int mid = MidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{                      //如果一开始cur就比key小，prev往后走就赶上了cur，交换后相当于没交换，所以如果prev的下一个是cur的让它们两个一起往后走一步就行了
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	return prev;
}

递归法小区间优化

递归调用层次越深，区间划分越多，递归调用的次数就越多，效率就会降低。我们可以考虑后面的几层用其他排序方法排序，可以大大减少调用递归的次数，防止栈溢出，提升排序效率。

代码汇总

//三数取中
int MidIndex(int* a,int left, int right)
{
	//int mid = left + right/2;  
	int mid = left + ((right - left) >> 1);//二进制往右移一位相当于除二，移两位相当于除四
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else
		{
			return a[left] < a[right] ?  right : left;
		}
	}
	else //(a[left] > a[mid])
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return a[right] > a[left] ? left : right;
		}
	}
}

//区间划分1.hoare左右指针
int partition1(int* a, int left, int right)//单趟排序
{
	int mid = MidIndex(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//把中间数位置换为left

	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
			right--;
		while (left < right && a[left] <= a[keyi])
			left++;
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	return left;
}



//区间划分2：挖坑法。
// 思想：选left或right做坑，这里选left做坑pivot，key记录当前值，right先走，right找到比key小的数停下，
//       把right填到坑里,然后right做坑，left走，找到大于key的数，填进坑，left做坑，right走
int partition2(int* a, int left,int right)
{
	int mid = MidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		while(left<right && a[right] > key)
			right--;
		a[pivot] = a[right];
		pivot = right;

		while (left < right && a[left] < key)
			left++;
		a[pivot] = a[left];
		pivot = left;
	}
	a[pivot] = key;
	return pivot;
}
//区间划分3：前后指针
int partition3(int* a, int left, int right)
{
	int mid = MidIndex(a, left, right);
	Swap(&a[left], &a[mid]);

	int key = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{

		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	return prev;
}

//快排
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;
	
	if ((right - left) + 1 < 10)//小区间优化。递归到最后几层时，调用的栈帧次数很大，第n层调用2^（n-1)次
	{                           //递归越到后面越接近有序，后面几层可以考虑用其他方法排序 
		InsertSort(a + left, right - left + 1);//使用插入排序更方便，适应性更强
	}
	else
	{
		int keyi = partition2(a, left, right);

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

}

4.快排非递归写法

递归深度太深的时候一般使用非递归
思想：

快排非递归需要用到栈来实现，在思想上和递归类似（也可以用队列模拟实现，类似层序遍历），借助一个和原数组一样大小的栈数组来代替栈帧保存各个子区间。一个大区间划分成两个区间，对一个区间进行划分排序，另一个区间就先放在栈里。

  • 把要排序的区间范围 begin 和 end 存到栈，取出 end 和 begin，对[begin,end]排序划分成两个区间 [begin，keyi-1], keyi, [keyi+1,end]，（左区间比keyi小，右区间比keyi大，keyi相当于已经被排好的数据，存在原数组的相应位置）
  • 把划分出来的区间范围keyi+1，end,begin，keyi-1存到栈里，取出左区间进行排序划分。重复步骤完成排序。

要先排左区间，就要先存右区间再存左区间，因为栈取数据是后进先出的原则

代码实现

//快速排序的非递归实现。

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	StackPush(&st, left);//把区间范围存到栈里
	StackPush(&st, right);//栈是后进先出，

	while (!StackEmpty(&st))
	{
		int end = StackTop(&st);
		StackPop(&st);

		int begin = StackTop(&st);
		StackPop(&st);

		int keyi = partition3(a,begin,end);
//此时可以分为区间 [begin,kei-1],keyi,[kei+1,end]
//左区间比keyi小，右区间比keyi大，keyi相当于已经被排好的数据
		if (keyi + 1 < end)
		{
			StackPush(&st, keyi + 1);
			StackPush(&st, end);
		}
		if (begin < keyi - 1)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi - 1);
		}
	}

	StackDestroy(&st);
}

图解：
非递归的优势：

非递归的栈空间是malloc出来的，使用的是存储空间中的堆空间（可以达到4G）。而递归的本质是要开辟栈帧，使用的是存储空间中的栈空间（一般只有4Mb-8Mb）,不会出现溢出的风险

归并排序

归并排序是将两个有序的区间合并成一个有序的数组，需要借助一个额外的数组空间来完成。也是一个分治递归的典范。

思想：

  • 把一个数组划分成两个区间 ，想让左右区间有序，就要对左右区间再继续划分直至不可划分。
  • 从最后划分出的最小区间开始往回归并，每两组在额外空间里归并为一组，归并完放回原数组，再归并它的右区间。到最后整个归并完后，放回原数组。

图解：
在这里插入图片描述
在这里插入图片描述
代码实现

//归并函数的子函数，实现区间的划分和排序
void _MergeSort(int* a, int left, int right, int* tem)
{
	if (left >= right)
		return;

	int mid = left + (right - left) / 2;
	//[left,mid]  [mid+1,right]
	_MergeSort(a,left,mid,tem);        //类似二叉树后序
	_MergeSort(a, mid + 1, right, tem);

	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tem[i++] = a[begin1++];
		}
		else
		{
			tem[i++] = a[begin2++];
		}
	}
	//两组中必有一组先排完，把未排完的一组放到后面
	while (begin1 <= end1)
	{
		tem[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tem[i++] = a[begin2++];
	}
	//把在tmp数组归并好的值放回原数组
	for (int j = left; j <= right; j++)
	{
		a[j] = tem[j];
	}
}
//归并函数
void MergeSort(int* a, int n)
{
	int* tem = (int*)malloc(sizeof(int) * n);//开辟额外数组空间
	if (tem == NULL)
	{
		printf("malloc failed\n");
		exit(-1);
	}
	_MergeSort(a, 0, n - 1, tem);   //利用子函数进行排序

	free(tem);
	tem = NULL;
}

性能分析

时间复杂度：（N*logN）
空间复杂度：O(N)
稳定性:稳定
缺点：需要额外开辟空间

计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 [1] 当然这是一种牺牲空间换取时间的做法，而且当O(k)>O(nlog(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(nlog(n)), 如归并排序，堆排序

思想：

  • 找出数组中最大和最小的值，用来确定需要开辟的count数组的大小
  • count数组里的所有值全部初始化成0，遍历原数组，利用count数组统计原数组的值出现的次数，出现一次就把这个值在count数组里相对映射的值加一
  • 按顺序把count数组里的记录的相对值放回原数组

图解:
在这里插入图片描述
代码实现

void Countsort(int* a, int n)
{
	int min = a[0]; int max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	
	int range = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * range);
	memset(count, 0, sizeof(int) * range);
	if (count == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	//统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}
	//根据次数进行排序
	int j = 0;
	for (int i = 0; i < range; i++)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}

总结
在这里插入图片描述


点击全文阅读


本文链接：http://zhangshiyu.com/post/36959.html

排序  递归  数组  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 《无敌天帝》小说主角萧宁萧炎章节免费在线阅读
  • 魂力升级最新章节，魂力升级免费阅读
  • 韩枫唐三（魂力升级）小说大结局无弹窗在线阅读
  • 小说《心肝宠》全文免费阅读
  • 爆款小说《主母爱谁当！纨绔夫君为我挣诰命》主角沈棠宁池宴全文在线完本阅读
  • 知乎小说主母爱谁当！纨绔夫君为我挣诰命主角是沈棠宁池宴全文阅读
  • 闲时修仙时闲时星，闲时修仙免费在线阅读
  • 秦方霸天（暴击锻造）小说大结局无弹窗在线阅读
  • 首辅家的长孙媳春归阿娘，首辅家的长孙媳在线无弹窗阅读
  • 男女主人公萧飞唐雨馨小说妻子助教在线免费阅读
  • 小说《太荒浮沉录》在线全文阅读
  • 冲喜一年后，我和隐婚老公第一次见面了沈知意薄御小说免费阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1