关于C++算法中归并排序的问题

求助大神,我写的这个归并排序的代码有什么问题,为什么程序运行后什么也不输出呢?

#include<iostream>
using namespace std;
void erfen(int A[],int low,int high);
void paixu(int A[],int low,int mid,int high);

int main()
{
    int num[2] = {3,4};
    erfen(num, 0,1);
    for (int i = 0; i < 2; i++)
        cout << num[i] << endl;

    return 0;
}
void paixu(int A[], int low, int mid, int high)
{
    int* B = new int[high - low + 1];
    int i = low;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= high)
    {
        if (A[i] <= A[j])B[k++] = A[i++];
        else B[k++] = A[j++];
    }
    while (i <= mid)B[k++] = A[i++];
    while (j <= high) B[k++] = A[j++];
    //填充原数组
    for (int x = low, k = 0; x <= high; i++)
        A[i] = B[k++];
    delete [] B;
}
void erfen(int A[], int low, int high)
{

    if (low < high)
    {
        int mid = (low + high) / 2;
        erfen(A,low,mid);
        erfen(A, mid + 1,high);
        paixu(A, low, mid, high);
    }
}

程序运行后,先是卡住几秒,然后输出“请按任意键继续...”

c++

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
关于C++算法中归并排序的问题
求助大神,我写的这个归并排序的代码有什么问题,为什么程序运行后什么也不输出呢? ``` #include<iostream> using namespace std; void erfen(int A[],int low,int high); void paixu(int A[],int low,int mid,int high); int main() { int num[2] = {3,4}; erfen(num, 0,1); for (int i = 0; i < 2; i++) cout << num[i] << endl; return 0; } void paixu(int A[], int low, int mid, int high) { int* B = new int[high - low + 1]; int i = low; int j = mid + 1; int k = 0; while (i <= mid && j <= high) { if (A[i] <= A[j])B[k++] = A[i++]; else B[k++] = A[j++]; } while (i <= mid)B[k++] = A[i++]; while (j <= high) B[k++] = A[j++]; //填充原数组 for (int x = low, k = 0; x <= high; i++) A[i] = B[k++]; delete [] B; } void erfen(int A[], int low, int high) { if (low < high) { int mid = (low + high) / 2; erfen(A,low,mid); erfen(A, mid + 1,high); paixu(A, low, mid, high); } } ``` 程序运行后,先是卡住几秒,然后输出“请按任意键继续...”
归并算法java实现的问题
package algorithm; public class MergeSort { // private static long sum = 0; /** *  * <pre> *  * 二路归并 *  * 原理:将两个有序表合并和一个有序表 *  * </pre> *  * *  * @param a *  * @param s *  * 第一个有序表的起始下标 *  * @param m *  * 第二个有序表的起始下标 *  * @param t *  * 第二个有序表的结束小标 *  * */ private static void merge(int[] a, int s, int m, int t) { int[] tmp = new int[t - s + 1]; int i = s, j = m, k = 0; while (i < m && j <= t) { if (a[i] <= a[j]) { tmp[k] = a[i]; k++; i++; } else { tmp[k] = a[j]; j++; k++; } } while (i < m) { tmp[k] = a[i]; i++; k++; } while (j <= t) { tmp[k] = a[j]; j++; k++; } System.arraycopy(tmp, 0, a, s, tmp.length); } /** *  * *  * @param a *  * @param s *  * @param len *  * 每次归并的有序集合的长度 */ public static void mergeSort(int[] a, int s, int len) { int size = a.length; int mid = size / (len << 1); int c = size & ((len << 1) - 1); // -------归并到只剩一个有序集合的时候结束算法-------// if (mid == 0) return; // ------进行一趟归并排序-------// for (int i = 0; i < mid; ++i) { s = i * 2 * len; merge(a, s, s + len, (len << 1) + s - 1); } // -------将剩下的数和倒数一个有序集合归并-------// if (c != 0) merge(a, size - c - 2 * len, size - c, size - 1); // -------递归执行下一趟归并排序------// mergeSort(a, 0, 2 * len); } public static void main(String[] args) { int[] a = new int[]{4, 3, 6, 1, 2, 5}; mergeSort(a, 0, 1); for (int i = 0; i < a.length; ++i) { System.out.print(a[i] + " "); } } } 就这个算法,其他还好理解,那个mergesort方法完全看不懂,,不知道c和mid代表什么,也不了解位移运算符和&运算符的用法,有大神能帮我看一下么,谢谢了
C语言或C++实现,排序方法的时间比较?
利用随机函数产生10个样本,每个样本有20000个随机整数(并使第一个样本是正序,第二个样本是逆序)利用直接插入排序、希尔排序,冒泡排序、快速排序、选择排序、堆排序,归并排序、基数排序8种排序方法进行排序(结果为由小到大的顺序)并统计每一种排序算法对不同样本所耗费的时间。 基本要求(1) 原始数据存在文件中,用相同样本对不同算法进行测试; (2) 屏幕显示每种排序算法对不同样本所花的时间;
分治算法:二分归并排序的合并中一段代码有疑问
![图片说明](https://img-ask.csdn.net/upload/201903/20/1553018183_618620.png) 上图是数据 下图是合并代码 求大神帮帮忙!!! ![图片说明](https://img-ask.csdn.net/upload/201903/20/1553018246_640516.png)
排序的递归问题:能否用函数指针以及栈代替递归??
最近学习排序,对于快排,归并等处理海量数据效率高的算法很钟意,但是其自身的递归特性有很多缺点,譬如数据量过大时存在溢出的风险,也影响了算法的效率,故想到用栈代替递归这一过程。大致想法就是创建个函数指针类型的栈,然后将每个子排序的函数指针压入其中,然后再一个一个用*解引用来运行函数。当然我知道改成非递归有别的方法,但是可能会比这复杂,就想考虑用栈来实现。我想知道的是,对于快排和归并等递归排序算法,用以上方法实现的话,算法的开销(时间复杂度和空间复杂度),以及实际效率会是如何,有实际意义么。问题描述不全,毕竟第一次在CSDN提问,望前辈们多看看。本人大二,学了c++ java。
Java算法设计:迭代器实现排序(求各位大佬各抒己见)
老师预留的习题,说可能会考。希望能得到比较准备的回答用以备考。 假设你有M个迭代器(Java.util.Iterator),其中每一个迭代器定义为:由多个低成本基础迭代器组成,形成一个迭代器链(chain of Iterator),我们称之为resultant Iterator。每个resultant Iterator传递一个有序数据流。我们需要将这些数据流合并成一个最终有序数据流。 数据:每个数据由一串K个Key的序列组成 [k1,k2,k3,…,kK] 数据排序的规则为:最先排列k1,其次k2再次k3,……例如 [2,3,1,…] > [2,1,3,…] > [1,3,2,…]。每种key的排列在一个resultant Iterator中只会出现一次,但是多个resultant Iterator中可能出现相同的排列。 * 问题A:为了便于分析,我们假设每个resultant Iterator返回N个元素,设计一种算法,能得到最终有序数据流,同时效率高于 O(N.M.K.lg(M)). 并且计算所设计算法的复杂度。(可以设计你需要的变量和参数)。如果有多种算法,请简述各自的优劣。 * 问题B:简述如何重新设计迭代器,可以降低计算成本。为什么? * 问题C:若要在数据库中存储不可变的有序数据集(如本题中的数据),什么数据结构最为合适,为什么?若本题数据中所有的key都可以在byte的量级进行排序,例如有2个key,他们的排序根据他们第一个不同的byte进行排序。那对我们之前选择的数据结构有影响吗?若只有部分key可以又会怎么样? * 问题D:基于Java的思想,如何优化它在内存中的表示。为什么?
数据结构C语言顺序表的排序和删除问题
顺序表定义的长度为10000,此时程序可以正常运行;把顺序表长度改成500000,程序出错,不能运行。求问大神是哪里出了错误,还是要提高存储上限?如何改正?#include <stdio.h> #include <stdlib.h> #include <time.h> typedef int ElemType; #define MAX 10000 typedef struct{ ElemType *elem; int length; }SqList; void InitList(SqList &L){ L.elem = (ElemType *)malloc(MAX*sizeof(ElemType)); free(L.elem); L.elem = (ElemType *)malloc(MAX*sizeof(ElemType)); L.length = MAX; }//初始化顺序表 void Merge(ElemType SR[],ElemType TR[],int i,int m ,int n){ int j,k; for(j=m+1,k=i;i<=m&&j<=n;k++){ if(SR[i]<=SR[j]) TR[k]=SR[i++]; else TR[k] = SR[j++]; } while(i<=m) TR[k++] = SR[i++]; while(j<=n) TR[k++] = SR[j++]; }// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] void Msort( ElemType SR[], ElemType TR1[], int s, int t ){ int k; ElemType TR2[MAX]; if(s==t) TR1[s] = SR[s]; else { k = (s+t)/2; Msort(SR,TR2,s,k); Msort(SR,TR2,k+1,t); Merge(TR2,TR1,s,k,t); } }// 对SR[s..t]进行归并排序,排序后的记录存入TR1[s..t] void SelectSort(SqList &L){ int i,j,k; ElemType temp; int n=L.length; for(i=1;i<n;i++){ k = i; for(j=i+1;j<=n;j++) if(L.elem[j]<L.elem[k]) k=j; if(i!=k){ temp = L.elem[i]; L.elem[i] = L.elem[k]; L.elem[k] = temp; } } }//简单选择排序的实现 int QKPass(ElemType s[],int left,int right){ ElemType x = s[left]; while(left<right){ while(left<right && s[right]>=x){ right--; } if(left<right){ s[left] = s[right]; left++; } while(left<right && s[left]<=x){ left++; } if(left<right){ s[right] = s[left]; right--; } } s[left] = x; return left; }//一趟快速排序算法 void HeapAdjust (SqList &H, int s, int m){ H.elem[0] = H.elem[s]; int j; H.elem[0] = H.elem[s]; for(j = 2*s ; j<=m; j*=2){ if(j<m && H.elem[j]<H.elem[j+1]) j++; if(H.elem[0]>=H.elem[j]) break; H.elem[s] = H.elem[j]; s = j; } H.elem[s] = H.elem[0]; }//保存大顶堆的根元素后,对大顶堆的调整 void HeapSort (SqList &H){ int i ; ElemType temp; for(i=H.length/2;i>1;i--) HeapAdjust(H,i,H.length); temp = H.elem[0]; H.elem[0] = H.elem[H.length]; H.elem[H.length] = temp; for(i = H.length-1;i>1;i--){ HeapAdjust(H,1,i); temp = H.elem[1]; H.elem[1] = H.elem[i]; H.elem[i] = temp; } }//建立大顶堆,实现堆排序 void BubbleSort(SqList &L){ int n = L.length,change = 1; int i,j; ElemType temp; for(i=1;i<n && change;i++){ change = 0; for(j=1;j<=n-i;j++) if(L.elem[i]>L.elem[j]){ temp = L.elem[i]; L.elem[i] = L.elem[j]; L.elem[j] = temp; change = 1; } } }//冒泡排序算法实现 void QKsort(ElemType s[],int low,int high){ int pos; if(low<high){ pos = QKPass(s,low,high); QKsort(s,low,pos-1); QKsort(s,pos+1,high); } }//递归实现快序排序 void DeleteItem(SqList &L,ElemType item){ int i; for(i=1;i<L.length;i++) if(L.elem[i]==item){ L.elem[i] = L.elem[--L.length]; free(&L.elem[L.length]); } }//删除与item相同元素 int main(){ double t1,t2; int i; SqList L1,L2; int k; printf("**************************************\n"); printf("0、退出\n"); printf("1、二路归并排序\n"); printf("2、堆排序\n"); printf("3、冒泡排序\n"); printf("4、快速排序\n"); printf("5、直接插入排序\n"); printf("6、删除与Item相同元素\n"); printf("**************************************\n"); do{ InitList(L1); InitList(L2); scanf("%d",&k); for(i=1;i<L1.length;i++) L1.elem[i] = rand()%MAX; for(i=1;i<L2.length;i++) L2.elem[i]=i; switch(k){ case 0:break; case 1: printf("\n********二路归并排序******\n"); t1=clock(); Msort(L1.elem,L1.elem,1,L1.length-1); t1 = clock() - t1; t2=clock(); Msort(L2.elem,L2.elem,1,L2.length-1); t2 = clock()- t2; break; case 2: printf("\n**********堆排序*********\n"); t1=clock(); HeapSort(L1); t1 = clock() - t1; t2=clock(); HeapSort(L2); t2=clock() - t2; break; case 3: printf("\n*********冒泡排序********\n"); t1=clock(); BubbleSort(L1); t1 = clock() - t1; t2=clock(); BubbleSort(L2); t2=clock() - t2; break; case 4: printf("\n*********快速排序********\n"); t1=clock(); QKsort(L1.elem,1,L1.length-1); t1 = clock() - t1; t2=clock(); QKsort(L2.elem,1,L2.length-1); t2=clock() - t2; break; case 5: printf("\n********直接插入排序******\n"); t1=clock(); SelectSort(L1); t1 = clock() - t1; t2=clock(); SelectSort(L2); t2=clock() - t2; break; case 6: t1=clock(); DeleteItem(L1,5); t1=clock()-t1; for(i=1;i<L1.length;i++) printf("%d ",L1.elem[i]); break; default : printf("\n输入错误!\n\n"); } if(0<k&&k<6){ printf("\n该排序无序表排序时间:%f毫秒\n",(double)t1); printf("\n该排序有序表排序时间:%f毫秒\n\n",(double)t2); } else if(k==6) printf("\n删除元素的时间为%f毫秒\n",(double)t1); }while(k!=0); return 0; }
排序方法比较 具体看下面要求
对各种排序方法(直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序)的时间性能进行比较。 1)基本要求: (1) 设计并实现上述各种排序算法; (2) 产生正序和逆序的初始排列分别调用上述排序算法,并比较时间性能; (3) 产生随机的初始排列分别调用上述排序算法,并比较时间性能。
求教归并排序c++代码(有詳解)
如題,最好能够在注释中写明该步作用。 教练的代码太风骚,看不懂。
如何c++编程产生白盒测试数据,遍历插入排序,快速排序合并排序的每条分支语句,并输出便历结果
如题,想知道会用到什么库函数,该怎么编写语句,用什么算法,如果可以提供一段简单的源代码供参考
链表的二路归并 求大神发完整的代码!!不会写啊!
题目:设有n个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个元素, 头指针为r。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后r仍指示结果链表的第一个结点。
尝试数据结构中的mergesearch失败
最近在学数据结构和算法,想简单模拟一下向量的归并排序 ``` #include<iostream> using namespace std; class vector { int* num; public: vector(int *k) { num=k; } void mergesort(int,int); void merge(int,int,int); void display() { for(int i=0;i<10;i++) cout<<num[i]<<endl; } }; void vector::mergesort(int low,int high) { if(high-low<2)return; int mi=(low+high)/2; mergesort(low,mi); mergesort(mi,high); merge(low,mi,high); } void vector::merge(int low,int mi,int high) { int* A=num+low; int lenb=mi-low; int *B=new int[lenb]; for(int i=0;i<lenb;i++)B[i]=A[i]; int lenc=high-mi; int *C=num+mi; for(int i=0,j=0,k=0;(j<lenb)||(k<lenc);) { if((j<lenb)&&(lenc<=k||(B[j]<=C[k])))A[i++]=B[j++]; if((k<lenc)&&(lenb<=j||(C[k]<B[j])))A[i++]=C[k++]; } delete[]B; } int main() { int *k; for(int i=0;i<10;i++) cin>>k[i]; cout<<"一开始"<<endl; for(int i=0;i<10;i++) cout<<" "<<k[i]; cout<<endl; vector v(k); v.mergesort(0,10); v.display(); } ``` ![图片说明](https://img-ask.csdn.net/upload/202003/24/1585040124_518724.png) 出现了一些错误
如何编写一段c++测试代码
如题,我是一位初学者,现有一道题如下: 编一段代码,分别实现插入排序,合并排序和快速排序的算法。然后编写测试代码,设计测试数据集,编写测试程序,测试正确性、算法复杂性和效率。 题目中注明检测正确性的测试程序应该输出一个遍历结果,保证所有分支语句都检测到。不太理解这是要我做什么……以及比较算法复杂性、效率,是需我明确地输出花费时间吗? 希望有大神可以在测试代码这方面指点迷津,谢谢!
c++的单链表合并,析构出现问题
#include<iostream> #include<algorithm> #include<assert.h> using namespace std; template<class ElemType> struct Node { //数据成员 ElemType data; //数据域 Node<ElemType> *next; //指针域 //构造函数 Node(); //无参数的构造函数 Node(ElemType e, Node<ElemType> *Link = NULL); //有参数的构造函数 }; template<class ElemType> Node<ElemType>::Node() { next = NULL; } template<class ElemType> Node<ElemType>::Node(ElemType e, Node<ElemType> *link) { data = e; next = link; } //单链表 template<class ElemType> class LinkList { protected: //单链表类模板的数据成员 Node<ElemType> *head; //头指针结点 int length; //元素个数 public: //单链表类模板的函数成员 LinkList(); //无参数构造函数 LinkList(ElemType v[], int n); //有参数的构造函数 virtual ~LinkList(); //析构函数 int GetLength()const; //求链表长度 bool IsEmpty()const; //判断链表是否为空 void Clear(); //将链表清空 void UseMerge(LinkList<ElemType>p1, LinkList<ElemType>p2); Node<ElemType>* merge(Node<ElemType> *head1, Node<ElemType> *head2); //合并 void output(); //将链表输出 }; //无参数的构造函数 template<class ElemType> LinkList<ElemType>::LinkList() { head = new Node<ElemType>; //构造头函数 length = 0; //单链表长度定为0; } //有参数构造函数 template<class ElemType> LinkList<ElemType>::LinkList(ElemType v[], int n) { //排序 for (int i = 0; i < n; i++) { for (int j = 1; j < n - i; j++) { if (v[j] < v[j - 1]) swap(v[j], v[j - 1]); } } Node<ElemType> *p; p = head = new Node<ElemType>; //构造头结点 for (int i = 0; i < n; i++) { p->next = new Node<ElemType>(v[i], NULL); assert(p->next); //构造元素结点失败,终止程序运行 p = p->next; } length = n; } //析构函数 template<class ElemType> LinkList<ElemType>::~LinkList() { Clear(); //清空链表 delete head; //释放头结点所指空间 } //清空链表 template<class ElemType> void LinkList<ElemType>::Clear() { Node<ElemType> *p; p = head->next; while (p != NULL) { cout << p->data; head->next = p->next; delete p; p = head->next; } length = 0; } //求链表长度 template<class ElemType> int LinkList<ElemType>::GetLength()const { return length; } //判断链表是否为空 template<class ElemType> bool LinkList<ElemType>::IsEmpty()const { Node<ElemType> *p = head->next; if (p != NULL) return false; return true; } //调用合并 template<class ElemType> void LinkList<ElemType>::UseMerge(LinkList<ElemType>p1, LinkList<ElemType>p2) { head->next = merge(p1.head->next, p2.head->next); } //合并链表 template<class ElemType> Node<ElemType>* LinkList<ElemType>::merge(Node<ElemType> *head1, Node<ElemType> *head2) { if (head1 == NULL) return head2; if (head2 == NULL) return head1; Node <ElemType> *head = NULL; if (head1->data < head2->data) { head = head1; head->next = merge(head1->next, head2); } else { head = head2; head->next = merge(head1, head2->next); } cout << "e"; return head; } //输出链表 template<class ElemType> void LinkList<ElemType>::output() { Node<ElemType> *p; p = head->next; while (p != NULL) { cout << p->data << ","; p = p->next; } } void main() { cout << "输入第一组五个整数:"; int v1[1]; for (int i = 0; i < 1; i++) cin >> v1[i]; cout<<"\n"; LinkList<int> p1(v1, 1); cout << "输出有序单链表应为:"; p1.output(); cout << "\n"; cout << "输入第二组五个整数:"; int v2[1]; for (int i = 0; i < 1; i++) cin >> v2[i]; cout << "\n"; LinkList<int> p2(v2, 0); cout << "输出有序单链表应为:"; p2.output(); cout << "\n"; LinkList<int> p; p.UseMerge(p1, p2); cout << "合并两个单链表,合并后输出结果应为:"; p.output(); system("pause"); } ``` ``` 析构出现问题
递归调用循环的非递归形式
背景:之前在算法书上看到说所有的递归算法都可以写成非递归的形式。 那么遍历一个完全树的所有叶子节点,我看过两个算法,一个是递归调用,非常简单。 还有一个使用了队列:(c++ 和伪代码的混合表示) queue.push(root);//根节点进队 while (!queue.isEmpty()) { queue.push(root->left); queue.push(root->right); if (!queue.top()->hasChild()) { print queue.top()->data; } queue.pop(); } 上面的算是非递归形式。 不过我想问的是,是不是说一定需要队列或者堆栈这样的辅助数据结构才能解决该问题? 因为我觉得之前的一些递归算法改成的非递归算法都没有用到什么数据结构。 比如合并排序的非递归形式。用到的仅仅是两个向量而已。 我一直认为递归算法改成非递归形式是有一定的模板可循的。如果辅助数据结构不可避免,是不是意味着所有的递归算法只是理论上可以写成递归形式,至于写不写的出来,还要看个人的数据结构水平?
编程:假设一个班的成绩交给M个人去输入,每个人随机从班级中抽出若干名学生信息进行输入
假设一个班的成绩交给M个人去输入,每个人随机从班级中抽出若干名学生信息进行输入, 每个人输入完后放在M个文件中, 每个人输入的成绩都按学号排好序的 学生成绩信息文件1(1.txt),例如: 姓名 性别 学号 语文 数学 英语 张明明 男 01 67 78 82 张辉灿 男 03 68 82 56 陈东明 男 05 67 38 47 李成友 男 32 78 91 88 王露 女 34 56 45 77 …. .. .. .. … 学生成绩信息文件2(2.txt), 例如: 姓名 性别 学号 语文 数学 英语 李华明 男 02 88 90 68 李明国 男 04 50 45 87 陈果 女 31 57 68 82 张明东 男33 48 42 56 陈道亮 男35 47 58 77 …. .. .. .. … 一共M个文件 1) 现在编程实现将M个文件的成绩合并一个文件,并且仍按学号有序的(total.txt) 提示,可以用合并排序 2) 从原文件(不是合并后文件)中抽出三科成绩中有补考的学生(只要有一门不及格,整个学生的信息都要抽出),并保存在一个新文件中,新文件不需要按学号有序(bk.txt) 3) 对补考文件(bk.txt) 中的数据按学号排序,保存在一个新文件bksort.txt (至少采用两种排序方法实现)中,并按各科打印出补考学生名单 4) 对于新文件(total.txt),读入内存,输入一个学生学号后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现) 5). 对于新文件(total.txt),读入内存,分男生和女生分别到存到两个文件中(boy.txt,girl.txt) 要求男生和女生分别按学号有序 6). 对于新文件(total.txt),读入内存,按总分排序,放入到(scoresort.txt)中 规定: 学生信息要求使用结构体,采用顺序表实现上述要求,上述6个功能的程序分开编写,最后能够合在一起运行。每个功能可以设立菜单。 采用多种方法且算法正确者,可适当加分。 (数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决,文件读写功能要写成通用函数, 上述6个功能直接调用)
我这样是否对同一个对象进行了排序(小猿一只,评论勿留情)
import java.util.Random; public class MergeSort implements Runnable{ public void run() { int[] a = new int[100000]; Random p = new Random(); //产生随机数 for(int i=0;i<100000;i++) a[i] = p.nextInt(10000); //计时 //long startMili=System.currentTimeMillis();// 当前时间对应的毫秒数 //System.out.println("总耗时为:"+(startMili)+"毫秒"); mergeSort(a, 0, 1); //long endMili=System.currentTimeMillis(); //System.out.println("总耗时为:"+(endMili)+"毫秒"); //System.out.println("\n总耗时为:"+(endMili-startMili)+"毫秒"); } // private static long sum = 0; /** * <pre> * 二路归并 * 原理:将两个有序表合并和一个有序表 * </pre> * * @param a * @param s * 第一个有序表的起始下标 * @param m * 第二个有序表的起始下标 * @param t * 第二个有序表的结束下标 * */ private static void merge(int[] a, int s, int m, int t) { int[] tmp = new int[t - s + 1]; int i = s, j = m, k = 0; while (i < m && j <= t) { if (a[i] <= a[j]) { tmp[k] = a[i]; k++; i++; } else { tmp[k] = a[j]; // sum += (j - i) - (j - m); j++; k++; } } while (i < m) { tmp[k] = a[i]; i++; k++; } while (j <= t) { tmp[k] = a[j]; j++; k++; } System.arraycopy(tmp, 0, a, s, tmp.length); } /** * * @param a * @param s * @param len * 每次归并的有序集合的长度 */ public static void mergeSort(int[] a, int s, int len) { int size = a.length; int mid = size / (len << 1); int c = size & ((len<<1) - 1); // -------归并到只剩一个有序集合的时候结束算法-------// if (mid == 0) return; // ------进行一趟归并排序-------// for (int i = 0; i < mid; ++i) { s = i * 2 * len; merge(a, s, s + len, (len << 1) + s - 1); } // -------将剩下的数和倒数一个有序集合归并-------// if (c != 0) merge(a, size - c - 2 * len, size - c, size - 1); // // for (int i = 0; i < a.length; ++i) { // System.out.print(a[i] + " "); // } // System.out.println(); // -------递归执行下一趟归并排序------// mergeSort(a, 0, 2 * len); } public static void main(String[] args) throws InterruptedException { Thread m = new Thread(new MergeSort()); Thread m1 = new Thread(m); Thread m2 = new Thread(m); Thread m3 = new Thread(m); Thread m4 = new Thread(m); Thread m5 = new Thread(m); //计时 long startMili1=System.currentTimeMillis();// 当前时间对应的毫秒数 System.out.println("总耗时为:"+(startMili1)+"毫秒"); m1.start(); m1.join(); long endMili1=System.currentTimeMillis(); System.out.println("总耗时为:"+(endMili1)+"毫秒"); System.out.println("总耗时为:"+(endMili1-startMili1)+"毫秒\n"); long startMili2=System.currentTimeMillis();// 当前时间对应的毫秒数 System.out.println("总耗时为:"+(startMili2)+"毫秒"); m2.start(); //m2.join(); m3.start(); //m3.join(); m4.start(); //m4.join(); m5.start(); //m5.join(); long endMili2=System.currentTimeMillis(); System.out.println("总耗时为:"+(endMili2)+"毫秒"); System.out.println("总耗时为:"+(endMili2-startMili2)+"毫秒"); } }
这道编程题为什么会是答案错误?
已知线性表 LA 和 LB 中的数据元素按值非递减有序排列,现要求将 LA 和 LB 归并为一个新的线性表 LC, 且 LC 中的数据元素仍然按值非递减有序排列。例如,设LA=(3,5,8,11) ,LB=(2,6,8,9,11,15,20) 则 LC=(2,3,6,6,8,8,9,11,11,15,20) 算法描述如下: 从上述问题要求可知,LC中的数据元素或是LA中的数据元素,或是LB中的数据元素,则只要先设LC为空表,然后将LA或LB中的元素逐个插入到LC中即可。为使LC中元素按值非递减有序排列,可设两个指针 i 和 j 分别指向LA和LB中某个元素,若设 i 当前所指的元素为 a,j 所指的元素为 b,则当前应插入到 LC 中的元素 c 为 c = a < b ? a : b显然,指针 i 和 j 的初值均为1(实际写代码时往往是从 0 开始的),在所指元素插入 LC 之后,在 LA 或者 LB 中顺序后移。上述归并算法如下图: ![图片说明](https://img-ask.csdn.net/upload/201505/26/1432571130_850496.jpg) 图:有序列表有序插入算法 输入 有多组测试数据,每组测试数据占两行。第一行是集合A,第一个整数m(0<=m<=100)代表集合A起始有m个元素,后面有m个非递减排序的整数,代表A中的元素。第二行是集合B,第一个整数n(0<=n<=100)代表集合B起始有n个元素,后面有n个非递减排序的整数,代表B中的元素。每行中整数之间用一个空格隔开。 输出 每组测试数据只要求输出一行,这一行含有 m+n 个来自集合 A 和集合B 中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。 样例输入 4 3 5 8 11 7 2 6 8 9 11 15 20 样例输出 2 3 5 6 8 8 9 11 11 15 20 我的代码如下: ``` #include<stdlib.h> void Merglist(int a[],int b[],int c[],int m,int n){ int i,j,k; i=0;j=0;k=0; while(i<m&&j<n){ if(a[i]<=b[j]){ c[k++]=a[i]; ++i; } else{ c[k++]=b[j]; ++j; } } while(i<m){ c[k++]=a[i]; i++; } while(j<n){ c[k++]=b[j]; j++; } } int main(){ int a[100]; int b[100]; int c[200]; int i,j,n,m; scanf("%d",&m); for(i=0;i<m;i++){ scanf("%d",&a[i]); } scanf("%*c"); scanf("%d",&n); for(j=0;j<n;j++){ scanf("%d",&b[j]); } Merglist(a,b,c,m,n); for(i=0;i<m+n;i++){ if(i==0){ printf("%d",c[i]); }else printf(" %d",c[i]); } return 0; } ``` 求大神指点!在codeblocks中,范例可以通过,但是提交后,告诉我答案错误,找不到原因。求帮助
cnt变量的值为什么会无故变动?
(新手学习中)以下是一个关于归并排序的函数。一开始cnt初始化为0(本来应该是plo),然后奇怪的事发生了:在调试时cnt的值开始随意的变化(以下各图均是运行一步的结果)。求大神解答原因。![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531289_360990.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531294_754598.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531423_198911.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531428_889320.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531435_426713.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531444_869118.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531329_54318.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531335_102314.png)![图片说明](https://img-ask.csdn.net/upload/201608/18/1471531462_947493.png)
使用MFSet集合及克鲁斯卡尔算法实现最小生成树,但是最后结果总不对,求大神指教!
#include "stdafx.h" #include "stdafx.h" #include<stdio.h> #include<stdlib.h> #define MAX_SIZE 100 //树的最大结点数 #define MAX_VEX_NUM 20 //最大顶点数 #define MAX_EDGE_NUM 190 //最大边数 //边集 typedef struct { char begin; char end; int weight; }Edge; //图结构 typedef struct{ Edge edge[MAX_EDGE_NUM]; char vex[MAX_VEX_NUM]; int vexnum,edgenum; }Graph; //树的节点结构 typedef struct Node{ char data; int parent; }Node; //树的双亲表示存储结构 typedef struct{ Node node[MAX_SIZE]; int n; //结点数 }PTree,MFSet; //初始化MFSet集合 void initMFSet(MFSet *S,Graph G){ if(!S) exit(0); for(int i=0;i<G.vexnum;i++){ S->node[i].data=G.vex[i]; S->node[i].parent=-1; } S->n=G.vexnum; } int find_mfset(MFSet S,int i){ if(i<0||i>S.n) exit(0); int j; for(j=i;S.node[j].parent>0;j=S.node[j].parent); return j; } //合并 void merge(MFSet *S,int i,int j){ if(i<0||i>S->n||j<0||j>S->n) exit(0); S->node[j].parent=i; } //创建无向网 void creatGraph(Graph *G){ printf("请输入定点元素个数以及边数:"); scanf("%d,%d",&G->vexnum,&G->edgenum); if(G->edgenum>MAX_EDGE_NUM||G->vexnum>MAX_VEX_NUM){ printf("输入错误,请重新输入:"); scanf("%d,%d",&G->vexnum,&G->edgenum); } printf("请输入各个定点信息:\n"); for(int i=0;i<G->vexnum;i++){ fflush(stdin); scanf("%c",&G->vex[i]); } printf("请输入每条边的两个定点和权值:\n"); for(int i=0;i<G->edgenum/2;i++){ fflush(stdin); scanf("%c,%c,%d",&G->edge[i].begin,&G->edge[i].end,&G->edge[i].weight); // G->edge[i].weight = rand()%100; } for(int i=G->edgenum/2;i<G->edgenum;i++){ G->edge[i].begin=G->edge[i-G->edgenum/2].end; G->edge[i].end=G->edge[i-G->edgenum/2].begin; G->edge[i].weight=G->edge[i-G->edgenum/2].weight; } } //找到网中某一结点元素在顶点数组中的位置 int vexLocate(Graph G,char c){ for(int i=0;i<G.vexnum;i++){ if(c==G.vex[i]) return i; } return -1; } void minSpanTree(Graph *G){ int parent[MAX_VEX_NUM]; int m,n,temp; char a,b; for(int i=0;i<G->vexnum;i++){ parent[i]=0; } MFSet S; initMFSet(&S,*G); //使用冒泡排序法将边集的权值按从小到大排序 for(int i=0;i<G->edgenum;i++){ for(int j=0;j<G->edgenum-i-1;j++){ if(G->edge[j].weight>G->edge[j+1].weight){ a=G->edge[j].begin; b=G->edge[j].end; temp=G->edge[j].weight; G->edge[j].begin=G->edge[j+1].begin; G->edge[j].end=G->edge[j+1].end; G->edge[j].weight=G->edge[j+1].weight; G->edge[j+1].begin=a; G->edge[j+1].end=b; G->edge[j+1].weight=temp; } } } for(int i=0;i<G->edgenum;i++){ m=find_mfset(S,vexLocate(*G,G->edge[i].begin)); n=find_mfset(S,vexLocate(*G,G->edge[i].end)); if(m!=n){ //说明没有形成回路 merge(&S,m,n); printf("<%c,%c>,%d\t",G->edge[i].begin,G->edge[i].end,G->edge[i].weight); } } } int _tmain(int argc, _TCHAR* argv[]) { Graph G; creatGraph(&G); minSpanTree(&G); system("pause"); return 0; }
大学四年自学走来,这些私藏的实用工具/学习网站我贡献出来了
大学四年,看课本是不可能一直看课本的了,对于学习,特别是自学,善于搜索网上的一些资源来辅助,还是非常有必要的,下面我就把这几年私藏的各种资源,网站贡献出来给你们。主要有:电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意:文中提到的所有资源,文末我都给你整理好了,你们只管拿去,如果觉得不错,转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...
【JSON解析】浅谈JSONObject的使用
简介 在程序开发过程中,在参数传递,函数返回值等方面,越来越多的使用JSON。JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,同时也易于机器解析和生成、易于理解、阅读和撰写,而且Json采用完全独立于语言的文本格式,这使得Json成为理想的数据交换语言。 JSON建构于两种结构: “名称/值”对的集合(A Collection of name/va...
程序员请照顾好自己,周末病魔差点一套带走我。
程序员在一个周末的时间,得了重病,差点当场去世,还好及时挽救回来了。
卸载 x 雷某度!GitHub 标星 1.5w+,从此我只用这款全能高速下载工具!
作者 | Rocky0429 来源 | Python空间 大家好,我是 Rocky0429,一个喜欢在网上收集各种资源的蒟蒻… 网上资源眼花缭乱,下载的方式也同样千奇百怪,比如 BT 下载,磁力链接,网盘资源等等等等,下个资源可真不容易,不一样的方式要用不同的下载软件,因此某比较有名的 x 雷和某度网盘成了我经常使用的工具。 作为一个没有钱的穷鬼,某度网盘几十 kb 的下载速度让我...
只因接了一个电话,程序员被骗 30 万!
今天想给大家说一个刚刚发生在我身边的一起真实的诈骗经历,我的朋友因此被骗走30万。注:为了保护当事人隐私,部分情节进行了修改。1平安夜突来的电话开始以为就像普通的诈骗一样,想办法让你把钱...
我一个37岁的程序员朋友
周末了,人一旦没有点事情干,心里就瞎想,而且跟几个老男人坐在一起,更容易瞎想,我自己现在也是 30 岁了,也是无时无刻在担心自己的职业生涯,担心丢掉工作没有收入,担心身体机能下降,担心突...
python自动下载图片
近日闲来无事,总有一种无形的力量萦绕在朕身边,让朕精神涣散,昏昏欲睡。 可是,像朕这么有职业操守的社畜怎么能在上班期间睡瞌睡呢,我不禁陷入了沉思。。。。 突然旁边的IOS同事问:‘嘿,兄弟,我发现一个网站的图片很有意思啊,能不能帮我保存下来提升我的开发灵感?’ 作为一个坚强的社畜怎么能说自己不行呢,当时朕就不假思索的答应:‘oh, It’s simple. Wait for me for a ...
一名大专同学的四个问题
【前言】   收到一封来信,赶上各种事情拖了几日,利用今天要放下工作的时机,做个回复。   2020年到了,就以这一封信,作为开年标志吧。 【正文】   您好,我是一名现在有很多困惑的大二学生。有一些问题想要向您请教。   先说一下我的基本情况,高考失利,不想复读,来到广州一所大专读计算机应用技术专业。学校是偏艺术类的,计算机专业没有实验室更不用说工作室了。而且学校的学风也不好。但我很想在计算机领...
复习一周,京东+百度一面,不小心都拿了Offer
京东和百度一面都问了啥,面试官百般刁难,可惜我全会。
Java 14 都快来了,为什么还有这么多人固守Java 8?
从Java 9开始,Java版本的发布就让人眼花缭乱了。每隔6个月,都会冒出一个新版本出来,Java 10 , Java 11, Java 12, Java 13, 到2020年3月份,...
达摩院十大科技趋势发布:2020 非同小可!
【CSDN编者按】1月2日,阿里巴巴发布《达摩院2020十大科技趋势》,十大科技趋势分别是:人工智能从感知智能向认知智能演进;计算存储一体化突破AI算力瓶颈;工业互联网的超融合;机器间大规模协作成为可能;模块化降低芯片设计门槛;规模化生产级区块链应用将走入大众;量子计算进入攻坚期;新材料推动半导体器件革新;保护数据隐私的AI技术将加速落地;云成为IT技术创新的中心 。 新的画卷,正在徐徐展开。...
轻松搭建基于 SpringBoot + Vue 的 Web 商城应用
首先介绍下在本文出现的几个比较重要的概念: 函数计算(Function Compute): 函数计算是一个事件驱动的服务,通过函数计算,用户无需管理服务器等运行情况,只需编写代码并上传。函数计算准备计算资源,并以弹性伸缩的方式运行用户代码,而用户只需根据实际代码运行所消耗的资源进行付费。Fun: Fun 是一个用于支持 Serverless 应用部署的工具,能帮助您便捷地管理函数计算、API ...
讲真,这两个IDE插件,可以让你写出质量杠杠的代码
周末躺在床上看《拯救大兵瑞恩》 周末在闲逛的时候,发现了两个优秀的 IDE 插件,据说可以提高代码的质量,我就安装了一下,试了试以后发现,确实很不错,就推荐给大家。 01、Alibaba Java 代码规范插件 《阿里巴巴 Java 开发手册》,相信大家都不会感到陌生,其 IDEA 插件的下载次数据说达到了 80 万次,我今天又贡献了一次。嘿嘿。 该项目的插件地址: https://github....
Python+OpenCV实时图像处理
目录 1、导入库文件 2、设计GUI 3、调用摄像头 4、实时图像处理 4.1、阈值二值化 4.2、边缘检测 4.3、轮廓检测 4.4、高斯滤波 4.5、色彩转换 4.6、调节对比度 5、退出系统 初学OpenCV图像处理的小伙伴肯定对什么高斯函数、滤波处理、阈值二值化等特性非常头疼,这里给各位分享一个小项目,可通过摄像头实时动态查看各类图像处理的特点,也可对各位调参、测试...
2020年一线城市程序员工资大调查
人才需求 一线城市共发布岗位38115个,招聘120827人。 其中 beijing 22805 guangzhou 25081 shanghai 39614 shenzhen 33327 工资分布 2020年中国一线城市程序员的平均工资为16285元,工资中位数为14583元,其中95%的人的工资位于5000到20000元之间。 和往年数据比较: yea...
为什么猝死的都是程序员,基本上不见产品经理猝死呢?
相信大家时不时听到程序员猝死的消息,但是基本上听不到产品经理猝死的消息,这是为什么呢? 我们先百度搜一下:程序员猝死,出现将近700多万条搜索结果: 搜索一下:产品经理猝死,只有400万条的搜索结果,从搜索结果数量上来看,程序员猝死的搜索结果就比产品经理猝死的搜索结果高了一倍,而且从下图可以看到,首页里面的五条搜索结果,其实只有两条才是符合条件。 所以程序员猝死的概率真的比产品经理大,并不是错...
害怕面试被问HashMap?这一篇就搞定了!
声明:本文以jdk1.8为主! 搞定HashMap 作为一个Java从业者,面试的时候肯定会被问到过HashMap,因为对于HashMap来说,可以说是Java集合中的精髓了,如果你觉得自己对它掌握的还不够好,我想今天这篇文章会非常适合你,至少,看了今天这篇文章,以后不怕面试被问HashMap了 其实在我学习HashMap的过程中,我个人觉得HashMap还是挺复杂的,如果真的想把它搞得明明白...
毕业5年,我问遍了身边的大佬,总结了他们的学习方法
我问了身边10个大佬,总结了他们的学习方法,原来成功都是有迹可循的。
python爬取百部电影数据,我分析出了一个残酷的真相
2019年就这么匆匆过去了,就在前几天国家电影局发布了2019年中国电影市场数据,数据显示去年总票房为642.66亿元,同比增长5.4%;国产电影总票房411.75亿元,同比增长8.65%,市场占比 64.07%;城市院线观影人次17.27亿,同比增长0.64%。 看上去似乎是一片大好对不对?不过作为一名严谨求实的数据分析师,我从官方数据中看出了一点端倪:国产票房增幅都已经高达8.65%了,为什...
推荐10个堪称神器的学习网站
每天都会收到很多读者的私信,问我:“二哥,有什么推荐的学习网站吗?最近很浮躁,手头的一些网站都看烦了,想看看二哥这里有什么新鲜货。” 今天一早做了个恶梦,梦到被老板辞退了。虽然说在我们公司,只有我辞退老板的份,没有老板辞退我这一说,但是还是被吓得 4 点多都起来了。(主要是因为我掌握着公司所有的核心源码,哈哈哈) 既然 4 点多起来,就得好好利用起来。于是我就挑选了 10 个堪称神器的学习网站,推...
这些软件太强了,Windows必装!尤其程序员!
Windows可谓是大多数人的生产力工具,集娱乐办公于一体,虽然在程序员这个群体中都说苹果是信仰,但是大部分不都是从Windows过来的,而且现在依然有很多的程序员用Windows。 所以,今天我就把我私藏的Windows必装的软件分享给大家,如果有一个你没有用过甚至没有听过,那你就赚了????,这可都是提升你幸福感的高效率生产力工具哦! 走起!???? NO、1 ScreenToGif 屏幕,摄像头和白板...
阿里面试,面试官没想到一个ArrayList,我都能跟他扯半小时
我是真的没想到,面试官会这样问我ArrayList。
曾经优秀的人,怎么就突然不优秀了。
职场上有很多辛酸事,很多合伙人出局的故事,很多技术骨干被裁员的故事。说来模板都类似,曾经是名校毕业,曾经是优秀员工,曾经被领导表扬,曾经业绩突出,然而突然有一天,因为种种原因,被裁员了,...
大学四年因为知道了这32个网站,我成了别人眼中的大神!
依稀记得,毕业那天,我们导员发给我毕业证的时候对我说“你可是咱们系的风云人物啊”,哎呀,别提当时多开心啦????,嗯,我们导员是所有导员中最帅的一个,真的???? 不过,导员说的是实话,很多人都叫我大神的,为啥,因为我知道这32个网站啊,你说强不强????,这次是绝对的干货,看好啦,走起来! PS:每个网站都是学计算机混互联网必须知道的,真的牛杯,我就不过多介绍了,大家自行探索,觉得没用的,尽管留言吐槽吧???? 社...
良心推荐,我珍藏的一些Chrome插件
上次搬家的时候,发了一个朋友圈,附带的照片中不小心暴露了自己的 Chrome 浏览器插件之多,于是就有小伙伴评论说分享一下我觉得还不错的浏览器插件。 我下面就把我日常工作和学习中经常用到的一些 Chrome 浏览器插件分享给大家,随便一个都能提高你的“生活品质”和工作效率。 Markdown Here Markdown Here 可以让你更愉快的写邮件,由于支持 Markdown 直接转电子邮...
【程序人生】程序员接私活常用平台汇总
00. 目录 文章目录00. 目录01. 前言02. 程序员客栈03. 码市04. 猪八戒网05. 开源众包06. 智城外包网07. 实现网08. 猿急送09. 人人开发10. 开发邦11. 电鸭社区12. 快码13. 英选14. Upwork15. Freelancer16. Dribbble17. Remoteok18. Toptal19. AngelList20. Topcoder21. ...
看完这篇HTTP,跟面试官扯皮就没问题了
我是一名程序员,我的主要编程语言是 Java,我更是一名 Web 开发人员,所以我必须要了解 HTTP,所以本篇文章就来带你从 HTTP 入门到进阶,看完让你有一种恍然大悟、醍醐灌顶的感觉。 最初在有网络之前,我们的电脑都是单机的,单机系统是孤立的,我还记得 05 年前那会儿家里有个电脑,想打电脑游戏还得两个人在一个电脑上玩儿,及其不方便。我就想为什么家里人不让上网,我的同学 xxx 家里有网,每...
史上最全的IDEA快捷键总结
现在Idea成了主流开发工具,这篇博客对其使用的快捷键做了总结,希望对大家的开发工作有所帮助。
阿里程序员写了一个新手都写不出的低级bug,被骂惨了。
这种新手都不会范的错,居然被一个工作好几年的小伙子写出来,差点被当场开除了。
谁是华为扫地僧?
是的,华为也有扫地僧!2020年2月11-12日,“养在深闺人不知”的华为2012实验室扫地僧们,将在华为开发者大会2020(Cloud)上,和大家见面。到时,你可以和扫地僧们,吃一个洋...
立即提问