【自顶向下模块化编程】C语言实现多级反馈队列调度算法

article/2025/9/16 2:18:18

自顶向下-多级反馈队列

  • 多级反馈队列算法
    • 算法原理
    • 算法描述
    • 题目摘要
  • 自顶向下模块化设计
    • 整体框架
    • 具体实现
      • Generator
      • Scheduler
      • Executor
    • 整体代码实现
  • 总结及心得
    • 总结
    • 心得

多级反馈队列算法

多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。

算法原理

  1. 设有N个队列（Q1,Q2…QN），其中各个队列对于处理机的优先级不一样，即位于各个队列中的作业(进程)的优先级不一样。一般来说，优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高，依次类推其它的队列。
  2. 对于优先级最低的队列来说，里面是遵循时间片轮转法。位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。
  3. 各个队列的时间片不一样，它们的时间片随着优先级的增加而减少，优先级越高的队列中的时间片越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大。

算法描述

  1. 进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
  2. 首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，当且仅当在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
  3. 对于同一个队列中的各个进程，按照FCFS分配时间片调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列末尾，直至完成。
  4. 在最后一个队列QN中的各个进程，按照时间片轮转分配时间片调度。
  5. 在低优先级的队列中的进程在运行时，又有新到达的作业，此时须立即把正在运行的进程放回当前队列的队尾，然后把处理机分给高优先级进程。换而言之，任何时刻，只有当第1~i-1队列全部为空时，才会去执行第i队列的进程（抢占式）。

特别说明，当再度运行到当前队列的该进程时，仅分配上次还未完成的时间片，不再分配该队列对应的完整时间片。

题目摘要

  1. 假设有 5 个运行队列，它们的优先级分别为 1，2，3，4，5，它们的时间片长度分别为10ms,20ms,40ms,80ms,160ms，即第 i 个队列的优先级比第 i-1 个队列要低一级，但是时间片比第 i-1 个队列的要长一倍。
  2. 多级反馈队列调度算法包括四个部分：主程序main，进程产生器 generator，进程调度器函数 scheduler，进程运行器函数 executor。
  3. 结果输出：在进程创建、插入队列、执行时的相关信息，并计算输出总的平均等待时间。

补充说明：

  • 其中，Generator 用线程来实现，每隔一个随机时间(例如在[1,100]ms 之间)产生一个新的进程 PCB，并插入到第 1 个队列的进程链表尾部。
  • Scheduler 依次探测每个队列，寻找进程链表不为空的队列，然后调用 Executor, executor 把该队列进程链表首部的进程取出来执行。
  • 要设置 1 个互斥信号量来实现对第 1 个队列的互斥访问，因为generator 和 executor 有可能同时对第 1 个队列进行操作。
  • 同时要设置 1 个同步信号量，用于 generator 和scheduler 的同步：generator 每产生 1 个新进程，就 signal 一次这个同步信号量；只有所有队列不为空时，scheduler 才会运行，否则 scheduler要等待这个同步信号量。
  • 当所有进程运行完毕后，scheduler 退出，主程序结束。

自顶向下模块化设计

所谓的自顶向下的编程方法，本质上就是编写程序的视角从整体的宏观性逐层进入具体的微观性的一种编程思想。
我们编写程序时一开始不用思考得事无巨细，把所有细节都想清楚；也不要面条式的想到哪里写到哪里。
而应该是自顶向下的，从一个大的粗的核心的任务开始，逐级细分，最后再完成最底层的具体实现。

整体框架

