算法思想

 

 

 模板

 1 import java.io.BufferedInputStream;
 2 import java.util.Scanner;
 3 
 4 public class Main{
 5     public static void main(String[] args){
 6         Scanner scan = new Scanner(new BufferedInputStream(System.in));
 7         int n = scan.nextInt();
 8         int[] q = new int[n];
 9         for(int i = 0; i < n; i++) q[i] = scan.nextInt();
10         merge_sort(q, 0, n - 1);
11         for(int i = 0; i < n; i++) System.out.print(q[i] + " ");
12     }
13     
14     public static void merge_sort(int[] q, int l, int r){
15         if(l >= r) return;
16         int mid = (l + r) / 2; //将数组一分为二
17         merge_sort(q, l, mid); merge_sort(q, mid + 1, r);
18         int k = 0, i = l, j = mid + 1; //k来标记temp，i和j分别指向二分后的数组的开头
19         int[] temp = new int[r - l + 1];
20         while(i <= mid && j <= r) 
21             if(q[i] < q[j]) temp[k++] = q[i++];
22             else temp[k++] = q[j++];
23         while(i <= mid) temp[k++] = q[i++];
24         while(j <= r) temp[k++] = q[j++];
25         for(i = l, k = 0; i <= r; i++, k++) q[i] = temp[k];
26     }
27 }

归并排序是稳定排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。