首页 > 编程语言 >惊叹数据结构之美,品味排序算法之妙:对快排的详细介绍

惊叹数据结构之美,品味排序算法之妙:对快排的详细介绍

时间:2025-01-12 14:00:42浏览次数:3  
标签:ps arr right int 之美 快排 排序 数据结构 left

大家好,这里是小编的博客频道
小编的博客:就爱学编程

很高兴在CSDN这个大家庭与大家相识,希望能在这里与大家共同进步,共同收获更好的自己!!!

本文目录


在这里插入图片描述


那接下来就让我们开始遨游在知识的海洋!

正文


快速排序是一种非常高效的排序算法,其基本思想是通过一个划分操作将待排序的数组分为两个子数组,左边子数组的元素都比右边子数组的元素小,然后递归地对这两个子数组进行排序。下面是快速排序的多种版本及其实现原理和优化方法的详细介绍。

1. 基本快速排序

原理

  • 选择基准:从数组中选择一个元素作为基准(pivot)。
  • 分区操作:将数组分为两部分,左边部分的所有元素都小于基准,右边部分的所有元素都大于基准。
  • 递归排序:对左右两个子数组递归地进行快速排序。

三种版本:

霍尔法(Hoare法)

霍尔法是以快速排序的创始人霍尔命名的,也是快速排序最初的实现版本。其基本思想是用两个指针分别指向待排序数组的开头和结尾,然后让这两个指针相向而行,根据与key值的大小关系进行移动和交换,直到两者相遇。具体步骤如下:

任取一个待排序数组中的数作为key值(可以取头值、尾值或中间值等)。

如果取头值作为key值,则让右指针先移动;如果取尾值作为key值,则让左指针先移动。“移动”的过程是:

right指针直到找到小于key的值才停下来,left指针直到找到大于key的值才停下来。

将left和right所对应的值进行交换。

重复上述过程,直到left和right相遇。此时,将key值和right所指向的值进行交换,right最后指向的位置就是key值应该所在的位置。

以right为界,将数组一分为二,递归地对左右两部分进行排序。

代码实现:

//快速排序-----霍尔
void QuickSort1(int* a, int left, int right) {
	if (left >= right) return;
	int end = right, begin = left, keyi = left;
	while (left < right) {
		//右指针找小
		while (left < right && a[right] >= a[keyi]) {
			--right;
		}
		
		//左指针找大
		while (left < right && a[left] <= a[keyi]) {
			++left;
		}

		Swap(&a[right], &a[left]);
	}
	//最后对调将目标值放到合适的位置
	Swap(&a[keyi], &a[left]);
	keyi = left;

	QuickSort1(a, begin, keyi - 1);
	QuickSort1(a, keyi + 1, end);
}

霍尔法的优势在于其高效性,但理解起来可能相对复杂一些。


挖坑法

挖坑法是快速排序的一种实现方式,其思路与霍尔法类似,但更容易理解。具体步骤如下:

选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑。
定义left和right两个指针,分别从数组的左右两端开始相向而行。
right指针向左移动,直到找到比key小的数;然后将该数填入坑中,并将hole更新为当前right的位置。
left指针向右移动,直到找到比key大的数;然后将该数填入当前的hole中,并再次更新hole为当前left的位置。
重复上述步骤,直到left和right相遇。此时,将key值填入最后的hole中。
以hole为界,将数组一分为二,递归地对左右两部分进行排序。

代码实现:

//快速排序-----挖坑
void QuickSort2(int* a, int left, int right) {
	if (left >= right) return;
	int end = right, begin = left;
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = a[left], hole = left;
	while (left < right) {
		//右指针找小
		while (left < right && a[right] >= key) {
			--right;
		}
		a[hole] = a[right];
		hole = right;

		//左指针找大
		while (left < right && a[left] <= key) {
			++left;
		}
		a[hole] = a[left];
		hole = left;

	}
	a[hole] = key;

	QuickSort2(a, begin, hole - 1);
	QuickSort2(a, hole + 1, end);
}

挖坑法的优势在于其直观易懂,便于理解和实现。


快慢指针法

这种方法使用两个指针从数组的两端向中间移动,直到它们相遇或交错。

代码实现:

//快速排序-----快慢指针
void QuickSort3(int* a, int left, int right) {
	if (left >= right) return;
	int keyi = left;
	int prev = left, cur = left + 1;
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);
	while (cur <= right){
		if (a[cur] < a[keyi]) {
			Swap(&a[cur], &a[++prev]);
		}
		cur++;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	QuickSort3(a, left, keyi - 1);
	QuickSort3(a, keyi + 1, right);
}

2. 随机化快速排序

原理

  • 随机选择基准:在每次划分之前,随机选择一个元素作为基准,以减少最坏情况的发生概率。
  • 分区操作:与基本快速排序相同。
  • 递归排序:对左右两个子数组递归地进行快速排序。

代码示例

