algorithm-sort

排序

冒泡排序

public void bubbleSort(int[] arr) {
    int temp = 0, len = arr.length;
    for (int i = 0; i < len; ++i) {
        for (int j = len-1; j > i; --j) {
            if (arr[j] < arr[j-1]) {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

插入排序

public void insertSort(int[] arr) {
    int temp = 0, len = arr.length;
    for (int i = 0; i < len; ++i) {
        temp = arr[i];
        for (int j = i; j >= 0; --j) {
            if (j == 0 || temp > arr[j-1]) {
                arr[j] = temp;
                break;
            }
            else {
                arr[j] = arr[j-1];
            }
        }
    }
}

快速排序（非稳定排序）

public void swap(int[] arr, int left, int right) {
    int temp = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
}
// 单指针分割法
public int split(int[] arr, int left, int right) {
    int i = left;
    int temp = arr[left];
    for (int j = left+1; j <= right; ++j) {
        if (arr[j] < temp) {
            swap(arr, j, ++i);
        }
    }
    swap(arr, left, i);
    return i;
}
// 双指针分割法
public int partition(int[] arr, int left, int right) {
    int temp = arr[left];
    int i = left;
    int j = right;
    while (i < j) {
        // 写法1（这种写法区别是：在指针移动的过程中加入条件i<j,所以最终遍历结束条件只有i==j，而没有j<i，且不需要考虑i和j的边界情况
        // 但是，要注意要先执行--j的遍历,否则最终指针相聚的位置是在正确位置的右边，这样与left交换就会导致大值被放到了左边
        while (i < j && arr[j] >= temp) --j;
        while (i < j && arr[i] <= temp) ++i;
        swap(arr, i, j);
        if (i == j) swap(arr, left, j);
        // 写法2（本科数据结构课的写法）
        // while (i < right && arr[i] <= temp) ++i;
        // while (j > left && arr[j] >= temp) --j;
        // if (i < j) swap(arr, i, j);
        // else if (i == j) swap(arr, left, j);
        // else swap(arr, left, j);
    }
    return j;
}
// 快排主体
public void quickSort(int[] arr, int left, int right) {
    // int i = split(arr, left, right);
    int i = partition(arr, left, right);
    if (left < i-1) quickSort(arr, left, i-1);
    if (i+1 < right) quickSort(arr, i+1, right);
}

归并排序

public void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right-left+1];
    int tempIndex = 0;
    int i = left;
    int j = mid + 1;
    while (i <= mid && j <= right) {
        if (array[i] <= array[j]) temp[tempIndex++] = array[i++];
        else temp[tempIndex++] = array[j++];
    }
    while (i <= mid) temp[tempIndex++] = array[i++];
    while (j <= right) temp[tempIndex++] = array[j++];
    for (i = 0; i < temp.length; ++i) array[i+left] = temp[i];
}
// 归并排序主体
public void mergeSort(int[] array, int left, int right) {
    if (right > left) {
        int mid = left + (right - left) / 2;
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
}