盘点几种常见的Java排序算法

排序算法是程序员日常开发中经常使用的基本算法之一。Java是目前最流行的编程语言之一，因此掌握Java的排序算法对于程序员来说是必须的。

本篇文章将会介绍几种Java常见的排序算法，包括冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序和计数排序，一步步讲解其中的实现原理和Java代码实现。

冒泡排序

冒泡排序是一种基本的排序算法，它的实现主要通过交换两个相邻元素的位置，并重复这个过程，直到列表排好序为止。

以下是Java的冒泡排序代码示例：

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

选择排序

选择排序是另一种基本的排序算法，它的实现与冒泡排序很相似，只不过它是通过在未排序的列表中选择最小（或最大）元素，并将其移到已排序的列表的末尾来排序整个列表。

以下是Java的选择排序代码示例：

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

插入排序

插入排序基本思想是将未排序的元素插入到已排序的列表中，对于插入操作，需要将已排序元素中的所有大于该元素的元素向右移动一个位置，并将该元素插入到空出的位置上。

以下是Java的插入排序代码示例：

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

归并排序

归并排序是一种递归排序算法，它的基本思想是将一个大列表分成两个小列表，对这两个小列表分别进行排序后，再将这两个小列表合并成一个有序的列表。

以下是Java的归并排序代码示例：

public static 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);
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[arr.length];
    int i = left;
    int j = mid + 1;
    int t = 0;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];
        } else {
            temp[t++] = arr[j++];
        }
    }
    while (i <= mid) {
        temp[t++] = arr[i++];
    }
    while (j <= right) {
        temp[t++] = arr[j++];
    }
    t = 0;
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

快速排序

快速排序是一种基于分治的排序算法，它的基本思想是通过选定一个基准元素，将列表分成两个子列表，其中左子列表所有的元素小于或等于基准元素，右子列表所有的元素大于基准元素，然后递归地应用该算法，直到所有的子列表都有序。

以下是Java的快速排序代码示例：

public static void quickSort(int[] arr, int left, int right) {
    int i, j, base, temp;
    if (left > right) {
        return;
    }
    base = arr[left];
    i = left;
    j = right;
    while (i != j) {
        while (arr[j] >= base && i < j) {
            j--;
        }
        while (arr[i] <= base && i < j) {
            i++;
        }
        if (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    arr[left] = arr[i];
    arr[i] = base;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

堆排序

堆排序是一种基于树的排序算法，它的基本思想是将列表中的元素构造成一个最大堆（或最小堆），然后依次将堆的根节点取出，得到一个有序列表。

以下是Java的堆排序代码示例：

public static void heapSort(int[] arr) {
    int length = arr.length;
    //构建最大堆
    for (int i = length / 2 - 1; i >= 0; i--) {
        heapify(arr, length, i);
    }
    //依次将最大值放在堆的末尾
    for (int i = length - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

public static void heapify(int[] arr, int length, int i) {
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int largest = i;
    if (left < length && arr[left] > arr[largest]) {
        largest = left;
    }
    if (right < length && arr[right] > arr[largest]) {
        largest = right;
    }
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, length, largest);
    }
}

计数排序

计数排序是一种基于计数的排序算法，它的实现通过遍历列表中的元素，统计小于等于该元素的个数，然后将该元素放在排序列表中对应的位置上。

以下是Java的计数排序代码示例：

public static void countSort(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    int[] temp = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
        temp[arr[i]]++;
    }
    int j = 0;
    for (int i = 0; i <= max; i++) {
        while (temp[i]-- > 0) {
            arr[j++] = i;
        }
    }
}

通过以上几种排序算法的介绍，读者应该能够对Java中的排序算法有一个更清晰的认识，掌握这些算法对于提高程序员的编程能力、提高代码质量是非常有帮助的。