#include <stdlib.h>

int randomPartition(int arr[], int low, int high) {
    int random = low + rand() % (high - low + 1);
    swap(&arr[random], &arr[high]);
    return partition(arr, low, high);
}

void randomizedQuickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = randomPartition(arr, low, high);

        randomizedQuickSort(arr, low, pi - 1);
        randomizedQuickSort(arr, pi + 1, high);
    }
}

3. 三向切分快速排序

原理

  • 选择基准:选择一个元素作为基准。
  • 三向分区:将数组分为三部分:
  • 左边部分的所有元素都小于基准。
  • 中间部分的所有元素都等于基准。
  • 右边部分的所有元素都大于基准。
  • 递归排序:只对左右两个子数组递归地进行快速排序,中间部分已经有序。

代码示例

void threeWayQuickSort(int arr[], int low, int high) {
    if (high <= low) return;

    int lt = low, gt = high;
    int pivot = arr[low];
    int i = low + 1;

    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(&arr[lt++], &arr[i++]);
        } else if (arr[i] > pivot) {
            swap(&arr[i], &arr[gt--]);
        } else {
            i++;
        }
    }

    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

4. 插入排序优化

原理

  • 选择基准:选择一个元素作为基准。
  • 分区操作:将数组分为两部分。
  • 递归排序:当子数组的大小小于某个阈值时,使用插入排序而不是快速排序,以减少递归调用的开销。

代码示例

void hybridQuickSort(int arr[], int low, int high, int threshold) {
    while (low < high) {
        if (high - low < threshold) {
            insertionSort(arr, low, high);
            break;
        } else {
            int pi = partition(arr, low, high);

            hybridQuickSort(arr, low, pi - 1, threshold);
            low = pi + 1;
        }
    }
}

