堆排序,快速排序

news/2025/1/15 17:18:13/

目录

1.堆排序

2.快速排序

1.hoare版本

2.挖坑法

3.前后指针法

注意点


1.堆排序

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}
void adjustdown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);}else{break;}parent = child;child = parent * 2 + 1;}
}
void heapsort(int* a, int n)
{for (int i = (n - 1 -1) / 2; i >= 0; i--){adjustdown(a, n, i);}for (int i = n-1; i > 0; i--){Swap(&a[0], &a[i]);adjustdown(a, i, 0);}
}void printarr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}
void heaptest()
{int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 };printarr(arr, sizeof(arr)/sizeof(int));heapsort(arr, sizeof(arr)/sizeof(int));printarr(arr, sizeof(arr)/sizeof(int));
}

        我们先用向下调整算法建堆。

        使用向下调整算法建堆的前提是,该节点的子树都是堆。那么我们从最后一个节点的父节点开始向下调整算法,这样因为两个子树都是叶子节点,因此满足条件。从后往前,一直遍历到父节点为根节点,那么就建好堆了。

        然后只需要不断将第一个和最后一个节点的值交换,把最大值放到末尾,然后不断从根节点向下建堆,即可每次都挑选出最大值,我们依次把他们放到末尾即可。 

2.快速排序

主逻辑,递归

