c/c++基础简单易懂的快速排序算法

快速排序就是找一个基准，然后其左边要比他小，右边要比他大

int partition(int* a, int left, int right)
{
	int pivot = left;//找最开始位置为基准
	int index = left + 1;
	for (int i = index; i <= right; i++)
	{
		if (a[i] < a[pivot])
		{
			swap(a, i, index);
			index++;
		}
	}
	swap(a, pivot, index - 1);//index-1表示找到比a[pivot]要小的个数
	return index - 1;
}

然后通过递归的方法对基准左右两边都进行这样的排序 知道一个元素为止

void quick_sort(int* a, int left, int right)
{
	if (left < right)
	{
		int pivot = partition(a, left, right);
		quick_sort(a, left, pivot);//调用这个递归函数是将左边全部排好序
		quick_sort(a, pivot+1, right);//将右边排好
	}
}

以上就是c/c++基础简单易懂的快速排序算法的详细内容，更多关于c/c++快速排序的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • C语言编程入门必背的示例代码整理大全

    C语言编程入门必背的示例代码整理大全

    目录 一.C语言必背代码前言 二.一部分C语言必背代码 一.C语言必背代码前言 对于c语言来说,要记得东西其实不多,基本就是几个常用语句加一些关键字而已.你所看到的那些几千甚至上万行的代码,都是用这些语句和关键词来重复编写的.只是他们逻辑功能不一样,那如何快速的上手C语言代码,建议多看多写,下面是小编整理的C语言必背代码. 二.一部分C语言必背代码 1.输出9*9成法口诀,共9行9列,i控制行,j控制列. #include "stdio.h" main() {int i,j,resul

  • C/C++编程判断String字符串是否包含某个字符串实现示例

    目录 一.C语言风格 二.C++风格 一.C语言风格 在C语言中,字符串存储为字符数组,以'\0'结束. 在C的接口中,有strstr函数,可以在字符串中查找另一个字符串. char * strstr(const char *str1, const char *str2); 功能为在str1中查找str2,如果存在,那么返回查找到的起始指针,否则返回NULL. 参考代码: #include <iostream> #include <string> #include <cstr

  • C语言基础野指针与空指针示例分析

    目录 一:野指针 1.1 :野指针的成因 2.1 :规避野指针 1. 初始化指针 2. 避免指针越界 3 避免返回局部变量的地址 4. 开辟的指针释放后置为NULL 5. 养成良好的编程习惯 二:空指针 一:野指针 概念:野指针就是指向的内存地址是未知的(随机的,不正确的,没有明确限制的). 说明:指针变量也是变量,是变量就可以任意赋值.但是,任意数值赋值给指针变量没有意义,因为这样的指针就成了野指针,此指针指向的区域是未知(操作系统不允许操作此指针指向的内存区域). 注:野指针不会直接引发错误

  • C++数据结构链表基本操作示例过程

    目录 首先创建好一个节点 其次创建一个统计节点属性 增加节点 用表头插入的方法插入节点 删除节点 首先创建好一个节点 typedef struct node { int date; struct node* next; }*PNODE; PNODE creatnode(int date ) { PNODE newnode = (PNODE)malloc(sizeof(struct node)); assert(newnode); newnode->next = NULL; newnode->d

  • 深入浅析C语言与C++的区别与联系

    深入浅析C语言与C++的区别与联系

    目录 一.C语言是面向过程语言,而C++是面向对象语言 1.面向过程和面向对象的区别 2.面向过程和面向对象的优缺点 面向过程语言 面向对象语言 二.具体语言上的区别 1.关键字的不同 2.后缀名不同 3.返回值 4.参数列表 5.缺省参数 半缺省参数 全缺省参数 6.函数重载 7.const 总结 8.引用 9.malloc,free && new,delete 10.作用域 C语言虽说经常和C++在一起被大家提起,但可千万不要以为它们是一种编程语言.我们来介绍C语言和C++中的区别和联

  • C语言的空类型指针,空指针,野指针详解

    C语言的空类型指针,空指针,野指针详解

    目录 空类型指针-void* 空指针-NULL 野指针 造成野指针的原因 1.指针未初始化 2.指针越界访问 3.指针指向的空间已经释放 避免野指针 总结 空类型指针-void* void是空类型,void*是空类型指针,又叫万能指针,就是该指针能接收任意类型的指针,可以指向任何类型对象,所以不能对空类型指针进行解引用,必须强制类型转换成相应的指针类型,才能进行解引用操作. 空指针类型: 作为函数形参类型,可以接收任意类型的指针: 作为函数返回值类型,在函数外面,将其强制类型转换为相应的指针类型

  • c/c++基础简单易懂的快速排序算法

    快速排序就是找一个基准,然后其左边要比他小,右边要比他大 int partition(int* a, int left, int right) { int pivot = left;//找最开始位置为基准 int index = left + 1; for (int i = index; i <= right; i++) { if (a[i] < a[pivot]) { swap(a, i, index); index++; } } swap(a, pivot, index - 1);//in

  • PHP 快速排序算法详解

    PHP 快速排序算法详解

    概念 这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化.他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数组重复上面拆分,最后把小的数组元素和大的数组元素合并起来.这里用到了递归的思想. PHP实现 复制代码 代码如下: /*     快速排序 */ function quickSort($array) {    

  • Go语言展现快速排序算法全过程的思路及代码示例

    快速排序算法 快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序. 算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大.划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法. 选择最右边的数字作为基数.使用一个变量j记录当前左边数字(比基数小的数)的最右的下标值.然后使用变量i从左到右遍历数组,如果a[i]比基数小,说明a[i]

  • 深入解析快速排序算法的原理及其Go语言版实现

    深入解析快速排序算法的原理及其Go语言版实现

    快速排序是一种基于分治技术的重要排序算法.不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分.具体来说,它对给定数组中的元素进行重新排列,以得到一个快速排序的分区.在一个分区中,所有在s下标之前的元素都小于等于A[s],所有在s下标之后的元素都大于等于A[s]. 显然,建立了一个分区以后,A[s]已经位于它在有序数组中的最终位置,接下来我们可以继续对A[s]前和A[s]后的子数组分别进行排序(使用同样的方法). 为了排序一个数组A的全部元素,初始调用的是QUI

  • Java实现快速排序算法(Quicktsort)

    快速排序算法介绍快速排序和归并排序都使用分治法来设计算法,区别在于归并排序把数组分为两个基本等长的子数组,分别排好序之后还要进行归并(Merge)操作,而快速排序拆分子数组的时候显得更有艺术,取一个基准元素,拆分之后基准元素左边的元素都比基准元素小,右边的元素都不小于基准元素,这样只需要分别对两个子数组排序即可,不再像归并排序一样需要归并操作.基准元素的选取对算法的效率影响很大,最好的情况是两个子数组大小基本相当.为简单起见,我们选择最后一个元素,更高级的做法可以先找一个中位数并把中位数与最后一

  • 浅析java快速排序算法

    浅析java快速排序算法

    快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值,如此作为基准的元素调整到排序后的正确位置.递归快速排序,将其他n-1个元素也调整到排序后的正确位置.最后每个元素都是在排序后的正 确位置,排序完成.所以快速排序算法的核心算法是分区操作,即如何调整基准的位置以及调整返回基准的最终位置以便分治递归. 一趟快速排序的算法是: 1)设置两个变量i.j,排序开始的时候:i=0,j=N-1: 2)

  • C#快速排序算法实例分析

    本文实例讲述了C#快速排序算法.分享给大家供大家参考.具体实现方法如下: public static int[] QuickSort(int[] arr) { if (arr.Length <= 1) return arr; int pivot = arr.Length - 1; int[] less = GetLessThanEqualToPivot(arr, pivot); int[] greater = GetGreaterThanPivot(arr, pivot); return Con

  • 详解Java中使用泛型实现快速排序算法的方法

    快速排序算法概念 快速排序一般基于递归实现.其思路是这样的: 1.选定一个合适的值(理想情况中值最好,但实现中一般使用数组第一个值),称为"枢轴"(pivot). 2.基于这个值,将数组分为两部分,较小的分在左边,较大的分在右边. 3.可以肯定,如此一轮下来,这个枢轴的位置一定在最终位置上. 4.对两个子数组分别重复上述过程,直到每个数组只有一个元素. 5.排序完成. 基本实现方式: public static void quickSort(int[] arr){ qsort(arr,

  • Python实现的快速排序算法详解

    本文实例讲述了Python实现的快速排序算法.分享给大家供大家参考,具体如下: 快速排序基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 如序列[6,8,1,4,3,9],选择6作为基准数.从右向左扫描,寻找比基准数小的数字为3,交换6和3的位置,[3,8,1,4,6,9],接着从左向右扫描,寻找比基准数大的数字为8,交换6和8的位置

  • java实现快速排序算法

    java实现快速排序算法

    1.算法概念. 快速排序(Quicksort)是对冒泡排序的一种改进.由C. A. R. Hoare在1962年提出. 2.算法思想. 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3.实现思路. ①以第一个关键字 K 1 为控制字,将 [K 1 ,K 2 ,-,K n ] 分成两个子区,使左区所有关键字小于等于 K 1 ,右区所有关键字大于

随机推荐