C语言常见排序算法之交换排序(冒泡排序,快速排序)

目录
  • 前言
  • 1.交换排序——冒泡排序
    • 1.1 算法思想
    • 1.2 动图演示
    • 1.3 冒泡最好的情况
  • 2. 交换排序——快速排序
    • 2.1 快速排序——挖坑法
      • 快排的缺点
      • 三数取中法
    • 2.3 快速排序——左右指针法
    • 2.4 前后指针法

前言

本期为大家带来的是常见排序算法中的交换排序,主要有冒泡排序,快速排序,快排分享了三种算法:挖坑法,左右指针法,前后指针法,以及两种优化方式:解决快排最坏情况的“三数取中”,避免递归次数过多的"小区间优化",

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

1.交换排序——冒泡排序

冒泡排序(Bubble Sort)基本思想: 冒泡排序,类似于水中冒泡,较大的数沉下去,较小的数慢慢冒起来,假设从小到大,即为较大的数慢慢往后排,较小的数慢慢往前排。直观表达,每一趟遍历,将一个最大的数移到序列末尾。也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,将他们之间小的,或者大的值交换过来。遍历数列的工作是重复地进行,直到没有再需要交换的,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

1.1 算法思想

比较相邻的元素,如果前一个比后一个大,交换之。
第一趟排序第i个和第i+1个比较与交换,随后第i+1个和第i+2个一对比较交换,这样直到倒数第n-1个和最后n个,将最大的数移动到最后一位。
第二趟将第二大的数移动至倒数第二位

……

1.2 动图演示

 算法实现:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10

Swap(int *p1, int * p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void Print(int *a)
{
	for (int i=0;i<N;i++)
	{
		printf("%d ",a[i]);
	}
}
void BubbleSort(int* a, int n)
{

	for (int j=0;j<n;++j)
	{
		int size = 0;
		for (int i=1;i<N-j;++i)
		{
			if (a[i-1]>a[i])
			{
				Swap(&a[i-1],&a[i]);
				size =1;
			}
		}
		if (size==0)
		{
			break;
		}
	}
}
int main()
{
	int a[N] = {0};
	for (int i=0;i<N;++i)
	{
		a[i] = rand();
	}
	BubbleSort(a,N);
	Print(a);

	return 0;
}

其中有一段优化程序,是定义一个变量判断排序是否在做无效操作,当内循环处于交换状态时,则数据未排序完毕,否则视为,数据已有序,我们就可以break;中止掉程序,避免做无用遍历。

1.3 冒泡最好的情况

待排序数列有序时,时间复杂度是O(N)。外循环只执行一次,内循环N-1,N-2,N-3……

冒泡排序的特性总结:

  • 1. 冒泡排序是一种非常容易理解的排序
  • 2. 时间复杂度:O(N^2)
  • 3. 空间复杂度:O(1)
  • 4. 稳定
  • 性:稳定

总结:

总的来说,冒泡排序是一种可以的排序,比直接选择排序要好,虽然有优化程序,但是,整体算法效率跟其他排序来比,还是差一些,比较适合新手学习。

2. 交换排序——快速排序

快速排序(Quicksort)是Hoare于1962年提出的一种二叉树结构的交换排序方法,有时候也叫做划分交换排序,是一个高效的算法,其基本思想为:任取待排序 元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有 元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所 有元素都排列在相应位置上为止。这是一个分治算法,而且它就在原地交换数据排序。

是目前已知最快的排序算法,会比一般的排序更节省时间。

2.1 快速排序——挖坑法

算法实现:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		int pivot = begin;//记录坑位的下标
		int key = a[begin];//坑值

		while (begin < end)
		{
			//右边找小,放到左边
			while (begin < end && a[end] >= key)//与坑值比较
			{
				--end;
			}
			//小的放在左边的坑里,自己形成了新的坑位
			a[pivot] = a[end];
			pivot = end;

			//左边找大,放在右边
			while (begin < end && a[begin] <= key)//与坑值比较
			{
				++begin;
			}
			//大的放在右边的坑里,自己形成了新的坑位
			a[pivot] = a[begin];
			pivot = begin;
		}
		//最后将坑值给到坑位
		a[pivot] = key;
		//[left,right]
		//[left,pivot-1]  [pivot+1,right]
		//左子区间和右子区间有序,我们就有序了,如何让他们有序?分治递归
		QuickSort(a, left, pivot - 1);
		QuickSort(a, pivot + 1, right);
	}
	else
	{
		return;
	}
}
int main()
{
	int a[10] = {0,9,5,6,3,2,1,7,8,4};
	//挖坑法
	QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
	Print(a,sizeof(a) / sizeof(a[0]));
	return 0;
}

快排的缺点

根据上面的代码,我们来分析一下快排的缺点:

如何解决快排对有序数据排序效率很差的方法?

三数取中法

所谓三数取中,不是取最大值,最小值,以及他们的中间值,而是取左边(begin)、右边(end)和中间(begin+end)/2;

