归并排序-Java实现
2018-07-24 07:53:18来源:博客园 阅读 ()
归并排序,作为分治思想的典型应用,值得掌握;在稳定性方面,是唯一复杂度为O(NlgN)的稳定排序。
1 /** 2 * Created by hardaway on 2018/7/23. 3 * 归并排序 4 * 分治思想,分:划分为规模更小的相似问题;治:将两个有序子序列整合为一个。 5 * 时间复杂度O(NlgN), 最好,最坏,平均复杂度是O(NlgN) 6 * 稳定排序 7 */ 8 public class mergeSorting { 9 public void sort(int[] arr){ 10 sort(arr,0,arr.length-1); 11 } 12 public void sort(int[] arr, int head, int tail){ 13 if(head>=tail) 14 return; 15 int mid = head+(tail-head)/2; 16 sort(arr, head, mid); 17 sort(arr, mid+1, tail); 18 format(arr,head,mid,tail); 19 } 20 public void format(int[] arr, int head, int mid, int tail){ 21 int[] small = Arrays.copyOfRange(arr,head,tail+1); 22 int tp1 = 0; 23 int tp2 = mid-head+1; 24 int i = head; 25 int end1 = mid-head; 26 int end2 = tail-head; 27 while(tp1<=end1&&tp2<=end2){ 28 if(small[tp1]<=small[tp2]) 29 arr[i++] = small[tp1++]; 30 else 31 arr[i++] = small[tp2++]; 32 } 33 while(tp1<=end1){ 34 arr[i++] = small[tp1++]; 35 } 36 while (tp2<=end2){ 37 arr[i++] = small[tp2++]; 38 } 39 } 40 41 public static void main(String[] args) { 42 int[] arr = {9,3,1,4,2,7,8,6,5}; 43 System.out.println(Arrays.toString(arr)); 44 mergeSorting m = new mergeSorting(); 45 m.sort(arr); 46 System.out.println(Arrays.toString(arr)); 47 } 48 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 1-Java基础回顾整理_01 2020-06-10
- 基础排序算法(附加java实现) 2020-06-02
- Java--Java的设计模式----单例模式 2020-05-26
- Java--Java的继承性 2020-05-26
- LeetCode 面试题53 - I. 在排序数组中查找数字 I 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash