排序算法函数的Java实现

排序是计算机科学的重要分支之一。排序算法是将杂乱无章的数据集合按照特定顺序重新排列的算法。排序算法可以通过比较、交换或者移动数据元素来实现排序。在实际开发中，我们经常需要对大量数据进行排序，那么排序算法的效率和正确性就成为了我们关注的重点。

在本篇文章中，我们将探讨常用的排序算法函数在Java语言中的实现，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序以及基数排序。这些算法函数在实现原理、算法复杂度、时间效率等方面各有不同。

1. 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，每次比较相邻的两个元素，如果逆序则交换，从而将较大的元素逐渐“浮”到数列的顶端，最终整个数列变得有序。

以下是冒泡排序算法的Java实现：

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

2. 选择排序

选择排序也是一种简单的排序算法，它的基本思想是每一轮选择一个最小（或最大）的元素放在已排好序的序列的末尾，直到全部元素都排好序。

以下是选择排序算法的Java实现：

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

3. 插入排序

插入排序是将未排序部分的元素逐个插入到已排序序列中的适当位置中，从而得到一个新的、更大的已排序序列的过程。插入排序算法分为直接插入排序和希尔排序。其中，直接插入排序是一种简单的排序算法，它的时间复杂度为O(n^2)。

以下是直接插入排序算法的Java实现：

public static void insertionSort(int[] array) {
    int n = array.length;
    for (int i = 1; i < n; i++) {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = key;
    }
}

希尔排序是插入排序的一种改进版本，通过将原数组分成若干个子序列进行排序，使得初始子序列基本有序，然后再逐渐减少子序列长度，直至子序列长度为1，完成排序操作。

以下是希尔排序算法的Java实现：

public static void shellSort(int[] array) {
    int n = array.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = array[i];
            int j;
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                array[j] = array[j - gap];
            }
            array[j] = temp;
        }
    }
}

4. 归并排序

归并排序是一种用于排序链表和数组的算法。归并排序算法采用分而治之的策略将原始数组分为较小的子数组，然后递归地排序这些子数组，并将排序好的子数组合并起来以获得原始数组的排序结果。

以下是归并排序算法的Java实现：

public static void mergeSort(int[] array, int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(array, low, mid);
        mergeSort(array, mid + 1, high);
        merge(array, low, mid, high);
    }
}
    
public static void merge(int[] array, int low, int mid, int high) {
    int[] temp = new int[array.length];
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (array[i] < array[j]) {
            temp[k++] = array[i++];
        } else {
            temp[k++] = array[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = array[i++];
    }
    while (j <= high) {
        temp[k++] = array[j++];
    }
    for (i = low; i <= high; i++) {
        array[i] = temp[i];
    }
}

5. 快速排序

快速排序是对冒泡排序的一种改进，它也采用分而治之的策略，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的元素都比另外一部分的元素小，然后再按照此方法对这两部分分别递归地进行排序，直到整个序列有序。

以下是快速排序算法的Java实现：

public static void quickSort(int[] array, int low, int high) {
    if (low < high) {
        int pivot = partition(array, low, high);
        quickSort(array, low, pivot - 1);
        quickSort(array, pivot + 1, high);
    }
}
    
public static int partition(int[] array, int low, int high) {
    int pivot = array[low];
    int i = low, j = high;
    while (i < j) {
        while (i < j && array[j] >= pivot) {
            j--;
        }
        if (i < j) {
            array[i++] = array[j];
        }
        while (i < j && array[i] < pivot) {
            i++;
        }
        if (i < j) {
            array[j--] = array[i];
        }
    }
    array[i] = pivot;
    return i;
}

6. 堆排序

堆排序（也称为选择排序）是一种选择性比较排序算法，它的时间复杂度是O(nlogn)。堆排序是利用堆这种数据结构而得以实现的，具体来说，堆是一棵有序二叉树，其中每个节点都满足父节点的值总是大于或等于其所有子节点的值（即它们的父节点总是比它们的值小）。堆排序算法利用这个性质来确定每个节点在堆中的位置，从而实现排序。

以下是堆排序算法的Java实现：

`

public static void heapSort(int[] array) {

int n = array.length;

for (int i = n / 2 - 1; i >= 0; i--) {

heapify(array, n, i);

}

for (int i = n - 1; i >= 0; i--) {

int temp = array[0];

array[0] = array[i];

array[i] = temp;

heapify(array, i, 0);

}

}

public static void