Java 随机生成数据并使用冒泡排序、选择排序、插入排序和合并排序进行排序

本文将介绍如何使用 Java 语言编程随机生成 10000 个实数，并将这些实数存储在数组中。随后，我们将使用四种常见的排序算法对这些数据进行排序，并提供伪代码和实际代码实现。

1. 随机生成数据

首先，我们需要使用 Java 代码随机生成 10000 个实数。可以使用 java.util.Random 类来实现。

import java.util.Random;

public class SortExample {

    public static void main(String[] args) {
        // 生成 10000 个随机实数
        double[] array = new double[10000];
        Random random = new Random(); 
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextDouble(); // 生成 0 到 1 之间的随机数
        }
        // ... 以下代码用于排序 ...
    }
}

2. 排序算法

我们将使用以下四种排序算法对数据进行排序：

• 冒泡排序 (Bubble Sort)
• 选择排序 (Selection Sort)
• 插入排序 (Insertion Sort)
• 自底向上的合并排序 (Bottom-Up Merge Sort)

2.1 冒泡排序 (Bubble Sort)

冒泡排序是一种简单的排序算法，每次比较相邻的两个元素，如果顺序不对则交换。

伪代码：

冒泡排序(array):
    n = array.length
    for i from 0 to n-1:
        for j from 0 to n-i-1:
            if array[j] > array[j+1]:
                swap(array[j], array[j+1])

实际代码：

public static void bubbleSort(double[] 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]) {
                // 交换两个元素
                double temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

2.2 选择排序 (Selection Sort)

选择排序是一种简单的排序算法，每次从未排序的部分选择最小的元素，放到已排序部分的末尾。

伪代码：

选择排序(array):
    n = array.length
    for i from 0 to n-1:
        minIndex = i
        for j from i+1 to n-1:
            if array[j] < array[minIndex]:
                minIndex = j
        swap(array[i], array[minIndex])

实际代码：

public static void selectionSort(double[] array) {
    int n = array.length;
    for (int i = 0; i < n-1; i++) {
        int minIndex = i;
        for (int j = i+1; j < n; j++) {
            if (array[j] < array[minIndex]) {
                minIndex = j;
            }
        }
        // 交换两个元素
        double temp = array[i];
        array[i] = array[minIndex];
        array[minIndex] = temp;
    }
}

2.3 插入排序 (Insertion Sort)

插入排序是一种简单的排序算法，将未排序的元素逐个插入到已排序的部分中。

伪代码：

插入排序(array):
    n = array.length
    for i from 1 to n-1:
        key = array[i]
        j = i-1
        while j >= 0 and array[j] > key:
            array[j+1] = array[j]
            j--
        array[j+1] = key

实际代码：

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

2.4 自底向上的合并排序 (Bottom-Up Merge Sort)

自底向上的合并排序是一种归并排序的变体，将数组分为小块进行排序，然后逐步合并。

伪代码：

自底向上的合并排序(array):
    n = array.length
    for blockSize from 1 to n-1:
        for start from 0 to n-blockSize-1 step blockSize*2:
            mid = start + blockSize-1
            end = min(start + blockSize*2-1, n-1)
            merge(array, start, mid, end)

合并(array, start, mid, end):
    n1 = mid - start + 1
    n2 = end - mid
    left = new double[n1]
    right = new double[n2]
    for i from 0 to n1-1:
        left[i] = array[start + i]
    for j from 0 to n2-1:
        right[j] = array[mid + 1 + j]
    i = 0, j = 0, k = start
    while i < n1 and j < n2:
        if left[i] <= right[j]:
            array[k] = left[i]
            i++
        else:
            array[k] = right[j]
            j++
        k++
    while i < n1:
        array[k] = left[i]
        i++
        k++
    while j < n2:
        array[k] = right[j]
        j++
        k++

实际代码：

public static void mergeSort(double[] array) {
    int n = array.length;
    for (int blockSize = 1; blockSize < n; blockSize *= 2) {
        for (int start = 0; start < n-blockSize; start += blockSize*2) {
            int mid = start + blockSize-1;
            int end = Math.min(start + blockSize*2-1, n-1);
            merge(array, start, mid, end);
        }
    }
}

private static void merge(double[] array, int start, int mid, int end) {
    int n1 = mid - start + 1;
    int n2 = end - mid;
    double[] left = new double[n1];
    double[] right = new double[n2];
    for (int i = 0; i < n1; i++) {
        left[i] = array[start + i];
    }
    for (int j = 0; j < n2; j++) {
        right[j] = array[mid + 1 + j];
    }
    int i = 0, j = 0, k = start;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {
            array[k] = left[i];
            i++;
        } else {
            array[k] = right[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        array[k] = left[i];
        i++;
        k++;
    }
    while (j < n2) {
        array[k] = right[j];
        j++;
        k++;
    }
}

3. 使用示例

以下是使用以上代码对随机生成的数组进行排序的示例：

import java.util.Random;

public class SortExample {

    public static void main(String[] args) {
        // 生成 10000 个随机实数
        double[] array = new double[10000];
        Random random = new Random(); 
        for (int i = 0; i < array.length; i++) {
            array[i] = random.nextDouble(); // 生成 0 到 1 之间的随机数
        }

        // 使用不同的排序算法进行排序
        double[] bubbleSortedArray = array.clone();
        bubbleSort(bubbleSortedArray);
        System.out.println("冒泡排序后：" + Arrays.toString(bubbleSortedArray));

        double[] selectionSortedArray = array.clone();
        selectionSort(selectionSortedArray);
        System.out.println("选择排序后：" + Arrays.toString(selectionSortedArray));

        double[] insertionSortedArray = array.clone();
        insertionSort(insertionSortedArray);
        System.out.println("插入排序后：" + Arrays.toString(insertionSortedArray));

        double[] mergeSortedArray = array.clone();
        mergeSort(mergeSortedArray);
        System.out.println("合并排序后：" + Arrays.toString(mergeSortedArray));
    }

    // ... 排序算法的代码 ...
}

以上代码会先随机生成 10000 个实数，然后使用四种排序算法分别对其进行排序，并将排序后的结果输出到控制台。

4. 总结

本文介绍了使用 Java 语言生成随机数据并使用四种常见的排序算法进行排序。通过本文，您应该能够理解这些排序算法的原理，以及如何使用 Java 代码实现它们。希望本文能够帮助您更好地理解和应用排序算法。