排序

• 快速排序

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class Main {
  	private static int[] arr = new int[100005];
  
  	public static void main(String[] args) throws IOException {
          //使用BufferedReader提高输入效率
  		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  		int n = Integer.parseInt(bf.readLine());
  		String[] str = bf.readLine().split(" ");
  		for (int i = 0; i < n; i++)
  			arr[i] = Integer.parseInt(str[i]);
  		quick_sort(0, n - 1);
  		for (int i = 0; i < n; i++)
  			System.out.print(arr[i] + " ");
          bf.close();
  	}
  
  	private static void quick_sort(int l, int r) {
  		if (l >= r)
  			return;
  		int i = l - 1, j = r + 1;
          //确定分界点，推荐中间位置的数
  		int x = arr[(l + r) / 2];
          //调整区间，使左半部分都小于等于x,右半部分都大于等于x
  		while (i < j) {
  			do
  				i++;
  			while (arr[i] < x);
  			do
  				j--;
  			while (arr[j] > x);
  			if (i < j) {
  				int temp = arr[i];
  				arr[i] = arr[j];
  				arr[j] = temp;
  			}
  		}
          //递归处理左右两段
  		quick_sort(l, j);
  		quick_sort(j + 1, r);
  	}
  
  }

• 归并排序

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  
  public class Main {
      private static int N=100005;
      private static int[] temp = new int[N];
      private static int[] arr= new int[N];
  	public static void main(String[] args) throws IOException {
  		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
  		int n = Integer.parseInt(bf.readLine());
  		String[] str = bf.readLine().split(" ");
  		for (int i = 0; i < n; i++)
  			arr[i] = Integer.parseInt(str[i]);
  		merge_sort( 0, n - 1);
  		for (int i = 0; i < n; i++)
  			System.out.print(arr[i] + " ");
  	}
  
  	private static void merge_sort(int l, int r) {
  		if (l >= r)
  			return;
          //确定分界点
  		int mid = l + r >> 1;
          
          
          //递归划分
  		merge_sort( l, mid);
  		merge_sort(mid + 1, r);
          
          
          //归并，即合并两段
  		int i = l, j = mid + 1, k = 0;
  		int[] temp = new int[r-l+1];
  		while (i <= mid && j <= r) {
              //谁大，谁就先放入temp
  			if (arr[i] <= arr[j])
  				temp[k++] = arr[i++];
  			else
  				temp[k++] = arr[j++];
  
  		}
          //未读完的剩余部分放入temp
  		while (i <= mid)
  			temp[k++] = arr[i++];
  		while (j <= r)
  			temp[k++] = arr[j++];
          //排好序的temp复制到原数组中
  		for (int t = l, p = 0; t <= r; t++, p++)
  			arr[t] = temp[p];
  	}
  
  }