问题A 二路归并排序(mergeSort)递归法
题目大意
就是最基础的递归二路归并排序的算法思想。
注意
这题测试结果Runtime Error80就是正确的。
//
// main.cpp
// 二路归并排序（mergesort）递归法
//
// Created by JustforStar on 2020/7/25.
// Copyright ? 2020 JustforStar. All rights reserved.
//
#include<stdio.h>
#include <iostream>
#define MAXN 100001
using namespace std;
int a[MAXN];
int n;void merge(int A[],int l1,int r1,int l2,int r2){int i=l1,j=l2;int temp[MAXN],index=0;while(i<=r1&&j<=r2){if(A[i]<=A[j]){temp[index++]=A[i++];}else{temp[index++]=A[j++];}}while(i<=r1)temp[index++]=A[i++];while(j<=r2)temp[index++]=A[j++];for(i=0;i<index;i++)A[l1+i]=temp[i];
}void mergeSort(int A[],int left,int right){if(left<right){int mid=(left+right)/2;mergeSort(A, left, mid);mergeSort(A, mid+1, right);merge(A,left,mid,mid+1,right);}
}int main(int argc, const char * argv[]) {// insert code here...scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);mergeSort(a, 0, n-1);for(int i=0;i<n;i++)printf("%d\n",a[i]);return 0;
}
问题B 基础排序III 归并排序
题目大意
同问题A，唯一的区别在于问题B是明确要求多点测试。
//
// main.cpp
// Codeup-归并排序
//
// Created by JustforStar on 2020/7/25.
// Copyright ? 2020 JustforStar. All rights reserved.
//#include<stdio.h>
#include <iostream>
#define MAXN 100001
using namespace std;
int a[MAXN];
int n,m;void merge(int A[],int l1,int r1,int l2,int r2){int i=l1,j=l2;int temp[MAXN],index=0;while(i<=r1&&j<=r2){if(A[i]<=A[j]){temp[index++]=A[i++];}else{temp[index++]=A[j++];}}while(i<=r1)temp[index++]=A[i++];while(j<=r2)temp[index++]=A[j++];for(i=0;i<index;i++)A[l1+i]=temp[i];
}void mergeSort(int A[],int left,int right){if(left<right){int mid=(left+right)/2;mergeSort(A, left, mid);mergeSort(A, mid+1, right);merge(A,left,mid,mid+1,right);}
}int main(int argc, const char * argv[]) {// insert code here...scanf("%d",&m);while(m--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);mergeSort(a, 0, n-1);for(int i=0;i<n;i++)printf("%d\n",a[i]);}return 0;
}
问题C 快速排序qsort
问题D 二分递归快排（Qsort）
题目大意
最基本的快速排序的思想
//
// main.cpp
// Codeup-快速排序
//
// Created by JustforStar on 2020/7/25.
// Copyright ? 2020 JustforStar. All rights reserved.
//#include <iostream>
#include<stdio.h>
#define MAXN 5001
using namespace std;int n;
int a[MAXN];int Partition(int A[],int left,int right){int temp=A[left];while(left<right){while(left<right&&A[right]>temp)right--;A[left]=A[right];while(left<right&&A[left]<=temp)left++;A[right]=A[left];}A[left]=temp;return left;
}void quickSort(int A[],int left,int right){if(left<right){int pos=Partition(A, left, right);quickSort(A, left, pos-1);quickSort(A, pos+1, right);}
}int main(int argc, const char * argv[]) {scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);quickSort(a, 0, n-1);for(int i=0;i<n;i++)printf("%d\n",a[i]);return 0;
}