本文共 8293 字，大约阅读时间需要 27 分钟。

参考网络资料，复习用Java实现排序算法:冒泡排序、直接选择排序、直接插入排序、快速排序。数据结构:单链表、栈。

一眼就看明白的代码就把注释省略了。

package sort;import java.lang.reflect.Array;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Stack;/** * review some sort methods and data structure *  * @author Administrator *  */public class SortReview {	/**	 * inner array	 */	private ArrayList
   
     nums = new ArrayList
    
     () {		private static final long serialVersionUID = 1L;		{			for (int i = 1; i <= 15; i += 2) {				this.add(i);			}		}	};	public void bubbleSort() {// ascendent		int tmp = 0;		for (int i = 0; i < nums.size(); i++) {			for (int j = i + 1; j < nums.size(); j++) {				if (nums.get(j) < nums.get(i)) {					tmp = nums.get(i);					nums.set(i, nums.get(j));					nums.set(j, tmp);				}			}		}		System.out.println(nums);	}	public void selectSort() {		Integer index = 0;// the max number		Integer tmpNum = 0;		for (int i = 0; i < nums.size(); i++) {			for (int j = i + 1; j < nums.size(); j++) {				if (nums.get(index) > nums.get(j)) {// find the minimize index					index = j;				}			}			if (index != 0) {				tmpNum = nums.get(i);				nums.set(i, nums.get(index));				nums.set(index, tmpNum);			}		}	}	public void insertSort() {		Integer index = 0;		Integer tmpNum = 0;		int size = nums.size();		for (int i = 0; i < size; i++) {			// index = i + 1;			for (int j = i; j >= 0; j--) {				if (nums.get(j) > nums.get(index)) {					index = j;				}			}			if (index != 0) {				tmpNum = nums.get(i);				nums.set(i, nums.get(index));				nums.set(index, tmpNum);			}		}	}	private void quickSort(List
     
       originList) {		if (originList.size() <= 1) {			return;		}		Integer key = originList.get(0);		List
      
        leftList = new ArrayList
       
        ();		List
        
          rightList = new ArrayList
         
          (); for (int i = 0; i < originList.size(); i++) { if (originList.get(i) <= key) { leftList.add(originList.get(i)); } else if (originList.get(i) > key) { rightList.add(originList.get(i)); } } quickSort(leftList); quickSort(rightList); } /** * 归并排序 * @param arr * @param low * @param high */ void myMergeSort(int[] arr, int low, int high) { if (low < high) { int mid = (low + high) / 2; myMergeSort(arr, low, mid); myMergeSort(arr, mid + 1, high); mergeArr(arr, low, mid, high); } } /** * 归并排序 * @param arr * @param low * @param mid * @param high */ void mergeArr(int[] arr, int low, int mid, int high) { int len = high - low + 1; int[] bridge = new int[len]; int i = low; int j = mid + 1; int k = 0; while (i <= mid && j <= high) { if (arr[i] < arr[j]) { bridge[k++] = arr[i++]; } else { bridge[k++] = arr[j++]; } } while (i <= mid) { bridge[k++] = arr[i++]; } while (j <= high) { bridge[k++] = arr[j++]; } for (int m = 0; m < len; m++) { arr[m + low] = bridge[m]; } } int binarySearch(int[] sortedArr, int low, int high, int target) { if (low < high) return -1; int mid = low + (high - low) / 2; if (sortedArr[mid] == target) return mid; if (sortedArr[mid] < target) { return binarySearch(sortedArr, mid + 1, high, target); } else { return binarySearch(sortedArr, low, mid - 1, target); } } private void swap(int[] arr, int i, int min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } /** * node of the custom linked list * * @author Administrator * */ class LinkedArrayEle { LinkedArrayEle next;//point to the next element Object data; public LinkedArrayEle(Object data) { super(); this.data = data; } @Override public String toString() { return String.valueOf(this.data); } } /** * the custom linked list * * @author Administrator * */ private final class LinkedArray { LinkedArrayEle head = null; Integer pos = 0; public void showELes() { if (head == null) { return; } LinkedArrayEle curEle = head; while (curEle != null) { System.out.println(String.format("%d -> %s", pos, curEle)); curEle = curEle.next; pos++; } pos = 0; } public void addFirst(LinkedArrayEle ele) { ele.next = head; head = ele; } public void add(Integer index, LinkedArrayEle ele) { if (head == null) {// empty list System.out.println("empty list"); addFirst(ele); return; } LinkedArrayEle preEle = head; LinkedArrayEle curEle = head; while (pos != index) { if (curEle == null) {// avoid null pointer exception curEle = new LinkedArrayEle("null"); } preEle = curEle; if (curEle.next == null) { curEle.next = new LinkedArrayEle("null"); } curEle = curEle.next; pos++; } preEle.next = ele; ele.next = curEle; pos = 0; } public void del(Integer index) { LinkedArrayEle curEle = head; LinkedArrayEle preEle = head; while (index != pos) { preEle = curEle; curEle = curEle.next; pos++; } curEle = curEle.next; preEle.next = curEle; pos = 0; } public void update(LinkedArrayEle ele, Integer index) { LinkedArrayEle preEle = head; LinkedArrayEle curEle = head; while (index != pos) { preEle = curEle; curEle = curEle.next; pos++; } preEle.next = ele; ele.next = curEle.next; pos = 0; } public void find(Integer index) { LinkedArrayEle preEle = head; LinkedArrayEle curEle = head; pos = 0; while (index != pos) {// stop at index preEle = curEle; curEle = curEle.next; pos++; } pos = 0; System.out.println(String.format("%d map %s", pos, curEle.data.toString())); } /** * reverse the array */ public LinkedArrayEle reverse() { LinkedArrayEle curEle = head; LinkedArrayEle nxtEle = null; LinkedArrayEle reverseHead = null; LinkedArray array2 = new LinkedArray(); while (curEle != null) {// stop at index nxtEle = curEle.next; curEle.next = reverseHead; reverseHead = curEle; curEle = nxtEle; } return reverseHead; } /** * print element from the end */ public void backPrint() { MyStack myStack = new MyStack(); LinkedArrayEle curEle = head; while (curEle != null) {// stop at index myStack.push(curEle); curEle = curEle.next; } while (myStack.size() > 0) { System.out.println(myStack.pop()); } } /** * get the middle element of the custom array * * @return */ public LinkedArrayEle getMiddleEle() { LinkedArrayEle firstPointer = head; LinkedArrayEle secondPointer = head; while (firstPointer != null && firstPointer.next != null) { firstPointer = firstPointer.next.next; secondPointer = secondPointer.next; } return secondPointer; } /** * get the last No.K element * * @param k * @return */ public LinkedArrayEle getLastK(Integer k) { if (head == null || k == 0) { throw new RuntimeException("invalid parameter"); } LinkedArrayEle firstPointer = head; LinkedArrayEle secondPointer = head; for (int i = 0; i < k; i++) { firstPointer = firstPointer.next; } while (firstPointer != null) { firstPointer = firstPointer.next; secondPointer = secondPointer.next; } return secondPointer; } /** * get the size of the linked list * * @return */ public Integer getSize() { LinkedArrayEle firstPointer = head; Integer size = 0; while (firstPointer != null) { size++; firstPointer = firstPointer.next; } return size; } } /** * custom stack * * @author Administrator * */ class MyStack { public Integer size = 0; // private Object topEle = null; private Object[] arr = new Object[8]; public void push(Object o) { if (this.isFull()) { this.expand(); } arr[size] = o; size++; } public Object pop() { return this.isEmpty() ? arr[size] : null; } public boolean isEmpty() { return size.equals(0); } public boolean isFull() { return size.equals(arr.length); } public Integer size() { return this.size; } /** * expand the capacity of the inner array */ private void expand() { if (this.isFull()) { Object[] arr2 = new Object[this.size * 2]; for (int i = 0; i < arr.length; i++) { arr2[i] = arr[i]; } arr = arr2; } } } /** * execute main method * * @param args */ public static void main(String[] args) { SortReview sortReview = new SortReview(); // sortReview.bubbleSort(); // sortReview.quickSort(sortReview.nums); // SortReview.checkQueto(); LinkedArray array = sortReview.new LinkedArray(); LinkedArrayEle ele = sortReview.new LinkedArrayEle("cat"); array.add(1, ele); ele = sortReview.new LinkedArrayEle("dog"); array.add(2, ele); // array.del(3); array.update(sortReview.new LinkedArrayEle("mouse"), 1); array.showELes(); // array.find(1); // System.out.println(array.reverse()); // array.backPrint(); // array.getMiddleEle(); System.out.println("---------------------------"); System.out.println(array.getLastK(2)); System.out.println(array.getSize()); // sortReview.selectSort(); // sortReview.insertSort(); // System.out.println(sortReview.nums); }}
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/yangjiegang8/article/details/78317277 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！