根据题意，算法在整体上分为了四个部分：main、generator、scheduler、executor

  • main函数主要负责创建线程用以调度generator、scheduler函数，以及其他的一些次要工作（例如创建信号量、关闭线程等等）。
  • generator函数主要负责模拟进程的产生以及信号量的同步，模拟进程产生之后会被放置在多级队列中的第一队列队尾，并且分别释放两个信号量传递给scheduler和executor。前者用以激活调度（第一次激活后不一定再用到），后者用以解锁对第一队列中“进程”的使用权（generator和executor在第一队列互斥）。
  • scheduler函数主要负责调度executor函数来执行线程，在得到了来自generator的信号量之后，其会进入对多级队列的扫描循环，直到队列内为空（若进程没有执行完，则继续等待同步的信号量到来）或所有进程执行完毕。每次从上到下扫描到队列中的进程时，将其传入executor进行执行，同时再从头开始扫描（实现“优先级”），以此往复。
  • executor函数主要负责执行模拟进程，即对进程信息进行某种操作，执行完之后scheduler会根据进程的信息对进程进行转移或者删除操作。特别的executor在执行第一队列的模拟进程时，需要等待来自generator的信号量，同时和generator进行互斥访问，以防止冲突发生。

具体实现

根据上述整体框架的分析，我们可以对三大函数（main结构简单就不需要再拆解了）进行任务拆解。
通过任务拆解得到其中的细分函数（子函数），然后用它们拼出最终的“大函数”。

Generator

结合题意，通过在整体框架中的分析可以得到generator及其所需子函数：

  1. 创建模拟进程：init_PCB
  2. 插入（第一）队列：insert_queue
  3. 输出若干信息：print_…
DWORD WINAPI generator(LPVOID q_);   //generator和它的子函数，以此类推
PCB* init_PCB(int pid, int time);    //初始化PCB
void insert_queue(queue* q, PCB* pcb);  //插入队列
void print_generated(PCB* pcb);  //输出生成进程信息
void print_sleep(int sleep);    //输出休眠信息

// generator整体实现
DWORD WINAPI generator(LPVOID q_) {srand((unsigned)time(NULL));	//随机数种子queue* q = (queue*)q_;int count_process = 0;  //记录已生成的进程数int sleep = 0;  //记录休眠时间int count_sleep = 0;    //记录总计休眠时间while (count_process < num_Process) {PCB* pcb = init_PCB(count_process, count_sleep); //填入pid和到达时间（不觉得很怪吗）print_generated(pcb);sleep = 1 + rand() % 100;count_sleep += sleep;print_sleep(sleep);EnterCriticalSection(&cs);insert_queue(q, pcb);   //插入第一队列的队尾LeaveCriticalSection(&cs);ReleaseSemaphore(Sema[0], 1, NULL); //同步scheduler进行调度第一队列ReleaseSemaphore(Sema[1], 1, NULL); //唤醒访问第一队列的executorcount_process++;Sleep(sleep);    //隔一个随机的时间段}return 0;
}

Scheduler

结合题意，通过在整体框架中的分析可以得到scheduler及其所需子函数：

  1. 查看当前多级队列是否为空：isEmpty
  2. 对进程进行队列间转移：transfer
  3. 对已完成进程进行删除操作：delete_（关键字冲突）
  4. 输出若干信息：print_…
DWORD WINAPI scheduler(LPVOID q_);
bool isEmpty(queue q[]);    //查看队列是否为空
void transfer(queue* q, queue* q_);   //队列间转移
void delete_(queue* q);  //执行完的进程踢出队列并删除
void print_transfer(queue q);  //输出转移插入信息
void print_finish(queue q); //输出完成信息