1.hoare版本

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}void printarr(int* a, int n)
{for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}int partsort(int* a, int left, int right)
{int keyi = left;while (left < right){while (left < right &&a[left] <= a[keyi]){left++;}while (left < right && a[right] >= a[keyi]){right--;}Swap(&a[left], &a[right]);//如果是因为left==right结束,交换值也并不影响结果}Swap(&a[keyi], &a[left]);return left;
}void quicksort(int* a, int begin, int end)
{if (begin >= end)return;int keyi = partsort(a, begin, end);quicksort(a, begin, keyi-1);quicksort(a, keyi + 1, end);
}void quicktest()
{int arr[] = { 4,7,1,9,3,6,5,8,3,2,0 };printarr(arr, sizeof(arr) / sizeof(int));quicksort(arr,0, sizeof(arr) / sizeof(int)-1);printarr(arr, sizeof(arr) / sizeof(int));
}

我们以左边第一个下标为keyi,因此先从右边开始找

1.先从右往左找到比a【keyi】小的值

2.再从左往右找到比a【keyi】大的值

交换这两个值。

3.不断重复以上过程直到相遇left == right

4.交换a【keyi】和a【left】

注意点

        1.我们在移动下标时,判断条件是a[left] <= a[keyi]left++

                                                        a[right] >= a[keyi] right--

        这是为了防止遇到与a【keyi】相等的值的时候,陷入死循环

        2.我们在寻找下标的小循环中也加入left<right的判断是因为防止极端情况。

        如果不判断就会越界,而且如果是因为left==right结束,交换值也并不影响结果

        同时因为这个极端情况原因,我们遍历是从最左边keyi处开始遍历,不然会忽略掉这种情况。也是注意点1中判断条件需要加=的原因

 

 3.我们再来谈谈为什么从一边开始调整要从另一边开始找起

以上面的情况为例子,

因为这样可以保证他们相遇时候所处在的值一定比a【keyi】小

情况1、left不动,right先移动与left相遇,此时a【keyi】还在原位

情况2.  right移动后找到小值,left移动后与right相遇,此时该位置的值比a【keyi】小

情况3,left与right先各自移动并且交换一次,然后right再移动和left相遇,此时因为已经交换过,a【left】处储存的值小于a【keyi】因此也符合

综上

2.挖坑法

 

int partsort(int* a, int left, int right)
{int key = a[left];while (left < right){while (left < right && a[right] >= key){right--;}a[left] = a[right];while (left < right && a[left] <= key){left++;}a[right] = a[left];}a[left] = key;return left;}

 

 

 

 

 

把a【keyi】的位置先挖走,记录这个key值。

1.从右边往左找小,把这个值填入坑中,同时这个位置形成一个新的坑

2.从左边往右找大 把这个值填入坑中,同时这个位置形成一个新的坑

3.重复以上操作,直到left==right,然后把key值填入这个坑中,此时这个位置一定是坑,因为left和right永远有一个是坑

3.前后指针法

int partsort(int* a, int left, int right)
{int prev = left;int cur = left + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)//这里直接判断一下,相等就不交换,并且在判断条件 //的地方就更新prev{Swap(&a[prev], &a[cur]);}++cur;//cur就是一直往前走,直到结束,遇到相应位置才有操作,因此直接放到循环中}Swap(&a[keyi], &a[prev]);keyi = prev;return keyi;}

cur一直向后找小于key的位置

如果a【cur】< key

++prev,然后交换a【prev】和a【cur】

如果cur所在位置的值都比key小,那么cur和prev拉不开差距.++prev后和cur交换就是自身交换

        如果遇到比key大的值,就会拉开差距,此时如果cur遇到比key小的值,这个值就会和一个比key大的值交换,因为prev和cur原本中间隔着的都是大于key的值,++prev后再交换就会是这样的结果

 

这样相当于把大的往右推,小的往左推

 

cur走出数组结束,key与a【prev】交换即可 

注意点

        以上三种方法只是实现形式不同,时间复杂度是完全相同的,并且主逻辑的代码不需要更改,就是一个递归,只需要把部分排序修改即可


http://www.ppmy.cn/news/1526318.html

相关文章

<Linux> 进程间通信

目录 一、进程间通信介绍 1. 进程间通信概念 2. 进程间通信目的 3. 进程间通信的本质 4. 进程间通信发展 5. 进程间通信分类 管道&#xff08;文件缓冲区&#xff09; System V IPC POSIX IPC 二、管道 1. 匿名管道 1.1 匿名管道原理 1.2 pipe系统调用 1.3 匿名管道的使用 1.4…

Leetcode 第 414 场周赛题解

Leetcode 第 414 场周赛题解 Leetcode 第 414 场周赛题解题目1&#xff1a;3280. 将日期转换为二进制表示思路代码复杂度分析 题目2&#xff1a;3281. 范围内整数的最大得分思路代码复杂度分析 题目3&#xff1a;3282. 到达数组末尾的最大得分思路代码复杂度分析 题目4&#xf…

在线查看 Android 系统源代码 AOSPXRef and AndroidXRef

在线查看 Android 系统源代码 AOSPXRef and AndroidXRef 1. AOSPXRef1.1. http://aospxref.com/android-14.0.0_r2/1.2. build/envsetup.sh 2. AndroidXRef2.1. http://androidxref.com/9.0.0_r3/2.2. build/envsetup.sh 3. HELLO AndroidReferences 1. AOSPXRef http://aospx…

Go中如何找到哪里依赖了某个module,如何找到所有module的最大GoVersion

如何找到哪里依赖了某个module 举例&#xff1a;如何找到哪个模块依赖了 github.com/Shopify/toxiproxy&#xff1f; 你可以使用以下方法查找 github.com/Shopify/toxiproxy 是通过哪个依赖模块引入的&#xff1a; 1. 使用 go mod graph go mod graph 命令可以输出模块的依…

四、(JS)JS中常见的加载事件

一、文档加载监听 &#xff08;1&#xff09;抛出疑惑&#xff0c;什么是文档加载监听&#xff1f;为什么要有这个东西&#xff1f; 老样子&#xff0c;我们先讲一个场景&#xff0c;带着大家熟悉为什么会有文档加载监听&#xff0c;是来解决什么问题来着的。 我们先看下这段…

【操作系统】二、进程管理:4.死锁(银行家算法、系统安全状态、静态分配策略、资源有序分配法)

五、死锁 文章目录 五、死锁1.产生1.1产生情况1.2产生的4个必要条件 2.处理方式2.1预防死锁2.1.1破坏互斥条件2.1.2破坏请求和保持条件2.1.3破坏不可抢占条件2.1.4破坏循环等待条件 2.2避免死锁2.2.1系统安全状态❗2.2.2银行家算法 2.3检测死锁2.4解除死锁 死锁&#xff1a;资源…

Nginx中return和rewrite的区别

引言 在Nginx中&#xff0c;return和rewrite都用于重定向请求&#xff0c;但还是有区别&#xff0c;写法也不一样。 1、return和rewrite区别 执行方式&#xff1a; return&#xff1a;立即终止当前请求处理流程&#xff0c;并返回指定的 HTTP 状态码和响应头。它是在 Nginx…

若依plus- cloud RuoYiGatewayApplication :8080/(ruoyi-gateway)启动不了,报错!

报错内容如下&#xff1a; Error starting ApplicationContext. To display the condition evaluation report re-run your application with debug enabled. 2024-09-11T09:16:50.29508:00 ERROR 10296 --- [ruoyi-gateway] [ main] o.s.boot.SpringApplication …