Java算法6种排序小结

本文主要讲解Java中常用的6种排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序。下面对每个算法进行详细介绍。

冒泡排序

冒泡排序是一种简单的排序算法，它的核心思想是将相邻的元素进行两两比较，根据大小关系进行交换，一直重复这个过程，直到所有元素都有序为止。

示例代码：

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

选择排序

选择排序是一种简单的排序算法，它的核心思想是在待排序的元素中选择最小（或最大）的元素，放在已排序序列的起始位置，然后从剩余未排序的元素中继续选择最小（或最大）的元素，放到已排序序列的末尾，直到所有元素都排序完成。

示例代码：

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

插入排序

插入排序是一种简单的排序算法，它的核心思想是将待排序的元素插入到已排序序列中的合适位置，一开始已排序序列只有一个元素，然后把待排序序列中的元素一个一个插入到已排序序列中，直到所有元素都排序完成。

示例代码：

public void insertionSort(int[] arr) {
    int len = arr.length;
    int preIndex, current;
    for (int i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while (preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

快速排序

快速排序是一种分治算法，它通过一趟排序将待排序序列分成独立的两部分，其中一部分所有元素都比另外一部分的所有元素都小，然后继续对这两部分分别进行快速排序，递归此过程，直到序列有序为止。

示例代码：

public void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
}

private int partition(int[] arr, int left, int right) {
    int pivot = left; // 取第一个元素作为基准值
    int index = pivot + 1;
    for (int i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, index, i);
            index++;
        }
    }
    swap(arr, pivot, index - 1);
    return index - 1;
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

归并排序

归并排序是采用分治法的一个非常典型的应用。其算法核心是将原始序列划分为多个子序列，直到每个子序列只有一个元素，然后进行两两归并，将划分后的序列逐个归并成为有序的序列。

示例代码：

public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

private void merge(int[] arr, int left, int mid, int right) {
    int[] tempArr = new int[arr.length];
    int tempIndex = left;
    int leftIndex = left;
    int rightIndex = mid + 1;
    while (leftIndex <= mid && rightIndex <= right) {
        if (arr[leftIndex] <= arr[rightIndex]) {
            tempArr[tempIndex++] = arr[leftIndex++];
        } else {
            tempArr[tempIndex++] = arr[rightIndex++];
        }
    }
    while (leftIndex <= mid) {
        tempArr[tempIndex++] = arr[leftIndex++];
    }
    while (rightIndex <= right) {
        tempArr[tempIndex++] = arr[rightIndex++];
    }
    for (int i = left; i <= right; i++) {
        arr[i] = tempArr[i];
    }
}

堆排序

堆排序是一种树形选择排序，它的核心思想是将待排序序列构建成一个大顶堆或小顶堆，然后按照堆的性质依次取出堆顶元素，最终得到一个有序序列。

示例代码：

public void heapSort(int[] arr) {
    int len = arr.length;
    // 构建大顶堆
    for (int i = len / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, len);
    }
    // 提取堆顶元素，交换并调整堆结构，再次构建大顶堆，重复此过程直到堆元素只剩一个
    for (int i = len - 1; i >= 0; i--) {
        swap(arr, 0, i);
        maxHeapify(arr, 0, i);
    }
}

private void maxHeapify(int[] arr, int i, int len) {
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if (left < len && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        swap(arr, i, largest);
        maxHeapify(arr, largest, len);
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

以上就是Java中常用的6种排序算法的详细介绍。了解这些排序算法的原理和实现方式有助于我们更好地理解代码，提高自己的编程能力。