在有序的情况下中间的值刚好就是二分,将取出的值作为坑位,就不会出现最差的这种情况。我们依旧使用区间的开头作为“坑值”,但是要使用三数取中的逻辑。

选坑位:

int begin = left;
int end = right;
//使用三数取中选“坑值”,用mid存储其下标
int mid = GetMidIndex(a, begin, end);
//将区间首值当作坑位
//坑值与首值交换,避免算法混乱
//一般我们会将区间首值作为坑值
Swap(&a[begin], &a[mid]);//传地址调用
//存储坑值
int key = a[begin];

三数取中 GetMidIndex();

int GetMidIndex(int *a,int left,int right)
{
    //二分
	int mid = (right - left) / 2;
	if (a[left]<a[mid])
	{
		if (a[left]<a[right])
		{
			if (a[mid]<a[right])
			{
				return mid;
			}
			else  //a[mid]>=a[right]
			{
				return right;
			}
		}
		else   //a[left]>=a[right]
		{
			return left;
		}
	}
	else  //a[left]>=a[mid]
	{
		if (a[mid]<a[right])
		{
			if (a[left]<a[right])
			{
				return left;
			}
			else  //a[left]>=a[right]
			{
				return right;
			}
		}
		else  //a[mid]>=a[right]
		{
			return mid;
		}
	}
}

交换Swap();

//交换
void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

经过三数取中的处理,就不会出现快排的最坏情况,但也几乎不会成为最好的情况,有利有弊,我们在面试的过程中只需要写基础版的快排即可,以防时间不够。

 小区间优化:

关于如果处理数据多,相应的递归次数多,会不会影响操作快排的性能?

当我们在使用快排对大量数据进行排序时,我们可以采用小区间优化,减少递归次数,达到优化程序得到目的。

对当待处理数据大于10的子序列进行快排递归。

对当待处理数据低于10的子序列进行直接插入排序进行排序,避免递归次数过多。

这个10不是固定的,可以根据处理的数据量调整。

//区间[left,right]
//左区间[left,pivot-1]  右区间[pivot+1,right]
//左子区间和右子区间有序,我们就有序了,如何让他们有序?分治递归
// 小区间优化
if (pivot - 1 - left > 10)//对当待处理数据大于于10的子序列进行快排递归排序
{
	//快排
	QuickSort(a,left,pivot-1);
}
else
{
	//采用直接插入排序,对当待处理数据低于10的子序列进行排序,避免递归
	InsertSort(a+left,pivot-1-left+1);//为什么最后要加1,例如:区间[0,9]实际上有10个数
}

if (right - (pivot + 1) > 10)
{
	QuickSort(a,pivot+1,right);
}
else
{
	InsertSort(a + pivot+1, right-(pivot+1)+1);

}

如果大家有想了解直接插入排序可以查看博主的另一篇:C语言常见排序算法之插入排序(直接插入排序,希尔排序)

2.3 快速排序——左右指针法

根据上图的示例我们应该能够理解左右指针法是什么样的逻辑,跟挖坑法是一样的思想,单趟排序完毕实现左边比坑位小,右边比坑位大。但是即使左右指针法跟挖坑法的思想是一样的,但是他们单趟的运算结果是不一样的。

 算法实现:

void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		int begin = left;
		int end = right;
		//选坑位
		int mid = GetMidIndex(a, begin, end);//三数取中
		Swap(&a[begin], &a[mid]);
		int key = begin;
		while (begin < end)
		{
			while (begin < end && a[end] <= a[key])
				--end;
			while (begin < end && a[begin] >= a[key])
				++begin;
			Swap(&a[begin], &a[end]);
		}
		Swap(&a[begin], &a[key]);
		//分治递归
		QuickSort(a, left, begin - 1);
		QuickSort(a, begin + 1, right);
	}
}

2.4 前后指针法

  • 采用perv记录区间第一个元素的下标,采用cur记录区间第二个元素的下标。
  • cur找小,每次遇到比key(坑值)小的值就停下来,++prev。
  • 交换prev和cur位置的值

 算法实现:

//左右指针法
void QuickSort(int* a, int left, int right)
{
	if (left < right)
	{
		//选坑位
		int mid = GetMidIndex(a, left,right);//三数取中
		Swap(&a[left], &a[mid]);
		int key = left;
		//初始化指向
		int prev = left, cur = left + 1;
		while (cur<=right)
		{
			if (a[cur] <= a[key])//&&++prev!=cur
			{
				++prev;
				//避免无效操作
				if(cur!=prev)
				Swap(&a[prev],&a[cur]);
			}
			++cur;
		}
		Swap(&a[key], &a[prev]);
		//分治递归
		QuickSort(a, left, prev - 1);
		QuickSort(a, prev + 1, right);
	}
}

快速排序的特性总结:

  • 1.快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  • 2.时间复杂度:O(N*logN)
  • 3.空间复杂度:O(logN)
  • 4.稳定性:不稳定

总结:

