java最快的排序算法-ag捕鱼王app官网

本文将介绍两种最快的排序算法并用 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; iif(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; iif(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// doing addition of frequency
        for (int i=1; i1];
        }
        // 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" ");
        }
    }
}

输出:

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; ifor (int j=0; j1   j];
        int a = 0, b = 0;
        // merging temp arrays to the original array
        int k = left;
        while (aif (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// if any elements are left in rightarray, clone it to the original array
        while (bstatic void mergesort(int arr[], int left, int right)
    {
        if (left// 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" ");
        }
    }
}

输出:

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 中最快的算法之一。 此外，为了克服计数排序的局限性，我们学习了合并排序，它适用于任何输入范围。