void insertionSort(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
 

6.非递归优化

因为递归算法都存在一个无法避免的问题——递归深度太大会导致栈溢出的问题,所以我们应该掌握非递归实现各种递归算法的技能。

  • 递归算法改非递归一般有两种思路:(1)直接改循环;(2)借用数据结构其中栈是最为常用的
  • 对于快速排序,使用栈是最好模拟的方式。

代码实现:

(1)ST.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

#define MAXCAPACITY 4

typedef int Datastyle;

typedef struct stack {
	Datastyle* a;               //指向有效数据的指针 
	int top;
	//给top初始化一般要么给-1,要么给0,如果给1及以上就会造成空间的浪费,给-2及以下也会造成空间的浪费(除非进行特殊的处理,分情况给top加值)
	//如果top初始化给的是-1,则top代表的是栈顶元素所在位置的下标;如果top初始化给的是0,则top代表的是栈顶元素所在位置的下一个位置的下标
	//这是因为(以插入为例)每一次入栈后,top必定加1-----而top初始化给-1元素入栈就是top先++再赋值;而top初始化给0元素入栈就是top先赋值再++
	//但无论哪种入栈方式,最终的结果都是top++。至于为什么两种不同的给top赋初值对应不同的入栈方式也是取决于数组的下标从0开始的特点
	//本次我们就展示top初始化为0的栈的写法
	int capacity;
}ST;

//初始化栈
void STInit(ST* ps);

//销毁栈
void  STDestory(ST* ps);

//插入数据(从栈顶)----(入栈,压栈)
void STPush(ST* ps, Datastyle x);

//删除数据(从栈顶)----(出栈)
void STPop(ST* ps);

//访问栈顶元素
Datastyle STTop(ST* ps);

//得出栈的元素个数
int STSize(ST* ps);

//判空
bool STEmpty(ST* ps);

ST.c

#include"ST.h"

//初始化栈
void STInit(ST* ps) {
	assert(ps);
	Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
	if (temp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = MAXCAPACITY;
	ps->top = 0;
}

//销毁栈
void  STDestory(ST* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//插入数据(从栈顶)----(入栈,压栈)
void STPush(ST* ps, Datastyle x) {
	assert(ps);
	//判断是否满了
	if (ps->top == ps->capacity) {
		Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle));				//扩容为当前容量的两倍比较合理
		if (temp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = temp;
	}
	ps->a[ps->top++] = x;
}

//判空
bool STEmpty(ST* ps) {
	return (ps->top == 0);
}

//删除数据(从栈顶)----(出栈)
void STPop(ST* ps) {
	assert(ps && !STEmpty(ps));
	--ps->top;
}

//访问栈顶元素
Datastyle STTop(ST* ps) {
	return ps->a[ps->top - 1];
}

//得出栈的元素个数
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}



Sort.c

#include"ST.h"
//快速排序-----非递归实现------入栈元素:每次递归会发生改变的参数
void QuickSortNonR(int* a, int left, int right) {
	//Chaucer创建栈
	ST st;

	//初始化栈
	STInit(&st);

	//先入栈
	STPush(&st, right);
	STPush(&st, left);

	while (!STEmpty(&st)){
		//因为栈先入后出的特点,所以我们先入右再入左
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		//进行单趟排序并返回keyi
		int keyi = SingalQuickSort(a, begin, end);
		//[begin,keyi - 1] keyi [keyi + 1, end] 
		
		//因为栈先入后出的特点,所以我们先入右再入左,不过当区间内仅剩一个元素或没有元素的时候,我们也不应该入栈
		if (keyi + 1 < end) {
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi - 1) {
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	//销毁栈
	STDestory(&st);
}


总结

  • 快速排序的多种版本和优化方法可以显著提高其在不同场景下的性能。选择合适的版本和优化方法,可以根据具体的数据特性和应用场景,进一步提升排序算法的效率和稳定性。希望这些介绍能帮助你更好地理解和应用快速排序算法。

快乐的时光总是短暂,咱们下篇博文再见啦!!!不要忘了,给小编点点赞和收藏支持一下,在此非常感谢!!!

标签:ps,arr,right,int,之美,快排,排序,数据结构,left
From: https://blog.csdn.net/z15879084549/article/details/145091907

相关文章

  • 数据结构与算法之二叉树: LeetCode 108. 将有序数组转换为二叉搜索树 (Ts版)
    将有序数组转换为二叉搜索树https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/描述给你一个整数数组nums,其中元素已经按升序排列请你将其转换为一棵平衡二叉搜索树示例1输入:nums=[-10,-3,0,5,9]输出:[0,-3,9,-10,nul......
  • 数据结构与算法之二叉树: LeetCode 110. 平衡二叉树 (Ts版)
    平衡二叉树https://leetcode.cn/problems/balanced-binary-tree/description/描述给定一个二叉树,判断它是否是平衡二叉树示例1输入:root=[3,9,20,null,null,15,7]输出:true示例2输入:root=[1,2,2,3,3,null,null,4,4]输出:false示例3输入:root=[]输......
  • 数据结构与算法之二叉树: LeetCode 117. 填充每个节点的下一个右侧节点指针 II (Ts版)
    填充每个节点的下一个右侧节点指针IIhttps://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/描述给定一个二叉树:structNode{intval;Node*left;Node*right;Node*next;}填充它的每个next指针,让这个指针指向其......
  • 数据结构C语言描述11(图文结合)--二叉搜索树(BST树)的实现(数据采用KV存储形式进行封
    前言这个专栏将会用纯C实现常用的数据结构和简单的算法;有C基础即可跟着学习,代码均可运行;准备考研的也可跟着写,个人感觉,如果时间充裕,手写一遍比看书、刷题管用很多,这也是本人采用纯C语言实现的原因之一;欢迎收藏+关注,本人将会持续更新。文章目录什么是二叉搜索树代码实......
  • 时间复杂度和空间复杂度(全解)——数据结构
    目录1--时间复杂度和空间复杂度计算1.什么是时间复杂度和空间复杂度?1.1算法效率1.2时间复杂度的概念1.3空间复杂度的概念1.4复杂度计算在算法的意义2.1如何计算常见算法的时间复杂度?2.2大O的渐进表示法推导大O阶方法:2.3常见时间复杂度计算举例实例1:实例2:实例......
  • [数据结构学习笔记11] 前序树(Trie/Prefix tree)
    前序树(Trie/Prefixtree),它的一个典型的应用场景在搜索引擎里,当你输入查询关键字的时候,会联想自动补齐你想要输入的内容。比如,你输入app,下面可能会出来联想Apple,Applied等等。什么是Trie?Trie(读作Try)是这样一个数据结构,它把短语或者单词分解字母,然后以一种方式去存储,让添加、删......
  • 数据结构:栈(Stack)和队列(Queue)
    目录......
  • [微服务]redis数据结构
    介绍我们常用的Redis数据类型有5种,分别是:StringListSetSortedSetHash还有一些高级数据类型,比如Bitmap、HyperLogLog、GEO等,其底层都是基于上述5种基本数据类型。因此在Redis的源码中,其实只有5种数据类型。RedisObject不管是任何一种数据类型,最终都会封装为RedisObject格式......
  • 124.【C语言】数据结构之快速排序的小区间优化和非递归的解决方法
    目录1.小区间优化测试代码运行结果2.非递归的解决方法(重要!)递归产生的问题一般来说,递归改非递归有两种方法算法分析递归产生的二叉树栈的示意图先写代码框架再填写细节部分1.小区间优化回顾121.【C语言】数据结构之快速排序(未优化的Hoare排序存在的问题)以及......
  • 冒险数据结构:峰谷序列(动态序列查找问题)
    先考虑这么一个问题:    如何求出一个序列在所有位置上的各个元素的前面和后面第一个比它小的元素位置。显然这个问题可以用单调栈来解决。        如上图所示,维护一个单调递增的序列,每当栈顶>当前元素时,就抛出栈顶,这时就找到了栈顶元素后面第一个小于它的......