1.

  • 5 1 3(a) 4 7 3(b)

  • 1 3(a) 3(b) 4 5 7

  • 1 3(b) 3(a) 4 5 7

In-place Algorithm

2.

2.1

public class Asserts { public static void test(boolean value) { try { if (!value) throw new Exception(" "); } catch (Exception e) { e.printStackTrace(); } } }

2.2 Integers

public class Integers { /** */ public static Integer[] random(int count, int min, int max) { if (count <= 0 || min > max) return null; Integer[] array = new Integer[count]; int delta = max - min + 1; for (int i = 0; i < count; i++) { array[i] = min + (int)(Math.random() * delta); } return array; } /** */ public static Integer[] combine(Integer[] array1, Integer[] array2) { if (array1 == null || array2 == null) return null; Integer[] array = new Integer[array1.length + array2.length]; for (int i = 0; i < array1.length; i++) { array[i] = array1[i]; } for (int i = 0; i < array2.length; i++) { array[i + array1.length] = array2[i]; } return array; } public static Integer[] same(int count, int unsameCount) { if (count <= 0 || unsameCount > count) return null; Integer[] array = new Integer[count]; for (int i = 0; i < unsameCount; i++) { array[i] = unsameCount - i; } for (int i = unsameCount; i < count; i++) { array[i] = unsameCount + 1; } return array; } /** * * disorderCount */ public static Integer[] headTailAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int begin = (array.length - disorderCount) >> 1; reverse(array, begin, begin + disorderCount); return array; } /** * * disorderCount */ public static Integer[] centerAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; int left = disorderCount >> 1; reverse(array, 0, left); int right = disorderCount - left; reverse(array, array.length - right, array.length); return array; } /** * * disorderCount */ public static Integer[] headAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, array.length - disorderCount, array.length); return array; } /** * * disorderCount */ public static Integer[] tailAscOrder(int min, int max, int disorderCount) { Integer[] array = ascOrder(min, max); if (disorderCount > array.length) return array; reverse(array, 0, disorderCount); return array; } /** */ public static Integer[] ascOrder(int min, int max) { if (min > max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = min++; } return array; } /** */ public static Integer[] descOrder(int min, int max) { if (min > max) return null; Integer[] array = new Integer[max - min + 1]; for (int i = 0; i < array.length; i++) { array[i] = max--; } return array; } /** */ private static void reverse(Integer[] array, int begin, int end) { int count = (end - begin) >> 1; int sum = begin + end - 1; for (int i = begin; i < begin + count; i++) { int j = sum - i; int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } /** */ public static Integer[] copy(Integer[] array) { return Arrays.copyOf(array, array.length); } /** */ public static boolean isAscOrder(Integer[] array) { if (array == null || array.length == 0) return false; for (int i = 1; i < array.length; i++) { if (array[i - 1] > array[i]) return false; } return true; } /** */ public static void println(Integer[] array) { if (array == null) return; StringBuilder string = new StringBuilder(); for (int i = 0; i < array.length; i++) { if (i != 0) string.append("_"); string.append(array[i]); } System.out.println(string); } }

2.3

public class Times { private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS"); public interface Task { void execute(); } public static void test(String title, Task task) { if (task == null) return; title = (title == null) ? "" : (" " + title + " "); System.out.println(title); System.out.println(" " + fmt.format(new Date())); long begin = System.currentTimeMillis(); task.execute(); long end = System.currentTimeMillis(); System.out.println(" " + fmt.format(new Date())); double delta = (end - begin)/1000.0; System.out.println(" " + delta + " "); System.out.println("-------------------------------------"); } }

2.4 Sort

public abstract class Sort<T extends Comparable<T>> implements Comparable<Sort<T>> { /** */ protected T[] array; /** */ private int cmpCount; /** */ private int swapCount; /** */ private long time; /** */ private DecimalFormat fmt = new DecimalFormat("#.00"); /** */ public void sort(T[] array) { if (array == null || array.length < 2) return; this.array = array; long begin = System.currentTimeMillis(); sort(); time = System.currentTimeMillis() - begin; } /** */ protected abstract void sort(); /** * * * 0 array[index1] == array[index2] * 0 array[index1] < array[index2] * 0 array[index1] > array[index2] */ protected int cmp(int index1, int index2) { cmpCount++; return array[index1].compareTo(array[index2]); } /** */ protected int cmp(T value1, T value2) { cmpCount++; return value1.compareTo(value2); } /** */ protected void swap(int index1, int index2) { swapCount++; T tmp = array[index1]; array[index1] = array[index2]; array[index2] = tmp; } /** */ @SuppressWarnings("unchecked") private boolean isStable() { Student[] students = new Sort.Student[20]; for (int i = 0; i < students.length; i++) { //0 10 10 10 20 10 30 10 students[i] = new Student(i * 10, 10); } sort((T[]) students);// for (int i = 1; i < students.length; i++) { int score = students[i].score; int prevScore = students[i - 1].score; if (score != prevScore + 10) return false; } return true; } private static class Student implements Comparable<Student>{ Integer score; Integer age; public Student(Integer score, Integer age) { this.score = score; this.age = age; } @Override public int compareTo(Student o) { return age - o.age; } } /** */ @Override public int compareTo(Sort o) { int result = (int)(time - o.time); if(result != 0) return result; result = cmpCount - o.cmpCount; if(result != 0) return result; return swapCount - o.swapCount; } @Override public String toString() { return " " + getClass().getSimpleName() + "/n" + " ==> " + numberString(swapCount) + "\n" + " ==> " + numberString(cmpCount) + "\n" + " ==> " + time * 0.001 + "s" + "\n" + " ==> " + isStable() + "\n" + "================================="; } /** */ private String numberString(int number) { if (number < 10000) return "" + number; if (number < 100000000) { return fmt.format(number/10000.0) + " "; } return fmt.format(number/100000000.0) + " "; } }

3. Bubble Sort

3.1

3.2

public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) < 0) { swap(i, i - 1); } } } }

