精华内容
下载资源
问答
  • 冒泡排序深入理解

    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时, ai1a_{i-1}为前i1个数中最大的一个, 如果它大于aia_i那么它就会到aia_i的后面

    由此可推知, 每一次位置i前都会将一个比aia_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 奇怪的排序

    您有一个正整数序列, 您可以选择任意相邻的两个数ai,ai+1a_i,a_{i+1}插入另两个数之间,或序列首和尾;
    假如序列为: 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: 将序列相邻两个数插入别处不会改变原序列逆序对个数的奇偶性

    ​ 证明: a1...aiaj ...aq ...ana_1...a_ia_j~...a_q~...a_n 不断将a j a~j~与它右边的数字交换直至正好换到aqa_qa1...ai...ajaq...ana_1...a_i... a_ja_q...a_n此时共交换了q - j 次

    ​ 再将ai 向右与相邻数字交换q-1-i次到aja_j左侧 ,此时共交换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;
    }
    
    展开全文
  • 通常这一组类有一公共的抽象父类并且实现了相同的方法,但是这些方法针对不同的数据进行不同的操作。 首先需要定义一基类,该类的子类通过不同的方法实现了基类中的方法。 然后需要定义一工厂类,工厂...
  • Collections是针对集合类帮助类,他提供一系列静态方法实现各种集合搜索、排序、线程安全化等操作。 13、&和&&区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 14、...
  • 面试题36:数组中的逆序:这道题可以这么想,我们要找到数组中的逆序,可以看做数据进行排序,需要交换数组中的元素的次数,但是防止相同大小的元素发生交换,因此需要选择一稳定的排序方法,记录发生交换的...
  • 3.1 保证了不同线程变量进行操作时可见性,即一线程修改了某个变量值,这新值其他线程来说是立即可见。(保证可见性) 3.2 禁止进行指令重排序。(保证有序性) 划重点:volatile 关键字能保证...
  • 实例100 使用冒泡排序一维数组进行排序 实例101 使用快速排序法一维数组进行排序 实例102 使用直接插入法一维数组进行排序 实例103 使用希尔排序法一维数组进行排序 实例104 使用Sort方法对数组进行...
  • 实例100 使用冒泡排序一维数组进行排序 实例101 使用快速排序法一维数组进行排序 实例102 使用直接插入法一维数组进行排序 实例103 使用希尔排序法一维数组进行排序 实例104 使用Sort方法对数组进行...
  • 实例100 使用冒泡排序一维数组进行排序 实例101 使用快速排序法一维数组进行排序 实例102 使用直接插入法一维数组进行排序 实例103 使用希尔排序法一维数组进行排序 实例104 使用Sort方法对数组进行...
  • 数据结构课程设计

    2014-06-03 13:26:05
    8、英国人格思里于1852年提出四色问题(four colour problem,亦称四色猜想),即在为一平面或一球面的地图着色时,假定每一国家在地图上是一连通域,并且有相邻边界线的两国家必须用不同的颜色,问是否只要四...
  • 性质4:具有n个结点二叉树,其深度至少为[log2n]+1,其中[log2n]表示取log2n整数部分。 3. 满二叉树与完全二叉树 满二叉树是指这样一种二叉树:除最后一层外,每一层上所有结点都有两个子结点。在满二叉树中...
  •  实例100 使用冒泡排序一维数组进行排序 118  实例101 使用快速排序法一维数组进行排序 119  实例102 使用直接插入法一维数组进行排序 121  实例103 使用希尔排序法一维数组进行排序 122  实例...
  • 实例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:34
    Collections是针对集合类帮助类,他提供一系列静态方法实现各种集合搜索、排序、线程安全化等操作。 10、&和&&区别。 &是位运算符,表示按位与运算,&&是逻辑运算符,表示逻辑与(and)。 11、HashMap...
  • (42) 希尔排序法属于哪一种类型的排序法(B) A.交换类排序法 B.插入类排序法 C.选择类排序法 D.建堆排序法 (43) 在深度为5的满二叉树中,叶子结点的个数为(C) A. 32 B. 31 C. 16 D. 15 (44) 长度为N的线性表进行...
  • (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:23
    0086 用回溯法找出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 ...
  • 实例041 冒泡排序法 实例042 快速排序法 实例043 选择排序法 实例044 插入排序法 实例045 归并排序法 2.6 算法应用 实例046 算法应用——百钱买百鸡 实例047 算法应用——韩信点兵 实例048 算法应用——...
  • C#编程经验技巧宝典

    热门讨论 2008-06-01 08:59:33
    43 <br>0061 树实现 44 <br>3.2 排序 48 <br>0062 如何实现选择排序算法 48 <br>0063 如何实现冒泡排序算法 49 <br>0064 如何实现快速排序算法 50 <br>0065 如何实现插入排序算法 ...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

对n个不同的排序码进行冒泡排序