#include<iostream> #include<string> #include<sstream> #include<stdlib.h> using namespace std; int a[100005],n=0,i; void mergeSort(int,int); int main(){ string in,x; //freopen("input.txt","r",stdin); getline(cin,in); stringstream ss(in); while(ss>>x){ int dig=0,i,flag=0; for(i=0;i<x.length();i++) if('0'<=x[i]&&x[i]<='9') dig=dig*10+(x[i]-'0'); else if(x[i]=='-') flag=1; a[n++]=(flag?-dig:dig); } mergeSort(0,n-1); for(printf("["),i=0;i<n;i++) printf("%d%s",a[i],i==n-1?"]":", "); } void mergeSort(int l,int r){ if(l>=r) return; int mid=l+(r-l)/2; mergeSort(l,mid),mergeSort(mid+1,r); int *tmp=(int *)malloc(sizeof(int)*(r-l+1)),c=0,i,j; for(i=l,j=mid+1;i<=mid||j<=r;) if(i>mid||j<=r&&a[i]>a[j]) tmp[c++]=a[j++]; else tmp[c++]=a[i++]; for(i=0,j=l;i<c;i++) a[j++]=tmp[i]; }
public static void sort(int[] arr, int left, int right) { if (left < right) { // 中间值 int mid = (left + right) / 2; // 左边到中值排序并合并 sort(arr, left, mid); // 中值到右边排序并合并 sort(arr, mid + 1, right); // 左边和右边合并, 每个递归过程结束,弹栈后左边和右边都会内部有序 // 左数组长度 int leftLen = mid - left + 1; // 右数组长度 int rightLen = right - mid; // 左数组 int[] leftArr = new int[leftLen]; // 右数组 int[] rightArr = new int[rightLen]; // 装载左边数组,(已排序合并完成) for (int i = 0; i < leftLen; ++i) leftArr[i] = arr[left + i]; // 装载右边数组,(已排序合并完成) for (int j = 0; j < rightLen; ++j) rightArr[j] = arr[mid + 1 + j]; // 进行最小值比较并合并到 arr 指定位置 int i = 0, j = 0, k = left; while (i < leftLen && j < rightLen) { if (leftArr[i] <= rightArr[j]) { arr[k] = leftArr[i]; i++; } else { arr[k] = rightArr[j]; j++; } k++; } // 比较合并完成,左边数组有剩余,剩余部分填充到 arr while (i < leftLen) { arr[k] = leftArr[i]; i++; k++; } // 比较合并完成,右边数组有剩余,剩余部分填充到 arr while (j < rightLen) { arr[k] = rightArr[j]; j++; k++; } } }
package MergeSortDemo; import java.util.Arrays; import java.util.Scanner; public class MergeSortDemo { public static void main(String args[]){ Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; int[] tmp = new int[n]; for(int i = 0 ; i < n ; i++){ arr[i] = scanner.nextInt(); } mergeSort(arr, 0 , arr.length-1 , tmp); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[] arr , int left , int right , int[] tmp){ if(left < right){ int mid = (left + right) / 2; mergeSort(arr , left , mid , tmp); mergeSort(arr ,mid + 1 , right , tmp); merge(arr,left,mid,right,tmp); } } public static void merge(int[] arr , int left , int mid , int right,int[] tmp){ // 初始化i, 左边有序序列的头部初始索引 int i = left; // 初始化j, 右边有序序列的头部初始索引, mid + 1 int j = mid + 1; // 指向中转数组 temp 的当前索引 int t = 0; // 1. 先把左右(有序)序列的数据按照规则填充到中转数组 temp // 直到左右俩边的有序序列有一边处理完毕为止 while (i<=mid && j<=right){ if(arr[i] <= arr[j]){ tmp[t] = arr[i]; t += 1; i +=1; }else{ tmp[t] = arr[j]; t += 1; j += 1; } } // 2. 把有剩余数据的一边的剩余数据依次全部填充到 temp // 2.1 说明左边有序序列还有剩余元素, 将剩余元素全部填充到 temp while (i <= mid){ tmp[t] = arr[i]; t += 1; i += 1; } // 2.2 说明右边有序序列还有剩余元素, 将剩余元素全部填充到 temp while (j <= right){ tmp[t] = arr[j]; t += 1; j += 1; } t = 0; int tmpleft = left; while (tmpleft <= right){ arr[tmpleft] = tmp[t]; t += 1; tmpleft += 1; } } }
#include <iostream> #include<vector> #include<string> using namespace std; void merge_sort(vector<int>&ret,vector<int>&tmp,int left,int right) { if(left >= right) { return; } int mid = left+(right-left)/2; merge_sort(ret, tmp, left, mid); merge_sort(ret,tmp,mid+1,right); int i=left,j=mid+1,k=0; while(i<=mid && j<=right) { if(ret[i] < ret[j]) { tmp[k++] = ret[i++]; } else { tmp[k++] = ret[j++]; } } while(i<=mid) { tmp[k++] = ret[i++]; } while(j<=right) { tmp[k++] = ret[j++]; } for(i=left,j=0;i<=right;i++,j++) { ret[i] = tmp[j]; } } int main() { vector<int>ret; string s; string str; getline(cin,s); int j=1; int i = 0; for(i=0;i<s.length();i++) { if(s[i]==',') { str = s.substr(j,i-j); ret.push_back(stoi(str)); j = i+1; } } str = s.substr(j,i-j-1); ret.push_back(stoi(str)); int n = ret.size(); vector<int>tmp(n,0); merge_sort(ret,tmp,0,n-1); cout << "["; for(int i=0;i<n;i++) { if(i<n-1) cout << ret[i] << ", "; else cout << ret[i]; } cout << "]"; } // 64 位输出请用 printf("%lld")
import java.util.*; public class Main { public static void main(String[] args) { Scanner scan = new Scanner(System.in); String str = scan.nextLine(); String str1 = str.substring(1,str.length()-1); String[] s = str1.split(", ");//分隔符为一个英文逗号和一个空格 int[] arr = new int[s.length]; for(int j = 0;j < s.length;j ++) { int num = 0; for(int i = 0;i < s[j].length();i ++) { if(s[j].charAt(i) >= '0' && s[j].charAt(i) <= '9') { num = num * 10 + s[j].charAt(i)-'0'; } } //负号情况考虑 if(s[j].charAt(0) == '-') { num = -num; } arr[j] = num; } divide(arr,0,arr.length-1); //执行至此,arr已经变成有序的 System.out.print("["); for(int p = 0;p < arr.length;p ++) { System.out.print(arr[p]); if(p != arr.length-1) { System.out.print(", "); } } System.out.print("]"); } public static void divide(int[] arr,int left,int right) { if(left >= right) return; //分而治之 //取中间索引 int mid = (left + right)/2; //分 divide(arr,left,mid); divide(arr,mid+1,right); //治 merge(arr,left,mid,right); } public static void merge(int[] arr,int left,int mid,int right) { int[] temp = new int[right-left+1];//建立临时数组 int i = left; int j = mid + 1;//指向两个数组的起始位置 int k = 0;//指向临时数组的起始位置 while(i <= mid && j <= right) { if(arr[i] >= arr[j]) { //将更小的arr[j]放进临时数组中 temp[k++] = arr[j++]; }else { //将更小的arr[i]放进临时数组中 temp[k++] = arr[i++]; } } while(i <= mid) { //前一个数组还有剩余 temp[k++] = arr[i++]; } while(j <= right) { //前一个数组还有剩余 temp[k++] = arr[j++]; } //将临时数组中的值更新到原始数组中 for(int p = 0;p < temp.length;p ++) { arr[left+p] = temp[p]; } } }
#include <bits/stdc++.h> using namespace std; void mymerge(vector<int>& nums,int left,int right,int mid) { int l = left,r = mid + 1; vector<int> tem; while(l != mid + 1 || r != right + 1) { if(l == mid + 1) { while (r != right + 1) tem.push_back(nums[r++]); } else if(r == right + 1) { while (l != mid + 1) tem.push_back(nums[l++]); } else if(nums[l] > nums[r]) tem.push_back(nums[r++]); else tem.push_back(nums[l++]); } for(int i = left;i <= right;i ++) { nums[i] = tem[i - left]; } } void mysort(vector<int>& nums,int left,int right) { if(left == right) return; int mid = left + (right - left)/2; mysort(nums, left, mid); mysort(nums, mid + 1, right); mymerge(nums,left,right,mid); } int main() { vector<int> nums; string input; getline(cin, input); int tem = 0; int flag = 1; for(char ch:input) { if(ch == ']') { nums.push_back(flag * tem); } else if(ch >= '0' && ch <= '9') { tem = 10 * tem + ch - '0'; } else if(ch == ',') { nums.push_back(flag * tem); tem = 0; flag = 1; } else if(ch == '-') { flag = -1; } } mysort(nums,0,nums.size() - 1); cout << '['; for(int i = 0;i < nums.size();i ++) { cout << nums[i]; if(i == nums.size() - 1) cout << ']'; else cout << ", "; } return 0; }
//非递归版本 import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); String str = scan.nextLine(); String str1 = str.substring(1,str.length()-1); String[] strs = str1.split(", "); int[] arr = new int[strs.length]; for(int i = 0 ; i<arr.length ; ++i){ arr[i] = Integer.parseInt(strs[i]); } mergaSort(arr); System.out.println(Arrays.toString(arr)); } public static void mergaSort(int[] arr){ for(int i = 1 ; i<arr.length ; i *= 2){ int[] curArr = new int[arr.length]; int s1 = 0; int e1 = s1+i-1; int s2 = e1+1; int e2 = s2+i-1>=arr.length?arr.length-1:s2+i-1; int k = 0; while(s2<arr.length){ while(s1<=e1&&s2<=e2){ if(arr[s1]<=arr[s2]){ curArr[k++] = arr[s1++]; }else{ curArr[k++] = arr[s2++]; } } while(s1<=e1){ curArr[k++] = arr[s1++]; } while(s2<=e2){ curArr[k++] = arr[s2++]; } s1 = e2+1; e1 = s1+i-1; s2 = e1+1; e2 = s2+i-1>=arr.length?arr.length-1:s2+i-1; } while(s1<arr.length){ curArr[k++] = arr[s1++]; } for(int j = 0;j<curArr.length ; ++j){ arr[j] = curArr[j]; } } } }
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <errno.h> #include <assert.h> #define N 1000000 // 1百万 // ==================== Function Declaration ==================== // C99 标准库高仿函数 int str_len(const char * s); void mergeSort(int* nums, int* tmpArr, int l, int r); void merge(int* nums, int* tmpArr, int l, int m, int r); void printNumbers(int* nums, const int numsSize); // ==================== Function Declaration ==================== int main(const int argc, const char** argv) { int nums[N], numsSize = 0; char temp[10 * N]; // 设有一百万个整数,每个整数占10位 gets(temp); char* line = malloc(10 * N * sizeof(char)); strncat(line, temp + 1, str_len(temp) - 2); char* tok = strtok(line, ","); while (tok) { *(nums + numsSize++) = atoi(tok); tok = strtok(NULL, ","); } // Divide and Conquer algorithm 的经典应用 ---- merge_sort int tmpArr[N]; mergeSort(nums, tmpArr, 0, numsSize - 1); return printNumbers(nums, numsSize), 0; } int str_len(const char * s) { assert(s != NULL); // corner case if (*s == '\0') return 0; const char * pc = s; while (*++pc != '\0'); return pc - s; } void mergeSort(int* nums, int* tmpArr, int l, int r) { // recursion exit condition (空集或只有一个元素就认为是有序的) if (l >= r) return; int m = (l + r) >> 1; mergeSort(nums, tmpArr, l, m); mergeSort(nums, tmpArr, m + 1, r); merge(nums, tmpArr, l, m, r); } void merge(int* nums, int* tmpArr, int l, int m, int r) { int i = l, j = m + 1, k = l; while (k <= r) if (i > m) *(tmpArr + k++) = *(nums + j++); else if (j > r) *(tmpArr + k++) = *(nums + i++); else *(tmpArr + k++) = *(nums + i) < *(nums + j) ? *(nums + i++) : *(nums + j++); memcpy(nums + l, tmpArr + l, (r - l + 1) * sizeof(int)); } void printNumbers(int* nums, const int numsSize) { int i; putchar('['); for (i = 0; i < numsSize; ++i) { printf("%d", *(nums + i)); if (i < numsSize - 1) printf(", "); } printf("]\n"); }
s = input().replace("[", "").replace("]", "") nums = list(map(int, s.strip().split(", "))) def merge(left, right): merged = [] i = 0 j = 0 while(i < len(left) and j < len(right)): if left[i] <= right[j]: merged.append(left[i]) i += 1 else: merged.append(right[j]) j += 1 if i < len(left): merged.extend(left[i:]) if j < len(right): merged.extend(right[j:]) return merged def mergeSort(nums): n = len(nums) if n <= 1: return nums mid = n // 2 left = nums[:mid] right = nums[mid:] left = mergeSort(left) right = mergeSort(right) return merge(left, right) print(mergeSort(nums))
import java.util.Arrays; import java.util.Scanner; //20210519 复习一下归并排序 //https://www.nowcoder.com/questionTerminal/23ed40416d9c4c72816edb12daa3bdff // 输入格式:[3, 1, 4, 5, 17, 2, 12] // 输出格式:[1, 2, 3, 4, 5, 12, 17] public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String allInput = sc.nextLine(); String allInputNumString = allInput.substring(1, allInput.length()-1); //消除左右两端的[和] String[] allNumsString = allInputNumString.split(", "); int[] allNums = new int[allNumsString.length]; for(int i=0;i<allNums.length;i++) { allNums[i] = Integer.parseInt(allNumsString[i]); } //现在只使用allNums数组就可以了 guibingSort(allNums,0,allNums.length-1); //还要输出出来 System.out.println(Arrays.toString(allNums)); } //归并排序 分 的方法 private static void guibingSort(int[] allNums, int beginIndex, int endIndex) { if(beginIndex>=endIndex) { //递归结束条件 return; } int midIndex = beginIndex+(endIndex - beginIndex)/2; //左边再次分 guibingSort(allNums,beginIndex,midIndex); //右边再次分 guibingSort(allNums,midIndex+1,endIndex); //两边分好了,合起来 合并的范围就是 [beginIndex --- endIndex] getTogether(allNums,beginIndex,endIndex); } //合并两个有序数组 private static void getTogether(int[] allNums, int beginIndex, int endIndex) { int[] helpArray = new int[endIndex-beginIndex+1]; //辅助空间 int leftBeginIndex = beginIndex; //左半边开始的下标 int midIndex = beginIndex+(endIndex - beginIndex)/2; int rightBeginIndex = midIndex +1; //右半边开始的下标 int helpArrayIndex = 0; //辅助数组的下标位置 while(leftBeginIndex<=midIndex && rightBeginIndex<=endIndex) { if(allNums[leftBeginIndex]<=allNums[rightBeginIndex]) { //稳定性! helpArray[helpArrayIndex] = allNums[leftBeginIndex]; helpArrayIndex++; leftBeginIndex++; }else { helpArray[helpArrayIndex] = allNums[rightBeginIndex]; helpArrayIndex++; rightBeginIndex++; } } //之后,把leftBeginIndex或者rightBeginIndex不到头的,都拷贝到辅助数组里面去 while(leftBeginIndex<=midIndex) { helpArray[helpArrayIndex] = allNums[leftBeginIndex]; helpArrayIndex++; leftBeginIndex++; } while(rightBeginIndex<=endIndex) { helpArray[helpArrayIndex] = allNums[rightBeginIndex]; helpArrayIndex++; rightBeginIndex++; } //最后,将helpArray覆盖原数组allNums对应的位置,也就是[beginIndex---endIndex]的全部位置 for(int i=0;i<helpArray.length;i++) { allNums[i+beginIndex] = helpArray[i]; } } }