冒泡排序（Bubble Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    bubbleSort(array);
    System.out.println(Arrays.toString(array));
}
public static void bubbleSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }
    int length = array.length;
    // 外层循环控制比较轮数i
    for (int i = 0; i < length; i++) {
        // 内层循环控制每一轮比较次数，每进行一轮排序都会找出一个较大值
        // (array.length - 1)防止索引越界，(array.length - 1 - i)减少比较次数
        for (int j = 0; j < length - 1 - i; j++) {
            // 前面的数大于后面的数就进行交换
            if (array[j] > array[j + 1]) {
                int temp = array[j + 1];
                array[j + 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

选择排序（Selection Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    // 只需要修改成对应的方法名就可以了
    selectionSort(array);
    System.out.println(Arrays.toString(array));
}
public static void selectionSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }
    int length = array.length;
    for (int i = 0; i < length - 1; i++) {
        // 保存最小数的索引
        int minIndex = i;
        for (int j = i + 1; j < length; j++) {
            // 找到最小的数
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 交换元素位置
        if (i != minIndex) {
            swap(array, minIndex, i);
        }
    }
}
/**
 * Description: 交换元素位置
 */
private static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

插入排序（Insertion Sort）

    public static void main(String[] args) {
        int[] arr = {5, 3, 4, 2, 1};

        for (int i = 1; i < arr.length ; i++) {
            int insertVal = arr[i];
            int insertIndex = i - 1; //即arr[1]的前面这个数的下标
            // 如果要插入的元素比当前元素小,就接着往前查找
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
             // 比要插入的元素大,就交换一下位置,  比如说 5比3大,就交换位置为 3 ,5
                arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
                insertIndex--;
            }
            arr[insertIndex + 1] = insertVal;

            System.out.println("第" + i + "轮插入");
            System.out.println(Arrays.toString(arr));

        }
    }

希尔排序（Shell Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    // 只需要修改成对应的方法名就可以了
    shellSort(array);

    System.out.println(Arrays.toString(array));
}

public static void shellSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }

    int length = array.length;

    // temp为临时变量，gap增量默认是长度的一半，每次变为之前的一半，直到最终数组有序
    int temp, gap = length / 2;

    while (gap > 0) {
        for (int i = gap; i < length; i++) {
            // 将当前的数与减去增量之后位置的数进行比较，如果大于当前数，将它后移
            temp = array[i];
            int preIndex = i - gap;

            while (preIndex >= 0 && array[preIndex] > temp) {
                array[preIndex + gap] = array[preIndex];
                preIndex -= gap;
            }

            // 将当前数放到空出来的位置
            array[preIndex + gap] = temp;

        }
        gap /= 2;
    }
}

归并排序（Merge Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    // 只需要修改成对应的方法名就可以了
    mergeSort(array);

    System.out.println(Arrays.toString(array));
}


public static void mergeSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }

    sort(array, 0, array.length - 1);
}

private static void sort(int[] array, int left, int right) {
    if (left == right) {
        return;
    }
    int mid = left + ((right - left) >> 1);
    // 对左侧子序列进行递归排序
    sort(array, left, mid);
    // 对右侧子序列进行递归排序
    sort(array, mid + 1, right);
    // 合并
    merge(array, left, mid, right);
}

private static void merge(int[] array, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = 0;
    int p1 = left;
    int p2 = mid + 1;
    // 比较左右两部分的元素，哪个小，把那个元素填入temp中
    while (p1 <= mid && p2 <= right) {
        temp[i++] = array[p1] < array[p2] ? array[p1++] : array[p2++];
    }
    // 上面的循环退出后，把剩余的元素依次填入到temp中
    // 以下两个while只有一个会执行
    while (p1 <= mid) {
        temp[i++] = array[p1++];
    }
    while (p2 <= right) {
        temp[i++] = array[p2++];
    }
    // 把最终的排序的结果复制给原数组
    for (i = 0; i < temp.length; i++) {
        array[left + i] = temp[i];
    }
}

快速排序（Quick Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    // 只需要修改成对应的方法名就可以了
    quickSort(array);

    System.out.println(Arrays.toString(array));
}


public static void quickSort(int[] array) {
    quickSort(array, 0, array.length - 1);
}


private static void quickSort(int[] array, int left, int right) {
    if (array == null || left >= right || array.length <= 1) {
        return;
    }
    int mid = partition(array, left, right);
    quickSort(array, left, mid);
    quickSort(array, mid + 1, right);
}


private static int partition(int[] array, int left, int right) {
    int temp = array[left];
    while (right > left) {
        // 先判断基准数和后面的数依次比较
        while (temp <= array[right] && left < right) {
            --right;
        }
        // 当基准数大于了 arr[left]，则填坑
        if (left < right) {
            array[left] = array[right];
            ++left;
        }
        // 现在是 arr[right] 需要填坑了
        while (temp >= array[left] && left < right) {
            ++left;
        }
        if (left < right) {
            array[right] = array[left];
            --right;
        }
    }
    array[left] = temp;
    return left;
}

堆排序（Heap Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    // 只需要修改成对应的方法名就可以了
    heapSort(array);

    System.out.println(Arrays.toString(array));
}


public static void heapSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }

    int length = array.length;

    //1.构建大顶堆
    for (int i = length / 2 - 1; i >= 0; i--) {
        //从第一个非叶子结点从下至上，从右至左调整结构
        adjustHeap(array, i, length);
    }
    //2.调整堆结构+交换堆顶元素与末尾元素
    for (int j = length - 1; j > 0; j--) {
        //将堆顶元素与末尾元素进行交换
        swap(array, 0, j);
        //重新对堆进行调整
        adjustHeap(array, 0, j);
    }

}


private static void adjustHeap(int[] array, int i, int length) {
    //先取出当前元素i
    int temp = array[i];
    //从i结点的左子结点开始，也就是2i+1处开始
    for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
        //如果左子结点小于右子结点，k指向右子结点
        if (k + 1 < length && array[k] < array[k + 1]) {
            k++;
        }
        //如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
        if (array[k] > temp) {
            array[i] = array[k];
            i = k;
        } else {
            break;
        }
    }
    //将temp值放到最终的位置
    array[i] = temp;
}


private static void swap(int[] array, int a, int b) {
    int temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

计数排序（Counting Sort）

public static void main(String[] args) {
    int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
    // 只需要修改成对应的方法名就可以了
    countingSort(array);

    System.out.println(Arrays.toString(array));
}


public static void countingSort(int[] array) {
    if (array == null || array.length <= 1) {
        return;
    }

    int length = array.length;

    int max = array[0];
    int min = array[0];
    for (int i = 0; i < length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
        if (min > array[i]) {
            min = array[i];
        }
    }
    // 最大最小元素之间范围[min, max]的长度
    int offset = max - min + 1;
    // 1. 计算频率，在需要的数组长度上额外加1
    int[] count = new int[offset + 1];
    for (int i = 0; i < length; i++) {
        // 使用加1后的索引，有重复的该位置就自增
        count[array[i] - min + 1]++;
    }
    // 2. 频率 -> 元素的开始索引
    for (int i = 0; i < offset; i++) {
        count[i + 1] += count[i];
    }

    // 3. 元素按照开始索引分类，用到一个和待排数组一样大临时数组存放数据
    int[] aux = new int[length];
    for (int i = 0; i < length; i++) {
        // 填充一个数据后，自增，以便相同的数据可以填到下一个空位
        aux[count[array[i] - min]++] = array[i];
    }
    // 4. 数据回写
    for (int i = 0; i < length; i++) {
        array[i] = aux[i];
    }
}