3.4

public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { boolean sorted = true; for (int i = 1; i <= eIndex; i++) { if (cmp(i,i - 1) < 0) { swap(i, i - 1); sorted = false; } } if (sorted) break; } }

3.5

<code-pre class="code-pre" id="pre-AZsyhD" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;">public class BubbleSort<T extends Comparable<T>> extends Sort<T> { /** * * sortedIndex 1 eIndex-- > 0 * => sortedIndex eIndex * => sortedIndex 1 * */ @Override public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { int sortedIndex = 1;// for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) < 0) { swap(i, i - 1); sortedIndex = i; } } eIndex = sortedIndex; } } }</code-pre> </pre></code-box>

3.6

  • O(n^2 O(n)

  • O(1)

<code-pre class="code-pre" id="pre-zmmbCP" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;">public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { for (int i = 1; i <= eIndex; i++) { if (cmp(i, i - 1) <= 0) { swap(i, i - 1); } } } }</code-pre> </pre></code-box>

4.1

4.2

public class SelectionSort<T extends Comparable<T>> extends Sort<T> { @Override public void sort() { for (int eIndex = array.length - 1; eIndex > 0; eIndex--) { int maxIndex = 0; for (int i = 1; i <= eIndex; i++) { // <= if (cmp(maxIndex, i) <= 0) { maxIndex = i; } } if(maxIndex != eIndex) swap(maxIndex, eIndex); } } }

4.3

  • O(n^2) O(1)

=>

5. Heap Sort

5.1

  • heapify
  • 1
    • 1
    • 0 siftDown

5.2

public class HeapSort<T extends Comparable<T>> extends Sort<T> { /** */ private int heapSize; @Override protected void sort() { // heapSize = array.length; for (int i = (heapSize >> 1) - 1; i >= 0; i--) { siftDown(i); } while (heapSize > 1) { // swap(0, --heapSize); // 0 siftDown siftDown(0); } } /** */ private void siftDown(int index) { T element = array[index]; int half = heapSize >> 1; while (index < half) {//index // int childIndex = (index << 1) + 1; T child = array[childIndex]; int rightIndex = childIndex + 1; // if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) { child = array[childIndex = rightIndex]; } // if (cmp(element, child) >= 0) break; array[index] = child; index = childIndex; } array[index] = element; } }

5.2

  • O(nlog^n)
  • O(1)

5.3.

@SuppressWarnings({"rawtypes","unchecked"}) public class SortTest { public static void main(String[] args) { Integer[] arr1 = Integers.random(10000, 1, 20000); testSort(arr1, new SelectionSort(), new HeapSort(), new BubbleSort()); } static void testSort(Integer[] arr,Sort... sorts) { for (Sort sort: sorts) { Integer[] newArr = Integers.copy(arr); sort.sort(newArr); // Asserts.test(Integers.isAscOrder(newArr)); } Arrays.sort(sorts); for (Sort sort: sorts) { System.out.println(sort); } } }

6. Insertion Sort

6.1

6.2

<code-pre class="code-pre" id="pre-cK7r8F" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;">public class InsertionSort<T extends Comparable<T>> extends Sort<T> { @Override protected void sort() { for (int i = 1; i < array.length; i++) { int cur = i; while(cur > 0 && cmp(cur,cur - 1) < 0) { swap(cur,cur - 1); cur--; } } } }</code-pre>

6.3 Inversion

 => [2,3,8,6,1] <2,1> < 3,1> <8,1> <8,6> <6,1>

O(n^2)

6.4

=>

  • 1

public class InsertionSort<T extends Comparable<T>> extends Sort<T> { @Override protected void sort() { for (int i = 1; i < array.length; i++) { int cur = i; T val = array[cur]; while(cur > 0 && cmp(val,array[cur - 1]) < 0) { array[cur] = array[cur - 1];// cur--; } array[cur] = val; } } }

6.5

=>

  • 0 O(n)

  • O(log^n)

  • [begin, end) v mid == (begin + end)/2
  • v < mid [begin,mid)
  • v > mid [mid + 1,end)
  • v == mid mid

<code-pre class="code-pre" id="pre-tjxD2m" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;">/** - * val arr -1 */ private static int indexOf(Integer[] arr,int val) { if(arr == null || arr.length == 0) return -1; int begin = 0; //end arr.length end - begin int end = arr.length; while (begin < end) { int mid = (begin + end) >> 1; if(val < arr[mid]) { end = mid; } else if(val > arr[mid]) { begin = mid + 1; } else { return mid; } } return -1; }</code-pre>

(Binary Search)

  • val val
  • 1 val
    • val 5 2
    • val 1 0
    • val 15 7
    • val 8 5

    • [begin,end) val mid == (begin + end)/2
    • val < mid [begin,mid)
    • val >= mid [mid + 1,end)
    • begin == end == x x

[

  • -
  • val arr
  • 1 val
private static int search(Integer[] arr,int val) { if(arr == null || arr.length == 0) return -1; int begin = 0; int end = arr.length; while (begin < end) { int mid = (begin + end) >> 1; if(val < arr[mid]) { end = mid; } else { begin = mid + 1; } } return begin; }</code-pre>

O(n^2)

public class InsertionSort<T extends Comparable<T>> extends Sort<T> { /** => */ @Override protected void sort() { for (int begin = 1; begin < array.length; begin++) { // //=> [0,i) insert(begin,search(begin)); } } /** source dest */ private void insert(int source,int dest) { //[dest,source) T val = array[source]; for (int i = source; i > dest; i--) { array[i] = array[i - 1]; } // array[dest] = val; } private int search(int index) { T val = array[index]; int begin = 0; int end = index; while (begin < end) { int mid = (begin + end) >> 1; if(cmp(val,array[mid]) < 0) { end = mid; } else { begin = mid + 1; } } return begin; } }

6.6

  • O(n^2) O(n)
  • O(1)

7. Merge Sort

7.1

  • 2
  • 2 1

[

7.2

merge

  • merge 2

  • merge 1 [begin,mid)

  • =>

  • =>

7.3
<code-pre class="code-pre" id="pre-fTBJPD" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;">@SuppressWarnings("unchecked") public class MergeSort<T extends Comparable<T>> extends Sort<T> { private T[] leftArr; @Override protected void sort() { leftArr = (T[]) new Comparable[array.length >> 1]; sort(0, array.length); } /** [begin,end) */ private void sort(int begin, int end) { if (end - begin < 2) return; int mid = (begin + end) >> 1; sort(begin, mid); sort(mid, end); merge(begin, mid, end); } /** [begin,mid) [mid,end) */ private void merge(int begin, int mid, int end) { int li = 0, le = mid - begin; int ri = mid, re = end; int ai = begin; // for (int i = 0; i < le; i++) { leftArr[i] = array[begin + i]; } // while (li < le) { // ri < re leftArr if (ri < re && cmp(array[ri],leftArr[li]) < 0) { array[ai++] = array[ri++]; } else {// array[ai++] = leftArr[li++]; } } } }</code-pre>
7.4

<code-pre class="code-pre" id="pre-kBDcFF" style="padding: 0px 0px 0px 10px; margin: 0px; position: relative; display: block;">T(n) = sort() + sort() + merge() => T(n) = T(n/2) + T(n/2) + O(n) => T(n) = 2T(n/2) + O(n) //sort() T T(n/2) T(n) O(n) T(1) = O(1) T(n)/n = T(n/2)/(n/2) + O(1) //S(n) = T(n)/n S(1) = O(1) S(n) = S(n/2) + O(1) = S(n/4) + O(2) = S(n/8) + O(3) = S( n/(2^k) ) + O(k) = S(1) + O(log^n) = O(lon^n) T(n) = n*S(n) = O(nlog^n) => O(nlog^n)</code-pre>

  • O(nlog^n)

  • O(n/2 + log^n) = O(n) n/2 log^n