Algorithm

Chap01

prerequisite

generate random array

public static Integer[] gra(int n, int min, int max) {
    
    Integer[] arr = new Integer[n];
    for(int i = 0; i<n; i++) {
        arr[i] = new Integer((int)(Math.random() * (max - min + 1) + min));
        return arr;
    }
}

The bounds are inclusive, ie[min,max].And be precautionary that min must be less than max.

Chap02

selection sort

int n = arr.length;
for(int i = 0; i < n; i++) {
    // 寻找[i, n)区间里的最小值的索引
    int minIndex = i;
    for(int j = i + 1; j < n; j++) 
        if(arr[j] < arr[i])
            minIndex = j;
    swap(arr, i, minIndex);
}

improvement in efficiency

int left = 0; right = arr.length - 1;
while(left < right) {
    int minIndex = left;
    int maxIndex = right;
    
    if(arr[minIndex].compareTo(arr[maxIndex]) > 0)
        swap(arr, minIndex, maxIndex);
    
    for(int i = left + 1; i < right; i++) {
        if(arr[i].comareTo(arr[minIndex]) < 0)
            minIndex = i;
        else if(arr[i].compareTo(arr[maxIndex]) > 0)
            maxIndex = i;
    
    swap(arr, left, minIndex);
    swap(arr, right, maxIndex);
    
    left++;
    right--;
    }
}

在每一轮中, 可以同时找到当前未处理元素的最大值和最小值。

insertion sort

for(int i = 1; i < n; i++) {
    // 寻找arr[i]合适的插入位置
    for(int j = i; j > 0; j--) {
        // 某种程度上是循环继续的条件
        if(arr[j] < arr[j-1])
            swap(arr, j, j-1);
        else
            break;
    }
}

improvement in concision

for(int i = 1; i < n; i++) {
    // 寻找arr[i]合适的插入位置
    for(int j = i; j > 0 && arr[j] < arr[j-1]; j--) {
            swap(arr, j, j-1);
    }
}

插入排序可以提前终止，而选择排序必须遍历所有元素。
测试算法性能时注意使用相同的数组，运行时间的计算。

improvement in efficiency

for(int i = 1; i < n; i++) {
    Comparable e = arr[i];
    int j = i;
    for( ; j > 0 && arr[j-1].compareTo(e) > 0; j--) 
            arr[j] = arr[j-1];
    arr[j] = e;
}

交换操作开销较大，改换成赋值和移动。即寻找arr[i]正确的位置，寻找的过程中元素后移，找到了将arr[i]赋值即可。
插入排序对近乎有序的数组排序效果较好，对完全有序的数组排序的时间复杂度是O(n)级别的。

bubble sort

实现

优化

shell sort

以h递减序列的话，time complexity可以达到O(n^1.5)，是和插入排序一脉相承的。

继承
泛型
反射
包装

Chap03

merge sort

//V1.0
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
void merge(Comparable[] arr, int l, int mid, int r) {
    Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
    int i = l, j = mid + 1;
    for(int k = l; k < r; k++) {
        if(l > mid) {
            arr[k] = aux[j-l]; j++;
        } 
        else if(j > r) {
            arr[k] = aux[i-l]; i++;
        }
        else if((aux[i-l].compareTo(aux[j-l]) < 0) {
            arr[k] = aux[i-l]; i++;
        }
        else {
            arr[k] = aux[j-l]; j++;
        }
}
void sort(Comparable[] arr, int l, int r) {
    if(l >= r) return;
    int mid = (l+r)/2;
    sort(arr, l, mid);
    sort(arr, mid+1, r);
    merge(arr, l, mid, r);
}

优化1：限定归并条件if(arr[mid] > arr[mid+1])
优化2：防止递归到底，在数据较少时数据有序可能性更大，插入排序更有优势。

//V1.1
void insert(Comparable[] arr, int l, int r) {
    for(int i = l+1; i < r + 1; i++) {
        Comparable e = arr[i];
        int j = i;
        for(; j > 0 && arr[j-1].compareTo(e) > 0; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = e;
}
void merge(Comparable[] arr, int l, int mid, int r) {
    Comparable[] aux = Arrays.copyOfRange(arr, l, r+1);
    int i = l, j = mid + 1;
    for(int k = l; k < r; k++) {
        if(l > mid) {
            arr[k] = aux[j-l]; j++;
        } 
        else if(j > r) {
            arr[k] = aux[i-l]; i++;
        }
        else if((aux[i-l].compareTo(aux[j-l]) < 0) {
            arr[k] = aux[i-l]; i++;
        }
        else {
            arr[k] = aux[j-l]; j++;
        }
}
void sort(Comparable[] arr, int l, int r) {

    if(r - l <= 15) {
        insert(arr, l, r);
        return
    }
    
    int mid = (l+r)/2;
    sort(arr, l, mid);
    sort(arr, mid+1, r);
    
    if( arr[mid].compareTo(arr[mid+1]) > 0 )
        merge(arr, l, mid, r);
}

前面我们实现了自顶向下的归并排序，其中运用到了递归的思想，下面我们将从另一种角度自底向上重新进行实现，而这没有用到递归而是用到了迭代的思想。更重要的是，在这种方法中没有用到数组，它可以对更广泛的如链表等结构进行排序。

//V2.0
void mergeSortBU(Comparable[] arr, int n) {
    for(int size = 1; i < n; size += size) 
        for(int i = 0; i < n; i += size + size) 
            merge(arr, i, i+size-1, min(i+size+siize-1, n-1));
}