// scheduler整体实现
DWORD WINAPI scheduler(LPVOID q_) {queue* q = (queue*)q_;int count_finish = 0;while (count_finish < num_Process) {    //当完成数没达到总线程数时进行循环WaitForSingleObject(Sema[0], INFINITE); //当多级队列为空、以及开始时等待同步信号量do {    //当不为空时进入调度for (int i = 0; i < num_Queue; i++) {if (q[i].list != NULL) {executor(&q[i], q);if (q[i].list->neededTime > q[i].list->usedTime) {if (i < (num_Queue - 1)) {EnterCriticalSection(&cs);transfer(&q[i], &q[i + 1]);print_transfer(q[i + 1]);LeaveCriticalSection(&cs);}}else {print_finish(q[i]);delete_(&q[i]);count_finish++;}break;  //执行完一次后重新从一级队列开始扫描}}} while (!isEmpty(q));}print_average_WaitTime(WaitTime);return 0;
}

Executor

结合题意，通过在整体框架中的分析可以得到executor及其所需子函数：
（executor实现功能相对简单，故可分解部分较少）

  1. 执行某一进程后，让所有在队列中的模拟进程增加等待时间：add_WaitTime
  2. 输出若干信息：print_…
void executor(queue* q_,queue q[]);
void add_WaitTime(queue* q_, queue q[]); //增加等待时间
void print_executed(queue* q);   //输出执行信息

// executor整体实现
void executor(queue* q_, queue q[]) {if (q_->priority == 1) { //如果执行的队列是第一队列，则要等待生成器的信号，并且进入临界区执行WaitForSingleObject(Sema[1], INFINITE);     //出现谜之问题EnterCriticalSection(&cs);Sleep(q_->timeSlice);q_->list->usedTime += q_->timeSlice;add_WaitTime(q_, q);print_executed(q_);LeaveCriticalSection(&cs);}else {Sleep(q_->timeSlice);q_->list->usedTime += q_->timeSlice;add_WaitTime(q_, q);print_executed(q_);}return;
}

整体代码实现

理清上述三个主要函数的结构后，再对一些细节部分进行补充，整个算法的实现也就呼之欲出了。

// 多级反馈队列调度算法代码实现
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <Windows.h>
#include <stdlib.h>#define num_Process 10	//定义必要的常量方便后面使用
#define num_Queue 5
#define maxWaitTime 100
#define minTimeSlice 10
#define neededTimeLB 2
#define neededTimeUB 200CRITICAL_SECTION cs;    //创建临界区
HANDLE Sema[2];     //一个用于generator和executor互斥访问第一个运行队列，另一个用于generator和scheduler同步
int WaitTime = 0;   //累计每个进程的等待时间typedef struct PCB {int pid;       //进程标识符，即进程的名字，改成int类型方便赋值//以下部分为用于进程调度的信息char state;         //‘r’: 运行状态；‘w’:就绪状态；‘b’:阻塞状态int priority;       //进程优先级int arrivalTime;    //进程的创建时间(到达时间)int neededTime;     //进程需要的运行时间int usedTime;       //进程已累计运行的时间int totalWaitTime;  //进程已等待的CPU时间总和//以下部分为进程的控制信息struct PCB* next;   //指向下一个PCB的链表指针
}PCB;typedef struct queue {int priority;    //该队列的优先级int timeSlice;   //该队列的时间片长度struct PCB* list;   //指向该队列中进程PCB链表的头部 
}queue;void init_queues(queue q[]);   //初始化队列DWORD WINAPI generator(LPVOID q_);   //generator和它的子函数，以此类推
PCB* init_PCB(int pid, int time);    //初始化PCB
void insert_queue(queue* q, PCB* pcb);  //插入队列
void print_generated(PCB* pcb);  //输出生成进程信息
void print_sleep(int sleep);    //输出休眠信息DWORD WINAPI scheduler(LPVOID q_);
bool isEmpty(queue q[]);    //查看队列是否为空
void transfer(queue* q, queue* q_);   //队列间转移
void delete_(queue* q);  //执行完的进程踢出队列
void print_transfer(queue q);  //输出转移插入信息
void print_finish(queue q); //输出完成信息void executor(queue* q_,queue q[]);
void add_WaitTime(queue* q_, queue q[]); //增加等待时间
void print_executed(queue* q);   //输出执行信息void print_average_WaitTime(int time);     //输出总的平均等待时间int main() {queue q[num_Queue] = {};init_queues(q); //初始化多级队列InitializeCriticalSection(&cs); //初始化临界区Sema[0] = CreateSemaphore(NULL, 0, num_Process, NULL);    //创建信号量，注意把信号量上限调为最大进程数   X(Sema[1] = CreateSemaphore(NULL, 0, num_Process, NULL);HANDLE handle[2];   //给generator、scheduler函数辅以线程handle[0] = CreateThread(NULL, 0, generator, (void*)&q[0], 0, NULL);handle[1] = CreateThread(NULL, 0, scheduler, (void*)q, 0, NULL);WaitForMultipleObjects(2, handle, TRUE, INFINITE);  //等待所有进程结束for (int i = 0; i < 2; i++) {CloseHandle(handle[i]);}DeleteCriticalSection(&cs);getchar();return 0;
}void init_queues(queue q[]) {    //初始化队列for (int i = 0; i < num_Queue; i++) {q[i].priority = i + 1;q[i].timeSlice = minTimeSlice * (int)pow(2, i);q[i].list = NULL;}return;
}DWORD WINAPI generator(LPVOID q_) {srand((unsigned)time(NULL));	//随机数种子queue* q = (queue*)q_;int count_process = 0;  //记录已生成的进程数int sleep = 0;  //记录休眠时间int count_sleep = 0;    //记录总计休眠时间while (count_process < num_Process) {PCB* pcb = init_PCB(count_process, count_sleep); //填入pid和到达时间（不觉得很怪吗）print_generated(pcb);sleep = 1 + rand() % 100;count_sleep += sleep;print_sleep(sleep);EnterCriticalSection(&cs);insert_queue(q, pcb);   //插入第一队列的队尾LeaveCriticalSection(&cs);ReleaseSemaphore(Sema[0], 1, NULL); //同步scheduler进行调度第一队列ReleaseSemaphore(Sema[1], 1, NULL); //唤醒访问第一队列的executorcount_process++;Sleep(sleep);    //隔一个随机的时间段}return 0;
}PCB* init_PCB(int pid, int time) {PCB* pcb = (PCB*)malloc(sizeof(PCB));pcb->pid = pid;pcb->arrivalTime = time;pcb->neededTime = neededTimeLB + rand() % (neededTimeUB - neededTimeLB + 1);pcb->next = NULL;pcb->priority = 1;pcb->state = 'w';pcb->totalWaitTime = 0;pcb->usedTime = 0;return pcb;
}void insert_queue(queue* q, PCB* pcb) {if (q->list == NULL) {q->list = pcb;return;}else{   //否则往后传到队尾，令队尾的下一个为新来的pcbPCB* temp = q->list;while (temp->next != NULL) {temp = temp->next;}temp->next = pcb;return;}
}void print_generated(PCB* pcb) {printf("Generator：Process %d is generated, neededTime = %d, arrivalTime = %d.\n", pcb->pid, pcb->neededTime, pcb->arrivalTime);return;
}void print_sleep(int sleep) {printf("Generator：Sleep for %d ms before generating next new process...\n", sleep);return;
}DWORD WINAPI scheduler(LPVOID q_) {queue* q = (queue*)q_;int count_finish = 0;while (count_finish < num_Process) {    //当完成数没达到总线程数时进行循环WaitForSingleObject(Sema[0], INFINITE); //当多级队列为空、以及开始时等待同步信号量do {    //当不为空时进入调度for (int i = 0; i < num_Queue; i++) {if (q[i].list != NULL) {executor(&q[i], q);if (q[i].list->neededTime > q[i].list->usedTime) {if (i < (num_Queue - 1)) {EnterCriticalSection(&cs);transfer(&q[i], &q[i + 1]);print_transfer(q[i + 1]);LeaveCriticalSection(&cs);}}else {print_finish(q[i]);delete_(&q[i]);count_finish++;}break;  //执行完一次后重新从一级队列开始扫描}}} while (!isEmpty(q));}print_average_WaitTime(WaitTime);return 0;
}bool isEmpty(queue q[]){for (int i = 0; i < num_Queue; i++) {if (q[i].list != NULL) {return false;}}return true;
}void transfer(queue* q, queue* q_) {PCB* temp_ = q_->list;PCB* temp = q->list;    //记录原队列头PCB的地址while (temp_ != NULL && temp_->next != NULL) {  //功能是当队列不为空时，找到当前队列最后一个元素temp_ = temp_->next;}q->list = q->list->next;  //原队列头指针指向下一个PCBif (temp_ != NULL) {temp_->next = temp;     //原队列头PCB被下一队列队尾(队尾不为空)指向}else {q_->list = temp;   //原队列头PCB被下一队列队头(队列为空)指向}temp->next = NULL;      //原队列头PCB指向NULL，作为下一队列新的队尾return;
}void delete_(queue* q) {WaitTime += q->list->totalWaitTime;  //记录等待时间PCB* temp = q->list;q->list = q->list->next;free(temp);return;
}void print_transfer(queue q) {while (q.list->next != NULL) {q.list = q.list->next;}printf("Scheduler：Process %d is moved to queue %d, priority = %d.\n", q.list->pid, q.priority - 1, q.priority);return;
}void print_finish(queue q) {printf("Scheduler：Process %d was done,total wait time = %d.\n", q.list->pid, q.list->totalWaitTime);return;
}void executor(queue* q_, queue q[]) {if (q_->priority == 1) { //如果执行的队列是第一队列，则要等待生成器的信号，并且进入临界区执行WaitForSingleObject(Sema[1], INFINITE);     //出现谜之问题EnterCriticalSection(&cs);Sleep(q_->timeSlice);q_->list->usedTime += q_->timeSlice;add_WaitTime(q_, q);print_executed(q_);LeaveCriticalSection(&cs);}else {Sleep(q_->timeSlice);q_->list->usedTime += q_->timeSlice;add_WaitTime(q_, q);print_executed(q_);}return;
}void add_WaitTime(queue* q_, queue q[]) {PCB* temp;for (int i = 0; i < num_Queue; i++) {if (q[i].priority != q_->priority) {temp = q[i].list;while (temp != NULL) {temp->totalWaitTime += q_->timeSlice;temp = temp->next;}}else {temp = q[i].list;while (temp->next != NULL) {    //和上面不同，跳掉队头PCBtemp = temp->next;temp->totalWaitTime += q_->timeSlice;}}}return;
}void print_executed(queue* q) {printf("Executor：Process %d in queue %d consumes %d ms.\n", q->list->pid, q->priority - 1, q->timeSlice);return;
}void print_average_WaitTime(int WaitTime) {double avg_wt = WaitTime / num_Process;printf("Main：All processes done, average wait time is %.2lf.\n", avg_wt);return;
}

Alt

总结及心得

总结

本次实验的具体实现流程可以分为几个部分：

  1. 分析题目的要求，得出整体框架（各部分的包含关系）
  2. 分解各部分的任务，得到子任务（子函数）
  3. 将各个子函数（未实现）以及其他细节像拼积木一样直接拼出各部分的实现
  4. 逐个实现子函数的功能
  5. 痛苦的DEBUG->完成

心得

  1. 面对较为复杂的任务时，自顶向下模块化设计的解决方式是非常管用的，因为它能够使你跳出对代码复杂具体实现的思考，让你在整体的、抽象的层面上进行规划和编排，并在这一过程中逐步分解出任务的层次结构，从而达到将整块大任务分解成一个个小任务的效果。
  2. 说人话就是，这相当于在做排除法，将任务切成一块一块的，以免遭遇到分析一整块大任务时，来自其内部不同部分的干扰，当排除了这些干扰，一次只做一两件事情，效率就会变得非常高。
  3. 第一次写博客，孩子很喜欢，下一次还要写，之后可能不单会写和编程相关的内容，还会写一些个人的思考、跨学科相关的想法等等。

http://chatgpt.dhexx.cn/article/cd51qCRp.shtml

相关文章

[算法] 栈和队列

[算法] 栈和队列

欢迎来到老胡的算法解题思路&#xff0c;本文章主要使用的语言为java&#xff0c;使用的题型为力扣算法题&#xff0c;基于这一篇文章&#xff0c;我将为你介绍栈和队列的基础知识和栈和队列的题型&#xff0c;喜欢的朋友可以关注一下&#xff0c;下次更新不迷路&#xff01; 目…
阅读更多...
十道经典面试算法真题详解

十道经典面试算法真题详解

前言 分享一下 腾讯常考的十道算法题&#xff08;真题&#xff09;。在金三银四&#xff0c;希望对大家有帮助呀。 重排链表 最长递增子序列 环形链表 反转链表 最长回文子串 全排列 LRU 缓存 合并K个升序链表 无重复字符的最长子串 删除链表的倒数第 N 个结点 1. …
阅读更多...
队列相关习题

队列相关习题

1.已知循环队列存储在一维数组A0…n-1]中&#xff0c;且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空&#xff0c;且要求第一个进入队列的元素存储在A[0]处&#xff0c;则初始时front和rear的值分别是( )。 A.0&#xff0c;0 B. 0&#xff0c;n-1 C. n-…
阅读更多...
java算法面试题_Java算法面试题汇总

java算法面试题_Java算法面试题汇总

原标题&#xff1a;Java算法面试题汇总 1. 字符串 如果IDE没有代码自动补全功能&#xff0c;所以你应该记住下面的这些方法。 toCharArray() // 获得字符串对应的char数组 Arrays.sort() // 数组排序 Arrays.toString(char[] a) // 数组转成字符串 charAt(int x) // 获得某个索…
阅读更多...
详解单调队列算法

详解单调队列算法

前言 嘿！彩蛋！感觉有帮助就三连呗！ 如果你对这篇文章可感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。 在上一篇文章中，我们介绍了「单调栈」这一最常考察的线性数据结构。而今天我们将继续沿着这个思路，介绍另…
阅读更多...
栈和队列相关经典算法题总结(数据结构+C语言)

栈和队列相关经典算法题总结(数据结构+C语言)

我们这里针对栈和队列的一些经典算法题做详细讲解: 1.括号匹配问题. 2.用队列实现栈. 3.用栈实现队列. 4.设计循环队列. 一.详细讲解如下: 1.括号匹配问题.(如下图) 给定一个只包括 (&#xff0c;)&#xff0c;{&#xff0c;}&#xff0c;[&#xff0c;] 的字符串 s &am…
阅读更多...
qt使用消息队列服务器,qt代码实现消息队列通信

qt使用消息队列服务器,qt代码实现消息队列通信

qt代码实现消息队列通信 内容精选 换一换 HBase 1.X版本在RPC流程中&#xff0c;多个数据通信线程会争抢同一个缓存Buffer队列&#xff0c;代码以lock重入锁实现线程安全&#xff0c;锁抢占严重&#xff0c;导致HBase不能充分发挥CPU多核的能力。HBase 1.X版本的RPC通信机制中B…
阅读更多...
消息队列MQ常见面试题

消息队列MQ常见面试题

面试官在面试候选人时&#xff0c;如果发现候选人的简历中写了在项目中使用了 MQ 技术&#xff08;如 Kafka、RabbitMQ、RocketMQ&#xff09;&#xff0c;基本都会抛出一个问题&#xff1a;在使用 MQ 的时候&#xff0c;怎么确保消息 100% 不丢失&#xff1f; 这个问题在实际…
阅读更多...
RabbitMQ消息队列常见面试题总结

RabbitMQ消息队列常见面试题总结

1、什么是消息队列&#xff1a; 1.1、消息队列的优点&#xff1a; &#xff08;1&#xff09;解耦&#xff1a;将系统按照不同的业务功能拆分出来&#xff0c;消息生产者只管把消息发布到 MQ 中而不用管谁来取&#xff0c;消息消费者只管从 MQ 中取消息而不管是谁发布的。消息…
阅读更多...
【消息队列】面试题及答案整理

【消息队列】面试题及答案整理

消息队列面试题 为什么要使用消息队列/消息队列的应用场景使用了消息队列会有什么缺点如何保证消息队列是高可用的RocketMQ是如何保证消息队列是高可用的 如何保证消息不被重复消费/如何保证消息消费的幂等性如何保证消费的可靠性传输RocketMQ如何保证消费的可靠性传输RabbitMQ…
阅读更多...
JAVA——快速排序（详细）

JAVA——快速排序（详细）

JAVA快速排序的实现 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高&#xff0c;因此经常被采用&#xff0c;再加上快速排序思想----分治法也确实实用&#xff0c;因此很多软件公司的笔试面试&#xff0c;包括像腾讯&#xff0c;微软等知名IT公司都喜欢考这个&…
阅读更多...
快速排序算法（java实现）

快速排序算法（java实现）

基本思想 快速排序是一种采用分治法解决问题的一个典型应用&#xff0c;也是冒泡排序的一种改进。它的基本思想是&#xff0c;通过一轮排序将待排记录分割成独立的两部分&#xff0c;其中一部分均比另一部分小&#xff0c;则可分别对这两部分继续进行排序&#xff0c;已达到整…
阅读更多...
java快速排序（含快速排序代码）

java快速排序（含快速排序代码）

目录 一&#xff1a;快速排序思想 二&#xff1a;快速排序代码&#xff08;pivot一定时先和arrays【r】先比较&#xff09; 三&#xff1a;结果 一&#xff1a;快速排序思想 假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准…
阅读更多...
快速排序 Java 实现

快速排序 Java 实现

概念 快速排序&#xff08;Quicksort&#xff09;是对冒泡排序的一种改进。 参考: [数据结构与算法(Kotlin语言)]1.冒泡排序&#xff08;Bubble Sort&#xff09; 快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略&#xff0c;通常称其为分治法(…
阅读更多...
java快速排序详解

java快速排序详解

文章目录 一、快排原理二、实例操作三、实战代码四、总结 一、快排原理 从待排序区间选择一个数&#xff0c;作为基准值&#xff08;pivot&#xff09;&#xff1b;遍历整个待排序区间&#xff0c;将比基准值小的&#xff08;可等于&#xff09;放到基准值左边&#xff0c;将比…
阅读更多...
快速排序Java

快速排序Java

基本思想 快速排序的基本思想&#xff1a;通过一趟排序将待排记录分隔成独立的两部分&#xff0c;其中一部分记录的关键字均比另一部分的关键字小&#xff0c;则可分别对这两部分记录继续进行排序&#xff0c;以达到整个序列有序。 算法描述 快速排序使用分治法来把一个串&…
阅读更多...
快速排序 Java模板

快速排序 Java模板

快速排序Java模板 详情参考 https://www.acwing.com/problem/content/787/ https://www.acwing.com/solution/content/2096/ 快速排序的整体过程&#xff0c;动态变化流程 以从小到大排序为例 选择一个目标参考值 p i v i t pivit pivit&#xff0c;通常课本上会说选择数组…
阅读更多...
java 实现快速排序

java 实现快速排序

1.介绍 快速排序是对冒泡排序的一种改进。它的基本思想是&#xff1a;通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一 部分的所有数据都比另外一部分的所有数据都要小&#xff0c;然后再按此方法对这两部分数据分别进行快速排序&#xff0c;整个排序 过程可以…
阅读更多...
使用 Java 实现快速排序（详解）

使用 Java 实现快速排序（详解）

一、概述 最近在看一些面试题&#xff0c;发现很多面试过程中都会要求手写快速排序&#xff0c;查阅一些博客发现别人写的并不是特别清楚而且也很难记住&#xff0c;所以为了更好的掌握这个算法&#xff0c;所以在这篇文章中&#xff0c;将自己的学习过程记录下来&#xff0c;…
阅读更多...
【JAVA】快速排序

【JAVA】快速排序

快排&#xff0c;和冒泡排序一样&#xff0c;是同一类型的排序&#xff0c;都是交换排序 交换&#xff0c;涉及在遍历中比较&#xff0c;然后相互交换元素 冒泡排序是根据趟数两两比较&#xff0c;边比较边交换&#xff0c;快排也一样&#xff0c;不过冒泡是以顺序表的格式进…
阅读更多...
推荐文章

Copyright @ 2022~2023