Java各种排序

快速排序

我们会以最左边的元素作为标准，

从高位取值和他比较，找到高位比他小的元素和low互换，如果比他大则坐标减一继续找

从低位取值找到比他大的元素，和high互换填补到high的位置，如果比他小则继续找

直到low = high循环结束，此时low或者high的坐标就是standard的坐标，返回之后继续递归

public static int parition(int[] arr, int low, int high) {
    int standard = arr[low];
    while (high > low) {
        while (high > low && arr[high] >= standard) {
            high--;
        }
        arr[low] = arr[high];
        while (high > low && arr[low] <= standard) {
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = standard;
    return low;
}
这里需要注意：必须要检查from要小于等于end
public static void quickSort(int[] arr, int from, int end) {
    if (arr.length <= 1 || from >= end) {
        return;
    }
    int partition = parition(arr, from, end);
    quickSort(arr, from, partition - 1);
    quickSort(arr, partition + 1, end);
}

归并排序

主体思想是先把数组分为不可分的整体每个整体看作一个数组，然后数组合并排序然后再合并最终变成一整个排序好的数组。但是直接这样可能不太好理解。

可以先用二分的方式把数组分成两个部分，然后再二分，直到不可分，然后merge

public static void mergeSort(int[] arr) {
    if (arr.length < 2) {
        return;
    }
    dichotomy(arr, 0, arr.length - 1);
}
public static void dichotomy(int[] arr, int low, int high) {
    if (high <= low) {
        return;
    }
    int mid = low + (high - low) / 2;
    // 继续二分
    dichotomy(arr, low, mid);
    dichotomy(arr, mid + 1, high);
    merge(arr, low, mid, high);
}

当有任意一方到头了，则另一方全部灌入目标数组

public static void merge(int[] arr, int low, int mid, int high) {
    int leftIndex = low;
    int rightIndex = mid + 1;
    int[] result = new int[high - low + 1];
    for(int i = 0; i < result.length; i++) {
        // 两边都还没到头则互相比较
        if (leftIndex <= mid && rightIndex <= high) {
            if (arr[leftIndex] <= arr[rightIndex]) {
                result[i] = arr[leftIndex];
                leftIndex++;
            } else {
                result[i] = arr[rightIndex];
                rightIndex++;
            }
        } else if (leftIndex <= mid) {
            // 右边到头了
            result[i] = arr[leftIndex];
            leftIndex++;
        } else {
            // 左边到头了
            result[i] = arr[rightIndex];
            rightIndex++;
        }
    }
// 目标数组归入原数组
    for(int i = 0; i < result.length;i++) {
        arr[i + low] = result[i];
    }
}

堆排序

通过大根堆的性质，把最大值放到堆顶，然后和数组最后一位互换，堆长度--

整个过程堆长度要始终传入。

数组元素i的左右堆元素分别为 2*i + 1，2*i+2

数组最大非叶子节点为(length - 2)/2

public static void heapsort(int[] arr) {
    if (arr.length < 2) {
        return;
    }
    int heapLen = arr.length;
    for (int i = arr.length - 1; i > 0; i--) {
        findBiggestHeap(arr, heapLen);
        // 此时和大根堆的0位置互换
        swap(arr, 0, i);
        heapLen--;
    }
}

public static void findBiggestHeap(int[] arr, int heapLen) {
    int notLeafNode = (heapLen - 2) / 2;
    int leftNode, rightMode;
    for(int i = notLeafNode; i >= 0;i--) {
        leftNode = i*2 + 1;
        rightMode = leftNode + 1;
        leftRightCompare(arr, leftNode, rightMode, heapLen, i);
    }
}
public static void downAdjust(int[] arr, int i, int heapLen) {
    int leftNode = i*2 + 1;
    int rightMode = leftNode + 1;
    leftRightCompare(arr, leftNode, rightMode, heapLen, i);
}

public static void leftRightCompare(int[] arr, int leftNode, int rightMode, int heapLen, int i) {
    if (rightMode < heapLen) {
        // 有两个节点
        if (arr[leftNode] > arr[i] && arr[leftNode] >= arr[rightMode]) {
            // 左节点最大
            swap(arr, leftNode, i);
            // i节点下放之后还得处理
            downAdjust(arr, leftNode, heapLen);
        } else if (arr[rightMode] > arr[i] && arr[rightMode] > arr[leftNode]) {
            // 右节点最大
            swap(arr, rightMode, i);
            // i节点下放之后还得处理
            downAdjust(arr, rightMode, heapLen);
        }
    } else if (leftNode < heapLen) {
        // 仅有左边的节点
        if (arr[leftNode] > arr[i]) {
            swap(arr, leftNode, i);
            // i节点下放之后还得处理
            downAdjust(arr, leftNode, heapLen);
        }
    }
}

半插入排序

我的半插入排序习惯从第三位开始排序，即默认前两个位置已经有序

public static void dInsertSort(int[] arr) {
    if (arr.length < 2) {
        return;
    }
    if(arr[0] > arr[1]) {
        swap(arr, 0, 1);
    }
    int mid, low, high, tmp;
    for(int i = 2; i < arr.length; i++) {
        if (arr[i] >= arr[i-1]) {
            continue;
        }
        low = 0;
        high = i;
        mid = low + (high - low)/2;
        while (high >= low) {
            if (arr[i] > arr[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
            mid = low + (high - low)/2;
        }
        // 当low比high要大的时候
        // 移动数组，1，4，5，3 => 1,4,4,5
        tmp = arr[i];
        moveArr(arr, low, i);
        // 1,4,4,5 -> 1,3,4,5
        arr[low] = tmp;
    }
}

public static void moveArr(int[] arr, int low, int to) {
    for(int i = to; i > low; i--) {
        arr[i] = arr[i - 1];
    }
}

桶排序

希尔排序

public static void shell(int[] arr) {
    int gap = arr.length >> 1;
    while (gap >= 1) {
        shell1(arr, gap);
        if(gap == 1) {
            break;
        }
        gap = gap >> 1;
    }
}
public static void shell1(int[] arr, int gap) {
    for(int i = 0; i < gap; i++) {
        isGap(arr, gap);
    }
}
public static void isGap(int[] arr, int gap) {
    for(int i = gap; i < arr.length; i += gap) {
        for(int j = i; j > 0; j -= gap) {
            if(arr[j - gap] > arr[j]) {
                swap(arr, j - gap, j);
            }
        }
    }
}