1. 選擇排序 selection sort
大循環 從左到右每次以一個點開始掃描array
小循環 找到從當前起始點開始的最小值
時間復雜度為O(N^2)


//selection sort an array array[] public class Solution {public int[] solve(int[] array) {if (array == null || array.length == 0) {return array;}for (int i = 0; i < array.length - 1; i++) {int gobalMin = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[gobalMin]) {gobalMin = j;}}swap(array, i, gobalMin);}return array;}private void swap(int[] array, int i, int j) {int temp = array[i];array[i] = array[j];array[j] = temp;} }
?
?
2. 歸并排序 Merge sort
歸并排序是基于一種被稱為“分治”(divide and conquer)的策略。
Merge sort array:


public int[] mergeSort(int[] array) {if (array == null || array.length == 0) {return array;}int[] temp = new int[array.length];mergeSortHelper(array, 0, array.length - 1, temp);return array;}private void mergeSortHelper(int[] array, int start, int end, int[] temp) {if (start == end) {return;}int mid = start + (end - start) / 2;mergeSortHelper(array, start, mid, temp);mergeSortHelper(array, mid + 1, end, temp);merge(array, start, mid, end, temp);}private void merge(int[] array, int start, int mid, int end, int[] temp) {int left = start;int right = mid + 1;int index = start;while (left <= mid && right <= end) {if (array[left] < array[right]) {temp[index++] = array[left++];} else {temp[index++] = array[right++];}}while (left <= mid) {temp[index++] = array[left++];}while (right <= end) {temp[index++] = array[right++];}for (index = start; index <= end; index++) {array[index] = temp[index];}}
復雜度分析:
?
1 2 3 4 5 6 7 8?
/ ? 當前層拆分需要劈1刀 O(1)
1 2 3 4
/ 當前層拆分需要劈2刀 O(2)
12 ...
/
? 1 ? 當前層拆分需要劈n ?/2刀
1 + 2 + 4 + 8+ ... + n/2 -> n ?= O(n) ?可以這樣理解,終極狀態下每個數字被切分成一個單位,n個數字,需要被切n-1刀
所以devide and conquer的上半部分的時間復雜度是O(n) 而不是log(n)
空間復雜度:考慮計算機里面只要保存的額外開銷,其實是粉色部分,因為在任意時刻,計算機只有一個確定的狀態,call stack在同一個確定的層只能保留部分的結果。比如最底層只能保留1,或者保留2,而不會1,2同時在棧里面!
所以空間復雜度:1 + 2 + 4 + 8 + ... + n = O(2n) = O(n)
? ==============================================
devide and conquer的上半部分,merge 部分, totoal time complexity is O(nlogn):
1 ? ? ?2 ? ? ? ? 3 ? ? 4 ? ? ? 5 ? ?6 ? ? ?7 ? ? ? 8
\/ ? ? ? ? ? ? ? ?\/ ? ? ? ? ? ? \/ ? ? ? ? ? ? ?\/ this level time complexity is O(n)
12 ? ? ? ? ? ? ? 34 ? ? ? ? ? ?56 ? ? ? ? ? ?78
\ ? ? / ? ? ? ? ? ? ? \ ? ? ? ?/ this level time complexity is O(n)
1234 5678
\ ? ? ? ? ? ? ? ? ? ? ? ? ?/ this level time complexity is O(n)
12345678
?
3. 快速排序
Array quick sort:
重點在于理解左右兩個擋板的物理意義!!!
a. [0,....., left]: left 的左側(不包含left)全部為比pivot小的數
b. [left, right]: left 和 right之間為未探索的區域
c. [right, ..... n-1]: right的右側(不包含)全部為比pivot大或者等于的數字


public class Solution {/*** @param A an integer array* @return void*/public void sortIntegers2(int[] A) {quickSort(A, 0, A.length - 1);}private void quickSort(int[] A, int start, int end) {if (start >= end) {return;}int left = start, right = end;// key point 1: pivot is the value, not the indexint pivot = A[(start + end) / 2];// key point 2: every time you compare left & right, it should be // left <= right not left < rightwhile (left <= right) {// key point 3: A[left] < pivot not A[left] <= pivotwhile (left <= right && A[left] < pivot) {left++;}// key point 3: A[right] > pivot not A[right] >= pivotwhile (left <= right && A[right] > pivot) {right--;}if (left <= right) {int temp = A[left];A[left] = A[right];A[right] = temp;left++;right--;}}quickSort(A, start, right);quickSort(A, left, end);} }
?
偽代碼:
function quicksort(q)var list less, pivotList, greaterif length(q) ≤ 1 {return q} else {select a pivot value pivot from qfor each x in q except the pivot elementif x < pivot then add x to lessif x ≥ pivot then add x to greateradd pivot to pivotListreturn concatenate(quicksort(less), pivotList, quicksort(greater))}
?
?
?
?
?
Linkedlist quick sort


public class Solution {public ListNode sortList(ListNode head) {if (head == null || head.next == null) {return head;}ListNode mid = findMedian(head); // O(n)//new three dummmy node with a tail point to itListNode leftDummy = new ListNode(0), leftTail = leftDummy;ListNode rightDummy = new ListNode(0), rightTail = rightDummy;ListNode middleDummy = new ListNode(0), middleTail = middleDummy;//sprate to three part while (head != null) {if (head.val < mid.val) {leftTail.next = head;leftTail = head;} else if (head.val > mid.val) {rightTail.next = head;rightTail = head;} else {middleTail.next = head;middleTail = head;}head = head.next;}//make the tail to nullleftTail.next = null;middleTail.next = null;rightTail.next = null;//recurisive do the sortListNode left = sortList(leftDummy.next);ListNode right = sortList(rightDummy.next);//connect the three parts togetherreturn concat(left, middleDummy.next, right);}private static ListNode findMedian(ListNode head) {ListNode fast = head.next;ListNode slow = head;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;}private static ListNode concat(ListNode left, ListNode mid, ListNode right) {ListNode dummy = new ListNode(0), dummyTail = dummy;dummyTail = connect(dummyTail, left);dummyTail = connect(dummyTail, mid);dummyTail = connect(dummyTail, right);return dummy.next;}private static ListNode connect(ListNode dummyTail, ListNode current) {while (current != null) {dummyTail.next = current;dummyTail = dummyTail.next;current = current.next;}return dummyTail;} }
?
?
相關題目整理: //to do?