归并排序

#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;  }
    }
}

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");
}

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];
		}
	}
}