Java有序數組的實現

2019-11-06 08:44:37

字體：大中小

來源：轉載

供稿：網友

算法和數據結構是程序的核心，有時候可能能夠很方便的使用java等語言提供的類庫，也能通過類庫滿足我們開發中遇到的絕大多數的需求，但是如果想加深計算機技能的深度，算法和數據結構是不可或缺的，因為計算機技術飛速發展，只有算法和數據結構這些本質的、思想性的東西不會改變，重復”造輪子”個人覺得是提高技能最好的途徑。

有序數組：數組存儲有序的元素缺陷：暫不考慮重復數組元素的問題

說明：

這里不會自己設計一個數組，而是通過代理模式，代理Java已實現的數組對象，實現有序數組的功能

有序數組結構主體：

package com.zhiwei.array;public class OrderArray { PRivate int[] orderArray; private int nElems; //非空元素個數 private int initSize; //數組最大容納元素個數 public OrderArray(int initSize){ this.orderArray = new int[initSize]; this.nElems = 0; this.initSize = initSize; }}

①：設計有序數組添加新元素的方法：addElem(int value) 思路：

①：數組已經初始化其內存空間是不能發生改變的，因此數組添加新元素的時候需要考慮數組的存儲空間是否有限的問題 ②：新元素有序插入：確定新元素位置–》原數組受影響元素向后移動1位–》存放新元素 ③：更新數組的屬性信息：非空元素個數等

public boolean addElem(int value){ if(nElems>=initSize){ return false; } int index = 0; for(int i=0;i<nElems;i++){ if (value > orderArray[i]){ index = i+1; break; } } //最后一個非空元素開始后移1位 for(int j=nElems-1;j>=index;j--){ orderArray[j+1] = orderArray[j]; } orderArray[index] = value; nElems++; return true; }

②：設計有序數組刪除元素方法：delElem(int value) 思路：

①：檢查原數組是否包含指定值的元素，如果不存在則不處理 ②：有序數組刪除元素：確定目標元素位置–》受影響元素前移動1位–》重置原數組最后一個元素值 ③：更新有序數組屬性：非空元素個數等注意：元素添加的時候已經保證元素的順序，刪除不影響原有的排列順序

public boolean delElem(int value){ boolean flag = false; int index = 0; for(int i=0;i<nElems;i++){ if(value == orderArray[i]){ index = i; flag = true; break; } } if(!flag) return false; for(int i=index;i<nElems-1;i++){ orderArray[i] = orderArray[i+1]; } orderArray[nElems-1] = 0; nElems--; return true; }

③：設計有序數組更新元素方法：updateElem(int index,int value) 思路：

①：檢查設置的元素下表是否越界 ②：保證更新后的數組的有序：更新指定的元素–》排序

public boolean updateElem(int index,int value){ if(index>=nElems) return false; orderArray[index] = value; sortArray(); //重新排序：這里采用冒泡法 return true; }

冒泡排序法思想：每次排序都將最大或者最小的元素篩選出來放在最后，然后一次對剩下的元素進行最值篩選，最后形成有序的序列 sortArray()方法:

public void sortArray(){ for(int i=0;i<nElems;i++){ for(int j=0;j<nElems-i-1;j++){ if(orderArray[j]>orderArray[j+1]){ int temp = orderArray[j]; orderArray[j] = orderArray[j+1]; orderArray[j+1] = temp; } } } }

④：提供遍歷數組元素信息方法：show()

public void show(){ StringBuffer sb = new StringBuffer(); sb.append("數組元素：["); for(int i=0;i<nElems;i++){ sb.append(orderArray[i]+","); } sb.deleteCharAt(sb.length()-1).append("]"); System.out.println(sb); }

⑤：返回數組的非空元素的屬性信息：length()

public int length(){ return nElems; }

測試代碼：

OrderArray orderArray = new OrderArray(10); orderArray.addElem(10); orderArray.addElem(8); orderArray.addElem(9); orderArray.addElem(5); orderArray.addElem(8); orderArray.addElem(7); orderArray.show(); orderArray.delElem(11); orderArray.show(); orderArray.delElem(8); orderArray.delElem(9); orderArray.show(); orderArray.updateElem(3,6); orderArray.show(); System.out.println(orderArray.length());

結果：這里寫圖片描述