迹忆客 专注技术分享

本文将介绍两种最快的排序算法并用 Java 编写它们的代码。

第一种技术是计数排序，它有一些局限性。 因此，我们还将介绍合并排序算法。

Java中的计数排序算法

当数组元素在特定范围内时，计数排序算法是我们可以使用的最快排序技术之一。 它不是基于比较的排序技术，而是通过计算和存储每个数组元素的频率来对数组进行排序。

简单来说，它使用散列对数组进行排序。

用户应遵循以下算法进行计数排序。

• 找出数组的最大和最小元素。
• 接下来，使用最大和最小元素找到数组的范围，并创建一个大小范围的新 freq 数组来存储每个元素的频率。
• 迭代原始数组并将每个元素的频率存储在 freq 数组中。
• 通过添加频率，计算每个元素的累积频率。
• 从末尾开始迭代原始数组，并使用 freq 数组将每个元素放入其排序位置。
• 将result中所有排序后的元素存储到原数组中，使原数组排序。

示例代码：

class CountingSort{
    // function to find the maximum from the array
    static int findMax(int arr[]) {
    int maxi = arr[0];
    for(int i = 1; i<arr.length; i++) {
        if(arr[i]>maxi)
            maxi = arr[i];
    }
    return maxi; // return maximum
    }
    //  function to find the minimum from the array
    static int findMin(int arr[]) {
    int mini = arr[0];
    for(int i=1; i<arr.length; i++) {
       if(arr[i]<mini)
            mini = arr[i];
    }
    return mini; // return minimum
    }
    static void cntSort(int[] arr)
    {
        int maxi = findMax(arr);
        int mini = findMin(arr);
        //     getting range from maximum and minimum elements of the array
        int range = maxi - mini + 1;
        //     creating the array to store the frequency of elements
        int freq[] = new int[range];
        //     resultant array
        int result[] = new int[arr.length];
        //     counting frequency of elements and storing it to freq array
        for (int i=0; i<arr.length; i++) {
            freq[arr[i] - mini]++;
        }
        // Doing addition of frequency
        for (int i=1; i<freq.length; i++) {
            freq[i] += freq[i - 1];
        }
        // Putting every element of arr to its correct place based on the freq array
        for (int i=arr.length - 1; i>=0; i--) {
            result[freq[arr[i] - mini] - 1] = arr[i];
            freq[arr[i] - mini]--;
        }
       // Make arr array sorted by assigning elements from the result array
        for (int i = 0; i < arr.length; i++) {
            arr[i] = result[i];
        }
    }

    public static void main(String[] args)
    {
        int[] arr = { 10, 20, -2, -4, 3, 40, 50, 30, 20, 10 };
        cntSort(arr);
        System.out.println("Sorted Array using counting sort is ");
        for (int a=0; a<arr.length; a++) {
            System.out.print(arr[a] + " ");
        }
    }
}

输出:

Sorted Array is -4 -2 3 10 10 20 20 30 40 50

Java计数排序算法的时间复杂度

计数排序的时间复杂度是线性顺序的，因为我们使用单个 for 循环。

Java计数排序算法的空间复杂度

由于我们使用临时数组来存储已排序的元素，因此计数排序的空间复杂度为 O(n)。

Java中计数排序算法的局限性

毫无疑问，计数排序技术是对数组元素进行排序的最快算法，但它有一些局限性。

用户可以想象一下数组长度非常小的场景，而输入范围太大，比如数百万。 在这种情况下，即使是冒泡排序也能表现得更好。

因此，当输入范围较小时，用户可以使用它在线性时间内对数组进行排序。

Java中的归并排序算法

为了克服计数排序的局限性，用户可以使用合并排序技术。

归并排序算法遵循分而治之的方法。 首先，它将数组分成两半，对其进行排序，然后合并排序后的数组。

要逐步学习完整的算法，用户可以按照以下步骤操作。

• 找到数组的中点。
• 对数组的第一部分和第二部分递归调用 mergeSort() 函数。
• 调用 merge() 函数合并数组。
• 在 merge() 函数中，创建两个与数组的两个部分大小相同的临时数组，并将数组元素存储到相应的临时数组中。
• 迭代临时数组，直到两个数组都有未排序的元素，从两个数组中找到最小元素，将其存储在原始数组中，然后继续移动。
• 如果 LeftArray 中还有剩余元素，则将它们存储到原始数组中，并对 RightArray 执行相同的操作。

示例代码：

class Test {
  // function to merge two sorted arrays
    static void merge(int arr[], int left, int mid, int right)
    {
        // sizes for temp arrays
        int n1 = mid - left + 1;
        int n2 = right - mid;
        // temp arrays
        int LeftArray[] = new int[n1];
        int RigthArray[] = new int[n2];
        // clone data to temp arrays
        for (int i=0; i<n1; ++i)
            LeftArray[i] = arr[left + i];
        for (int j=0; j<n2; ++j)
            RigthArray[j] = arr[mid + 1 + j];
        int a = 0, b = 0;
        // merging temp arrays to the original array
        int k = left;
        while (a<n1 && b<n2) {
            if (LeftArray[a] <= RigthArray[b]) {
                arr[k] = LeftArray[a];
                a++;
            }
            else {
                arr[k] = RigthArray[b];
                b++;
            }
            k++;
        }
        // If any elements are left in LeftArray, clone it to the original array
        while (a<n1) {
            arr[k] = LeftArray[a];
            a++;
            k++;
        }
        // If any elements are left in RightArray, clone it to the original array
        while (b<n2) {
            arr[k] = RigthArray[b];
            b++;
            k++;
        }
    }
    static void mergeSort(int arr[], int left, int right)
    {
        if (left<right) {
            // Find the mid of the array using the left and right
            int mid = left + (right - left) / 2;
            // sort the first half of the array
            mergeSort(arr, left, mid);
             // sort the second half of the array
            mergeSort(arr, mid + 1, right);
            // sort both parts of the array and merge it
            merge(arr, left, mid, right);
        }
    }
    public static void main(String args[])
    {
        int[] arr = { 10, 201, -22121, -412, 3, 212121, 50, 30, 20, 1021212 };
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array using merge sort is");
        for (int a=0; a<arr.length; a++) {
            System.out.print(arr[a] + " ");
        }
    }
}

输出:

Sorted array is -22121 -412 3 10 20 30 50 201 212121 1021212

Java 归并排序算法的时间复杂度

mergeSort() 的时间复杂度为 O(nlogn)，其中 n 是数组的长度。 这里，merge() 函数的时间复杂度为 O(n)，mergeSort() 函数的时间复杂度为 O(logn)，因为我们对数组的每半部分进行递归调用。

Java 归并排序算法的空间复杂度

合并排序的空间复杂度为 O(n)，因为我们使用两个临时数组来存储未排序的元素。

在本文中，我们通过示例代码逐步学习了计数排序算法，这是 Java 中最快的算法之一。 此外，为了克服计数排序的局限性，我们学习了合并排序，它适用于任何输入范围。