2019獨角獸企業重金招聘Python工程師標準>>>

表插入排序

隨機產生一組數，通過鏈表進行排序，然后在復制到數組中，提高效率

class Link {public long ddata;public Link next;public Link(long dd){ddata = dd;}public void displayLink(){System.out.println(ddata + " ");} } class SortedList {private Link first;public SortedList(){first = null;}public SortedList(Link[] linkArr){first = null;for(int j=0;j<linkArr.length;j++)insert(linkArr[j]);}public boolean Empty(){return (first == null);}public void insert(Link k){Link previous = null;Link current = first;while(current !=null&&k.ddata>current.ddata){previous = current;current = current.next;}if(previous == null)first = k;elseprevious.next =k;k.next = current;}public Link remove(){Link temp = first;first = first.next;return temp;}public void displayList(){System.out.println("link");Link currrent = first;while(currrent != null){currrent.displayLink();currrent = currrent.next;}System.out.println(" ");} } class ListInsertionApp {public static void main(String[] args){int size = 10;Link[] linkArray = new Link[size];for(int j=0;j<size;j++){int n = (int)(java.lang.Math.random()*99);Link newLink = new Link(n);linkArray[j] = newLink;}System.out.println("unsorted");for(int j=0;j<size;j++){System.out.print(linkArray[j].ddata+" ");System.out.println(" ");SortedList theSortedList = new SortedList(linkArray);for(int i=0;i<size;i++)linkArray[i] = theSortedList.remove();System.out.print("sorted");for(int x=0;x<size;x++)System.out.print(linkArray[x].ddata+" ");System.out.println(" ");}} }

雙向鏈表：允許向前遍歷也允許向后遍歷

缺點：每次插入和刪除一個鏈結點的時候，要出來四個鏈結點的引用，而不是兩個。

一下是插入功能，分為從鏈表頭插入和鏈表尾插入

class Link {public long ddata;public Link next;public Link previous;public Link(long d){ddata = d;}public void displayLink(){System.out.println(ddata + " ");} } class DoublyLinkedList {private Link first;private Link last;public DoublyLinkedList(){first = null;last = null;}public boolean isEmpty(){return first == null;}public void insertFirst(long dd){Link newLink = new Link(dd);if(isEmpty())last = newLink;elsefirst.previous = newLink;newLink.next = first;first = newLink;}public void insertLast(long dd){Link newLink = new Link(dd);if(isEmpty())first = newLink;else{last.next = newLink;newLink.previous = last; }last = newLink;} }

?

轉載于:https://my.oschina.net/u/3829307/blog/1922373

總結

以上是生活随笔為你收集整理的数据结构与算法17-表插入排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。