快排是我们一定要掌握的一种排序算法,在面试、笔试中也是很常见的,博主分享的三种方法:挖坑法,左右指针法,前后指针法,只少要掌握一种,但是要其他的方法也要知道算法思想。还有两种优化方式,小区间优化和三数取中,也要知道是什么逻辑,解决什么问题。

到此这篇关于C语言常见排序算法之交换排序(冒泡排序,快速排序)的文章就介绍到这了,更多相关C语言交换排序 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现交换排序算法(冒泡,快速排序)的示例代码

    目录 前言 一.冒泡排序 1.基本思想 2.优化 3.扩展 二.快速排序 1.基本思想 2.优化 3.代码 前言 查找和排序是数据结构与算法中不可或缺的一环,是前辈们在算法道路上留下的重要且方便的一些技巧,学习这些经典的查找和排序也能让我们更好和更快的解决问题.在这个专栏中我们会学习六大查找和十大排序的算法与思想,而本篇将详细讲解其中的交换排序——冒泡排序和快速排序: 注意:本文中所有排序按照升序排序,降序只需要把逻辑反过来即可! 一.冒泡排序 1.基本思想 对于很多同学来说冒泡排序是再熟悉不过

  • C语言常见排序算法之交换排序(冒泡排序,快速排序)

    目录 前言 1.交换排序——冒泡排序 1.1 算法思想 1.2 动图演示 1.3 冒泡最好的情况 2. 交换排序——快速排序 2.1 快速排序——挖坑法 快排的缺点 三数取中法 2.3 快速排序——左右指针法 2.4 前后指针法 前言 本期为大家带来的是常见排序算法中的交换排序,主要有冒泡排序,快速排序,快排分享了三种算法:挖坑法,左右指针法,前后指针法,以及两种优化方式:解决快排最坏情况的“三数取中”,避免递归次数过多的"小区间优化", 基本思想:所谓交换,就是根据序列中两个记录键值

  • C语言常见排序算法之插入排序(直接插入排序,希尔排序)

    目录 前言 一.直接插入排序 1.1 基本思想 1.2 算法思想 1.3 程序实现 1.4 直接插入排序的总结 二.希尔排序 2.1 算法思想 2.2 程序实现 2.3 希尔排序的特征总结 前言 本期为大家带来的是常见排序算法中的插入排序,主要有直接插入排序以及它的升级版——希尔排序,包您一看就会,快来试试吧~ 一.直接插入排序 1.1 基本思想 在生活当中,这种排序方式处处可见: 在玩扑克牌的时候我们就会采用插入排序的思想,当我们拿起第二张牌时,就会下意识的与第一张牌进行比较,如果比第一张牌小

  • C语言常见排序算法归并排序

    目录 前言 一.归并排序 1.1 基本思想 1.2 算法思想 1.3 程序设计思想 1.4 程序实现 1.5 归并排序的特性总结 前言 本期为大家带来的是常见排序算法中的归并排序,博主在这里先分享归并排序的递归算法,包您一看就会,快来试试吧~ 一.归并排序 1.1 基本思想 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法 (Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序 列:即先使每个子序列有序,再使

  • 必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

  • C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 代码实现 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具

  • Javascript中的常见排序算法

    具体代码及比较如下所示: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">  <html xmlns="http://www.w3.org/1999/xhtml" lang="gb2312">

  • C语言 奇偶排序算法详解及实例代码

    C语言奇偶排序算法 奇偶排序,或奇偶换位排序,或砖排序,是一种相对简单的排序算法,最初发明用于有本地互连的并行计算.这是与冒泡排序特点类似的一种比较排序.该算法中,通过比较数组中相邻的(奇-偶)位置数字对,如果该奇偶对是错误的顺序(第一个大于第二个),则交换.下一步重复该操作,但针对所有的(偶-奇)位置数字对.如此交替进行下去. 使用奇偶排序法对一列随机数字进行排序的过程 处理器数组的排序 在并行计算排序中,每个处理器对应处理一个值,并仅有与左右邻居的本地互连.所有处理器可同时与邻居进行比较.交

  • Python八大常见排序算法定义、实现及时间消耗效率分析

    本文实例讲述了Python八大常见排序算法定义.实现及时间消耗效率分析.分享给大家供大家参考,具体如下: 昨晚上开始总结了一下常见的几种排序算法,由于之前我已经写了好几篇排序的算法的相关博文了现在总结一下的话可以说是很方便的,这里的目的是为了更加完整详尽的总结一下这些排序算法,为了复习基础的东西,从冒泡排序.直接插入排序.选择排序.归并排序.希尔排序.桶排序.堆排序.快速排序入手来分析和实现,在最后也给出来了简单的时间统计,重在原理.算法基础,其他的次之,这些东西的熟练掌握不算是对之后的工作或者

  • Java实现常见排序算法的优化

    冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个元素已经是最大的了.即最后一个元素已经有序了. 优化一: 优化的思路就是每一次扫描遍历一次数组.如果某次的扫描之后没有发生数组元素的交换的话.那么说明数组的元素已经是有序的了, 就可以直接跳出循环.没有继续扫描的必要了. 优化二:如果数组的尾部已经局部有

随机推荐