C语言之快速排序算法(递归Hoare版)介绍
废话不多说，先看代码
#define _CRT_SECURE_NO_WARNINGS 1
//快速排序算法，递归求解
#include <stdio.h>
void swap(int* a, int* b)
{
int c = 0;
c = *a;
*a = *b;
*b = c;
}
void Compare(int arr[], int one, int end)
{
int first = one;//最左边数组下标
int last = end;//最右边数组下标
int key = first;//用于比较的标量（选取最左边第一个元素）
if (first >= last)
{
return;
}
while (first < last)
{
while (first < last && arr[last] >= arr[key])//右边找比标量小的数
{
last--;
}
while (first < last && arr[first] <= arr[key])//左边找比标量大的数
{
first++;
}
if(first < last)//分析交换找出来的值
swap(&arr[first], &arr[last]);
}
if (first == last)
{
int mite = key;//交换标量到它应该到的位置上，重新选取标量
swap(&arr[mite], &arr[last]);
}
Compare(arr,one,first-1);//左边递归排序
Compare(arr,first+1,end);//右边递归排序
}
int main()
{
int arr[] = { 5,4,6,5,2,1};
int i = 0;
int len = sizeof(arr) / 4;
Compare(arr,i,len-1);//传第一个和最后一个元素的下标
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
首先什么是快速排序算法：快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序n 个项目要Ο(nlogn) 次比较。在最坏状况下则需要Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。
快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）
简单的说，选取一个基准（这里选取第一个数据），与其他数据进行比较，使比它小的在它的前面，比它大的在它的后面。然后再以这个基准为界限分为两部地方（比它大的部分、比它小的部分），分别选取两个部分的基准，再进行比较，比较完后在进行分界，重复下去，直到最后每部分都只有一个数据时，排序结束。
图解-->
代码讲解：<运用递归>
1、首先需要创建数组、数组第一个数据下标，最后一个数据下标三个参数，数组用于储存数据，然后创建一个Compare()用于快速排序函数，最后打印出来就是我们需要的有序数列。
int main()
{
int arr[] = { 5,4,6,5,2,1};
int i = 0;
int len = sizeof(arr) / 4;
Compare(arr,i,len-1);//传第一个和最后一个元素的下标
for (i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
return 0;
2、Compare()函数创建
这里使用无符号返回类型，因为不需要返回值
为保证数组第一个元素和最后一个元素下标不变，创建first和last两个局部变量记录数组第一个元素和最后一个元素的下标
创建key下标的数据作为基准
void Compare(int arr[], int one, int end)
{
int first = one;//最左边数组下标
int last = end;//最右边数组下标
int key = first;//用于比较的标量（选取最左边第一个元素）
3、首先判断数列是否只有一个元素，如果只有一个元素，则函数结束。
4、开始实现函数主要比较部分
4.1、如果选取左边第一个数据为基准，先从右边开始比较，
4.2、从右边第一个数据开始与key进行比较，如果比它大则继续向右比较(last--)，直到找到比key小的数据，便停下来。
4.3、此刻开始从左边开始与key比较，如果比key小则继续比较(first++)，如果比key大则与右边找到的比key大的数进行交换。然后右边继续找，重复以上步骤。
4.4、直到first>=last时，都停止寻找，并交换此时first下标的数据与key的值
4.5、分治思想，以此时的key下标的数组作为分界，分为比它大的、比它小的两部分，在重复以上步骤，直至只有一个数据为止，停下排序。采用递归求解。
void Compare(int arr[], int one, int end)
{
int first = one;//最左边数组下标
int last = end;//最右边数组下标
int key = first;//用于比较的标量（选取最左边第一个元素）
if (first >= last)
{
return;
}
while (first < last)
{
while (first < last && arr[last] >= arr[key])//右边找比标量小的数
{
last--;
}
while (first < last && arr[first] <= arr[key])//左边找比标量大的数
{
first++;
}
if(first < last)//分析交换找出来的值
swap(&arr[first], &arr[last]);
}
if (first == last)
{
int mite = key;//交换标量到它应该到的位置上，重新选取标量
swap(&arr[mite], &arr[last]);
}
Compare(arr,one,first-1);//左边递归排序
Compare(arr,first+1,end);//右边递归排序
}
swap()交换函数，因为需要影响到交换函数外的值，使用指针形参。
void swap(int* a, int* b)
{
int c = 0;
c = *a;
*a = *b;
*b = c;
}
到此这篇关于C语言之快速排序算法（递归Hoare版）介绍的文章就介绍到这了,更多相关C语言快速排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C语言 八大排序算法的过程图解及实现代码
目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关
-
C语言实现单链表的快速排序算法
目录 背景 设计思路 算法主要步骤 快速排序算法实现 整个程序源代码 测试案例 总结 背景 传统QuickSort算法最大不足之处在于,由于其基于可索引存储结构设计(一般为数组或索引表),因而无法用于链式存储结构,而链式存储结构的实际应用非常广泛,例如动态存储管理.动态优先级调度等等,故本文针对于单向链表,以QuickSort的分治策略为基础,提出一种可用于单向链表的快速排序算法. 设计思路 将单向链表的首节点作为枢轴节点,然后从单向链表首部的第二个节点开始,逐一遍历所有后续节点,并将这些已遍历
-
C语言直接插入排序算法
目录 1.算法模板 2.算法介绍 3.实例 总结 1.算法模板 void InsertSort(SqList *L) { int j; for (int i = 2; i <= L->length; i ++ ) { if (L->arr[i] < L->arr[i-1]) { L->arr[0] = L->arr[i]; // 设置哨兵 for (j = i - 1; L->arr[j] > L->arr[0]; j -- ) L->ar
-
C语言数据结构经典10大排序算法刨析
1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp
-
C语言中冒泡排序算法详解
目录 一.算法描述 二.算法分析 三.完整代码 总结 一.算法描述 比较相邻两个元素,如果第一个比第二个大则交换两个值.遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面.假设数组有 n 个元素,那么需要遍历 n - 1 次,因为剩下的一个元素一定是最小的,无需再遍历一次.因此需要两层循环,第一层是遍历次数,第二层是遍历未排序数组. 动图如下: 黄色部分表示已排好序的数组,蓝色部分表示未排序数组 核心代码如下: /** * @brief 冒泡排序 * * @param arr 待排序的数
-
C语言直接插入排序算法介绍
目录 前言 一.什么是直接插入排序 二.代码讲解 总结 前言 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i =
-
C语言冒泡排序算法代码详解
今天我们来用C语言实现一下冒泡排序 首先我们来了解一下什么叫做冒泡排序,冒泡顾名思义把质量轻的气体(如二氧化碳一样)浮到水面上(如可乐中的二氧化碳),因此冒泡排序的原理就是N个元素在一个周期中,微观上依次进行两两元素的比较,小的元素就被放在前面,大的元素放在后面,以此来进行N-1个周期,来完成冒泡排序. 上文中的一个周期,即外循环,依次进行比较,即内循环. 文字看着很迷糊?没事儿,上图 如图所示,两两元素依次进行比较,小的元素往前移动,大的元素往后移动,直至元素顺序是升序的形式,即移动了 元素-
-
C语言实现各种排序算法实例代码(选择,冒泡,插入,归并,希尔,快排,堆排序,计数)
目录 前言 选择排序 冒泡排序 插入排序 归并排序 希尔排序 快速排序 堆排序 计数排序 总结 前言 平时用惯了高级语言高级工具高级算法,难免对一些基础算法感到生疏.但最基础的排序算法中实则蕴含着相当丰富的优化思维,熟练运用可起到举一反三之功效. 选择排序 选择排序几乎是最无脑的一种排序算法,通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位:再从数组中剩下的数里选出最大(小)的,放到第二位,依次类推. 算法步骤 设数组有n个元素,{ a 0 , a 1 , - , a n } 从数组第
-
C语言之直接插入排序算法的方法
目录 一.什么是直接插入排序 二.代码讲解 总结 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i = 0; i
-
C语言之快速排序算法(递归Hoare版)介绍
废话不多说,先看代码 #define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标 int key =
-
C语言实现快速排序算法实例
首先我们要对一组数据进行排序: 在数组中选一个基准数(通常为数组第一个,黄圈圈标记了): 将数组中小于基准数的数据移到基准数左边,大于基准数的移到右边,怎么移动,后面说: 对于基准数左.右两边的数组,不断重复以上两个过程,直到每个子集只有一个元素,即为全部有序. 好了,咱们开始吧! 快速排序需要两个哨兵,i 和 j,分别指向数组的头和尾.接下来就要进行移动. 我们通常选择第一个元素作为基准数,去移动数组元素,使其达到这个基准数的左边都是小于它的,右边都是大于它的.开始移动 i 和 j , i 和
-
C语言之快速排序算法（递归Hoare版）介绍
废话不多说,先看代码 #define _CRT_SECURE_NO_WARNINGS 1 //快速排序算法,递归求解 #include <stdio.h> void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int arr[], int one, int end) { int first = one;//最左边数组下标 int last = end;//最右边数组下标 int key =
-
C语言实现快速排序算法
一.快速排序算法(Quicksort) 1. 定义 快速排序由C. A. R. Hoare在1962年提出.快速排序是对冒泡排序的一种改进,采用了一种分治的策略. 2. 基本思想 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 3. 步骤 a. 先从数列中取出一个数作为基准数. b. 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全
-
Go语言展现快速排序算法全过程的思路及代码示例
快速排序算法 快速排序是一个递归的思想,首先选择一个数作为基数,把数组中小于它的数放在它的左边,把大于它的数放在它的右边,然后对左右两边的数递归进行排序. 算法的关键部分是实现数组的划分,即怎么把数组的元素划分成两部分,使得左边的数比基数小,右边的数比基数大.划分有许多不同的实现方法,这里主要使用单向扫描的方法,后面再稍微介绍双向扫描的方法. 选择最右边的数字作为基数.使用一个变量j记录当前左边数字(比基数小的数)的最右的下标值.然后使用变量i从左到右遍历数组,如果a[i]比基数小,说明a[i]
-
逐步讲解快速排序算法及C#版的实现示例
算法思想 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序.它采用了一种分治的策略,通常称其为分治法(Divide-and-ConquerMethod). 该方法的基本思想是: 1．先从数列中取出一个数作为基准数. 2．分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边. 3．再对左右区间重复第二步,直到各区间只有一个数. 虽然快速排序称为分治法,但分治法这三个字显然无法很好的概括快速排序的全部步骤.因此我的对快速排序作了进一步的说明:挖坑填数+分治法:
-
C语言中使用快速排序算法对元素排序的实例详解
调用C语言的快速排序算法qsort(); #include<stdio.h> #include<stdlib.h> #include<string.h> #define SIZE 100 //从小到大排序 int comp1(const void *x,const void *y) { return *(int *)x - *(int *)y; } //从大到小排序 int comp2(const void *x,const void *y) { return *(in
-
Java实现快速排序算法的完整示例
首先,来看一下,快速排序的实现的动态图: 快速排序介绍: 快速排序,根据教科书说法来看,是冒泡排序的一种改进. 快速排序,由一个待排序的数组(array),以及找准三个变量: 中枢值(pivot) 左值(left) 右值(right) 根据中枢值(pivot)来做调整,将数组(array)分为三个部分: 第一部分:中枢值(pivot),单独数字构成,这个值在每次排序好的"最中间": 第二部分:左边数组(由array的一部分组成),这个数组在第一部分 中枢值(pivot) 的"
-
Python语言实现SIFT算法
目录 一.什么是SIFT算法 二.准备工作 2.1 实验设备 2.2 OpenCV安装 三.实验工作 3.1 图像选择 3.2 程序实现 3.3 程序结果 本文侧重于如何使用Python语言实现SIFT算法 所有程序已打包:基于OpenCV-Python的SIFT算法的实现 一.什么是SIFT算法 SIFT,即尺度不变特征变换(Scale-invariant feature transform,SIFT),是用于图像处理领域的一种描述.这种描述具有尺度不变性,可在图像中检测出关键点,是一种局