# 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");

void execute();
}

title = (title == null) ? "" : (" " + title + " ");
System.out.println(title);
System.out.println(" " + fmt.format(new Date()));
long begin = System.currentTimeMillis();
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.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.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);
}
}

}
```

• O(n^2) O(1)

=>

# 5. Heap Sort

• 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;
}
}
```

• 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.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;
}
}
```

• 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