-
冒泡排序深入理解
2019-09-22 20:43:12冒泡排序深入理解 题目全部来自洛谷 对于冒泡排序有一个小性质: 每一次都会把序列未排好序的最大数"沉底", 即推到序列尾部 ...这是Bessie的对长度为N的数组A进行排序的奶牛码实现。 sorted = false wh...冒泡排序深入理解
题目全部来自洛谷
对于冒泡排序有一个小性质: 每一次都会把序列未排好序的最大数"沉底", 即推到序列尾部
1.P4378 Out of Sorts S
留意着农场之外的长期职业生涯的可能性,奶牛Bessie开始在不同的在线编程网站上学习算法。
她到目前为止最喜欢的算法是“冒泡排序”。这是Bessie的对长度为N的数组A进行排序的奶牛码实现。
sorted = false while (not sorted): sorted = true moo for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] sorted = false
显然,奶牛码中的“moo”指令的作用只是输出“moo”。奇怪的是,Bessie看上去执着于在她的代码中的不同位置使用这个语句。
给定一个输入数组,请预测Bessie的代码会输出多少次“moo”。
题意即进行多少次冒泡排序
对于一个序列, 我们称之为有序的, 当且仅当对于任意一个位置前面没有比它大的数(可以模拟一下)
比如:6 1 2 3 4 5 进行一次为 1 2 3 4 5 6
那么对于位置i, 冒泡排序进行到i-1时, 为前i1个数中最大的一个, 如果它大于那么它就会到的后面
由此可推知, 每一次位置i前都会将一个比大的数推至其后, 直至没有比它大的
那么我们对每位置求一下它前面有几个比它大就好啦(注意要将答案加一)
具体来说先进行离散化, 再树状数组求解即可
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100500; int d[N], n; int read(void) { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)){ x = (x << 3) + (x << 1) + c - '0'; c = getchar(); } return x; } struct node{ int val, pos; bool operator < (const node &i) const{ if (val == i.val) return pos < i.pos; return val < i.val; } }p[N]; inline int low(int x) { return x & -x; } int get(int x) { int tmp = 0; for (;x;x -= low(x)) tmp += d[x]; return tmp; } void add(int x) { for (;x <= n; x += low(x)) d[x]++; } bool cmp(node i,node j) { return i.pos < j.pos; } int main() { n = read(); for (int i = 1;i <= n; i++) p[i] = (node){read(),i}; sort(p + 1,p + n + 1); for (int i = 1;i <= n; i++) p[i].val = i; sort(p + 1,p + n + 1, cmp); int ans = 0; for (int i = 1;i <= n; i++) { add(p[i].val); ans = max(ans, i - get(p[i].val)); } printf ("%d\n", ans+1); return 0; }
2.P4375 Out of Sorts G
sorted = false while (not sorted): sorted = true moo for i = 0 to N-2: if A[i+1] < A[i]: swap A[i], A[i+1] for i = N-2 downto 0: if A[i+1] < A[i]: swap A[i], A[i+1] for i = 0 to N-2: if A[i+1] < A[i]: sorted = false
给定一个输入数组,请预测Bessie的代码会输出多少次“moo”。
题意:求双向冒泡排序的排序次数
对于一个序列, 我们称之为有序的, 当且仅当对于任意一个位置前面没有比它大的数(可以模拟一下)
我们暂且称它为平衡条件吧
首先将序列离散化
相比较于Out of Sorts S, 本题思路在于不动的位置, 结论为对于位置x, ans = max{ans, 前面有几个数的数值大于x}
为什么呢
在x不满足平衡条件的时候
首先第一波操作的时候,对于前x个位置一定会换出一个大于x的数
因为它不满足平衡条件
第二波操作时, 又会有一个小于等于x的数插回来
因为回来的时候一定会冒泡出一个位置在x后的最小值, 因为x不满足平衡条件, 所以最小值小于等于x, 就又插了回来
有人可能会问为什么Out of Sorts S不能用这个式子嘞, 因为每次换出的一定大于x, 但x+1位置上的数可能换过来, 而它有可能大于x
由此可知, 求每个位置前大于其的数就行啦
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 100500; int d[N], n; int read(void) { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)){ x = (x << 3) + (x << 1) + c - '0'; c = getchar(); } return x; } struct node{ int val, pos; bool operator < (const node &i) const{ if (val == i.val) return pos < i.pos; return val < i.val; } }p[N]; inline int low(int x) { return x & -x; } int get(int x) { int tmp = 0; for (;x;x -= low(x)) tmp += d[x]; return tmp; } void add(int x) { for (;x <= n; x += low(x)) d[x]++; } bool cmp(node i,node j) { return i.pos < j.pos; } int main() { n = read(); for (int i = 1;i <= n; i++) p[i] = (node){read(),i}; sort(p + 1,p + n + 1); for (int i = 1;i <= n; i++) p[i].val = i; sort(p + 1,p + n + 1, cmp); int ans = 1; for (int i = 1;i <= n; i++) { add(p[i].val); ans = max(ans, i - get(i)); } printf ("%d\n", ans); return 0; } /* 6 2 5 6 3 1 4 */
3.P4372 Out of Sorts P
留意着农场之外的长期职业生涯的可能性,奶牛Bessie开始在不同的在线编程网站上学习算法。她最喜欢的两个算法是“冒泡排序”和“快速排序”,但是不幸的是Bessie轻易地把它们搞混了,最后实现了一个奇怪的混合算法! 如果数组A中A[…i]的最大值不大于A[i+1…]的最小值,我们就称元素i和i+1之间的位置为一个“分隔点”。Bessie还记得快速排序包含对数组的重排,产生了一个分隔点,然后要递归对两侧的A[…i]和A[i+1…]排序。然而,尽管她正确地记下了数组中所有的分隔点都可以在线性时间内被求出,她却忘记快速排序应该怎么重排来快速构造一个分隔点了!在这个可能会被证明是排序算法的历史中最糟糕的算法性失误之下,她做出了一个不幸的决定,使用冒泡排序来完成这个任务。
以下是Bessie最初的对数组AA进行排序的实现的概要。她首先写了一个简单的函数,执行冒泡排序的一轮:
bubble_sort_pass (A) { for i = 0 to length(A)-2 if A[i] > A[i+1], swap A[i] and A[i+1] }
她的快速排序(相当快)函数的递归代码是按下面的样子构成的:
quickish_sort (A) { if length(A) = 1, return do { // Main loop work_counter = work_counter + length(A) bubble_sort_pass(A) } while (no partition points exist in A) divide A at all partition points; recursively quickish_sort each piece }
Bessie好奇于她的代码能够运行得多快。简单起见,她计算出她得主循环的每一轮都消耗线性时间,所以她相应增加一个全局变量work_counter的值,以此来跟踪整个算法总共完成的工作量。
给定一个输入数组,请预测quickish_sort函数接收这个数组之后,变量work_counter的最终值。
这道题用到了一个套路, 就是"横向变纵向"
求每一次冒泡排序的长度, 不如求每一个点被冒泡排序了几次
定义分割点为i与i+1的分割线,不妨假设它就在i上吧
再次定义序列排好序的标准
我们称一个序列是有序的当且仅当所有点(除了n)都是分割点
那么接下来我们要求分割点的出现时间t数组
为什么求:
对于每个点它不用在进行冒泡排序了当且仅当两边都已成为分割点, 也就是两边出现时间的最大值
依据t数组,我们可以求出每个点被排了几次
怎么求(敲重点):
首先离散化
对于一个点x来说, 所有小于它的数却在它后面的, 每一次都会向前走一次
那么它出现的时间就是离它最远的小于它的点冒泡到它前面的时间
即那个点到它的距离, 具体见代码
所以单调队列或指针都可以维护
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int N = 100500; int d[N], n; int read(void) { int x = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)){ x = (x << 3) + (x << 1) + c - '0'; c = getchar(); } return x; } struct node{ int val, pos; bool operator < (const node &i) const{ if (val == i.val) return pos < i.pos; return val < i.val; } }p[N]; bool cmp(node i,node j) { return i.pos < j.pos; } int t[N], k; int main() { // freopen("hs.in","r",stdin); n = read(); for (int i = 1;i <= n; i++) p[i] = (node){read(),i}; sort(p + 1,p + n + 1); for (int i = 1;i <= n; i++) p[i].val = i; sort(p + 1,p + n + 1, cmp); long long ans = 0; k = n; for (int i = n;i >= 1; i--) { while (p[k].val > i) k--; t[i] = max(p[k].pos - i, 1); } for (int i = 0;i < n; i++) ans += max(t[i], t[i+1]); printf ("%lld\n", ans); return 0; } /* 6 2 5 6 3 1 4 */
4.T99343 奇怪的排序
您有一个正整数序列, 您可以选择任意相邻的两个数插入另两个数之间,或序列首和尾;
假如序列为: 1 2 4 3 5 6
可以选2 4
插在序列首 2 3 4 3 5 6
插到3后 1 3 2 4 5 6
插到5后 4 3 5 1 2 6
插在6后 1 3 5 6 2 4
现在hs-black需要判断是否进行若干次操作能使序列变得有序(无论正序倒序), 蒟蒻hs-black当然不会啦, 请您帮帮他…这道题来源于一位数竞大佬提供的灵感
再次定义一个序列有序
我们称一个序列是有序的,当且仅当它的逆序对数为0或n*(n-1)/2;
引理1: 交换序列中相邻的两个数会改变原序列逆序对个数的奇偶性
引理2: 将序列相邻两个数插入别处不会改变原序列逆序对个数的奇偶性
证明: 不断将与它右边的数字交换直至正好换到 即此时共交换了q - j 次
再将ai 向右与相邻数字交换q-1-i次到左侧 ,此时共交换2 * (q - j) 次,为偶数次,所以奇偶性不变
那么说明逆序对数与排序好的逆序对数奇偶性不同时不能满足要求
下面证明相同时可以满足要求
以正序为例, 每次将序列最小的数和后面的数插到已排序部分的后面, 如果最小数在最后时就将后2,3个数插在它后面
当未排序列只剩两个数时, 逆序对个数也一定是偶数, 只可能是0
即序列有序, 证毕
具体实现是讨论一下n*(n-1)/2的奇偶性, 并树状数组求出原序列逆序对个数
代码:
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> const int M = 500005; using namespace std; int n, sum[M]; struct Num{ int val,num; inline friend bool operator < (Num a,Num b){ return a.val > b.val; } }p[M]; inline int lowbit(int x){ return x&-x; } void add(int k,int x){ while(k<=n){ sum[k]+=x; k+=lowbit(k); } } int getsum(int k){ int tmp=0; while(k>0){ tmp+=sum[k]; k-=lowbit(k); } return tmp; } long long Ans=0; char ss[1<<17],*A=ss,*B=ss; inline char gc() {if(A==B){B=(A=ss)+fread(ss,1,1<<17,stdin);if(A==B)return EOF;}return*A++;} template<class T>inline void read(T&x){ cin >> x ; } int main(){ int t; read(t); while(t--) { Ans = 0; memset(sum, 0, sizeof(sum)); read(n); for(int i=1;i<=n;i++){ read(p[i].val); p[i].num=i; } sort(p+1,p+n+1); for(int i=1;i<=n;i++){ add(p[i].num,1); Ans+=getsum(p[i].num-1); } // printf ("%lld\n", Ans); if (n % 4 > 1) printf("Yes\n"); else if (Ans % 2 == 1) printf("No\n"); else printf("Yes\n"); } return 0; }
-
做了一个小时的面试题(没有过 希望大家帮忙答下 虽然很幼稚 毕竟每个人都是这么过来的吗 感激了!...
2010-04-16 11:10:58通常这一组类有一个公共的抽象父类并且实现了相同的方法,但是这些方法针对不同的数据进行了不同的操作。 首先需要定义一个基类,该类的子类通过不同的方法实现了基类中的方法。 然后需要定义一个工厂类,工厂... -
超级有影响力霸气的Java面试题大全文档
2012-07-18 09:47:04Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 13、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、... -
面试题36:数组中的逆序对:这道题可以这么想,我们要找到数组中的逆序对,可以看做对数据进行排序,需要交换数组中的元素的次数,但是防止相同大小的元素发生交换,因此需要选择一个稳定的排序方法,记录发生交换的...
-
3.1 保证了不同线程对这个变量进行操作时的可见性,即一个线程修改了某个变量的值,这新值对其他线程来说是立即可见的。(保证可见性) 3.2 禁止进行指令重排序。(保证有序性) 划个重点:volatile 关键字能保证...
-
C#开发实战1200例(第1卷).(清华出版.王小科.王军.扫描版).part1
2016-06-16 20:55:43实例100 使用冒泡排序法对一维数组进行排序 实例101 使用快速排序法对一维数组进行排序 实例102 使用直接插入法对一维数组进行排序 实例103 使用希尔排序法对一维数组进行排序 实例104 使用Sort方法对数组进行... -
C#开发实战1200例(第1卷).(清华出版.王小科.王军.扫描版).part2
2016-06-16 20:59:52实例100 使用冒泡排序法对一维数组进行排序 实例101 使用快速排序法对一维数组进行排序 实例102 使用直接插入法对一维数组进行排序 实例103 使用希尔排序法对一维数组进行排序 实例104 使用Sort方法对数组进行... -
C#开发实战1200例(第1卷).(清华出版.王小科.王军.扫描版).part3
2016-06-16 21:02:21实例100 使用冒泡排序法对一维数组进行排序 实例101 使用快速排序法对一维数组进行排序 实例102 使用直接插入法对一维数组进行排序 实例103 使用希尔排序法对一维数组进行排序 实例104 使用Sort方法对数组进行... -
数据结构课程设计
2014-06-03 13:26:058、英国人格思里于1852年提出四色问题(four colour problem,亦称四色猜想),即在为一平面或一球面的地图着色时,假定每一个国家在地图上是一个连通域,并且有相邻边界线的两个国家必须用不同的颜色,问是否只要四... -
计算机二级公共基础知识
2011-04-30 14:00:09性质4:具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n的整数部分。 3. 满二叉树与完全二叉树 满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在满二叉树中... -
C#开发实战1200例(第一卷+第二卷)+源码下载地址.txt
2019-05-17 09:24:24实例100 使用冒泡排序法对一维数组进行排序 118 实例101 使用快速排序法对一维数组进行排序 119 实例102 使用直接插入法对一维数组进行排序 121 实例103 使用希尔排序法对一维数组进行排序 122 实例... -
C#开发实例大全(基础卷).软件开发技术联盟(带详细书签) PDF 下载
2018-02-20 01:26:55实例100 使用冒泡排序法对一维数组进行排序 118 实例101 使用快速排序法对一维数组进行排序 119 实例102 使用直接插入法对一维数组进行排序 121 实例103 使用希尔排序法对一维数组进行排序 122 实例104 使用Sort方法... -
1.3.2 给定一个链表,删除链表的倒数第N个节点,并且返回链表的头结点 1.3.3 如果让你设计一个通用的、支持各种数据库秒级备份和恢复的系统,你会如何设计 1.3.4 如果让你来设计一个支持数据库、NOSQL 和大数据...
-
数据结构课设
2013-01-03 02:51:25之一为倒序),每个样本有20000随机整数,利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序(递归和非递归),基数排序八种排序方法进行排序(结果为由小到大的顺序),并统计每一种... -
java 面试题 总结
2009-09-16 08:45:34Collections是针对集合类的一个帮助类,他提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。 10、&和&&的区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap... -
计算机二级C语言考试题预测
2010-06-08 18:29:34(42) 希尔排序法属于哪一种类型的排序法(B) A.交换类排序法 B.插入类排序法 C.选择类排序法 D.建堆排序法 (43) 在深度为5的满二叉树中,叶子结点的个数为(C) A. 32 B. 31 C. 16 D. 15 (44) 对长度为N的线性表进行... -
二级C语言公共基础知识
2009-11-20 11:26:03(12) 在最坏情况下,冒泡排序的时间复杂度为______。 答:n(n-1)/2#n*(n-1)/2#O(n(n-1)/2)#O(n*(n-1)/2) (13) 面向对象的程序设计方法中涉及的对象是系统中用来描述客观事物的一个______。 答:实体 (14) 软件的... -
delphi 开发经验技巧宝典源码
2010-08-12 16:47:230086 用回溯法找出n个自然数中取r个数的所有组合 58 0087 0~N位数的任意组合 59 0088 在数组中快速查找近似值 60 0089 实现直接插入法排序 61 第4章 函数应用 63 4.1 字符串处理函数 64 0090 使用... -
c语言经典案例
2014-10-30 08:06:57本文件中讲述了c语言经典的282个案例,由浅入深。有利于提高广大爱好c语言编程的人员。 其中包括: 第1章 初识C语言 1 实例001 第一个C语言程序 2 实例002 一个完整的C语言程序 2 实例003 输出名言 3 实例004 用TC ... -
javascript入门笔记
2018-05-15 15:01:07条件是一个boolean类型的数据,如果条件结果为true,则执行表达式1的内容,并将表达式1的结果作为整体表达式的结果。如果条件为false,则执行表达式2的内容,并将表达式2的结果作为整体表达式的结果 ex: var age ... -
《Java Web开发实战1200例(第I卷)》(清华出版.卢瀚.王春斌).part2 高清完整PDF版
2016-06-13 12:06:47实例041 冒泡排序法 实例042 快速排序法 实例043 选择排序法 实例044 插入排序法 实例045 归并排序法 2.6 算法应用 实例046 算法应用——百钱买百鸡 实例047 算法应用——韩信点兵 实例048 算法应用——... -
C#编程经验技巧宝典
2008-06-01 08:59:3343 <br>0061 树的实现 44 <br>3.2 排序 48 <br>0062 如何实现选择排序算法 48 <br>0063 如何实现冒泡排序算法 49 <br>0064 如何实现快速排序算法 50 <br>0065 如何实现插入排序算法 ...