案例3-数组排序

Csshry

138人浏览 · 2026-06-04 10:37:41

Csshry · 2026-06-04 10:37:41 发布

1、冒泡排序

在Java程序设计中，排序是一个常见的任务，它涉及将一组数据按照某种顺序重新排列。以下是一个简单的Java排序案例，它使用了冒泡排序算法来对一个整数数组进行排序。冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复进行的，直到没有再需要交换的元素为止，这意味着该数列已经排序完成。

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

public class BubbleSort {

// 冒泡排序算法的实现  

public static void bubbleSort(int[] array) {  

    int n = array.length;  

    boolean swapped;  

    // 外层循环控制排序的轮数  

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

        swapped = false;  

        // 内层循环进行实际的比较和交换  

        for (int j = 0; j < n - 1 - i; j++) {  

            if (array[j] > array[j + 1]) {  

                // 交换元素  

                int temp = array[j];  

                array[j] = array[j + 1];  

                array[j + 1] = temp;  

                swapped = true;  

            }  

        }  

        // 如果没有发生交换，说明数组已经有序，可以提前结束排序  

        if (!swapped) break;  

    }  

}  



// 打印数组的方法  

public static void printArray(int[] array) {  

    for (int i : array) {  

        System.out.print(i + " ");  

    }  

    System.out.println();  

}  



// 主方法，程序的入口点  

public static void main(String[] args) {  

    // 定义一个待排序的数组  

    int[] array = {64, 34, 25, 12, 22, 11, 90};  

    // 打印排序前的数组  

    System.out.println("排序前的数组:");  

    printArray(array);  

    // 调用冒泡排序算法对数组进行排序  

    bubbleSort(array);  

    // 打印排序后的数组  

    System.out.println("排序后的数组:");  

    printArray(array);  

}

}

在这个示例中，bubbleSort方法实现了冒泡排序算法，它接受一个整数数组作为参数，并对其进行原地排序（即不需要额外的存储空间）。printArray方法用于打印数组的内容。main方法是程序的入口点，它创建了一个待排序的数组，调用bubbleSort方法对其进行排序，并在排序前后打印数组的内容。

运行这个程序，你将看到数组在排序前后的变化。冒泡排序的时间复杂度为O(n^2)，在处理大数据集时可能不够高效。对于更高效的排序算法，你可以考虑使用Java内置的排序方法（如Arrays.sort），它基于TimSort算法实现，具有O(n log n)的时间复杂度。

2、选择排序

在Java程序设计中，选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

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

public class SelectionSort {

// 选择排序算法的实现  

public static void selectionSort(int[] 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; // 更新最小值的索引  

            }  

        }  

        // 将找到的最小值与当前元素交换位置  

        if (minIndex != i) {  

            int temp = array[minIndex];  

            array[minIndex] = array[i];  

            array[i] = temp;  

        }  

    }  

}  



// 打印数组的方法  

public static void printArray(int[] array) {  

    for (int i : array) {  

        System.out.print(i + " ");  

    }  

    System.out.println();  

}  



// 主方法，程序的入口点  

public static void main(String[] args) {  

    // 定义一个待排序的数组  

    int[] array = {64, 25, 12, 22, 11};  

    // 打印排序前的数组  

    System.out.println("排序前的数组:");  

    printArray(array);  

    // 调用选择排序算法对数组进行排序  

    selectionSort(array);  

    // 打印排序后的数组  

    System.out.println("排序后的数组:");  

    printArray(array);  

}

}

在这个示例中，selectionSort方法实现了选择排序算法，它接受一个整数数组作为参数，并对其进行原地排序。printArray方法用于打印数组的内容。main方法是程序的入口点，它创建了一个待排序的数组，调用selectionSort方法对其进行排序，并在排序前后打印数组的内容。

运行这个程序，你将看到数组在排序前后的变化。选择排序的时间复杂度为O(n^2)，在处理大数据集时可能不够高效。然而，由于其实现简单且不需要额外的存储空间，选择排序在某些特定情况下仍然是一个有用的算法。

3、快速排序

快速排序（Quick Sort）是一种高效的排序算法，它采用分而治之的策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。以下是Java中快速排序的一个简单实现案例：

public class QuickSort {

// 快速排序算法的实现  

public static void quickSort(int[] array, int low, int high) {  

    if (low < high) {  

        // 获取分区位置  

        int pi = partition(array, low, high);  

        // 递归地对左右子数组进行排序  

        quickSort(array, low, pi - 1);  

        quickSort(array, pi + 1, high);  

    }  

}  



// 分区方法，它选择一个元素作为基准，并重新排列数组，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边  

private static int partition(int[] array, int low, int high) {  

    int pivot = array[high]; // 选择最右边的元素作为基准  

    int i = (low - 1); // i是较小元素的索引  



    for (int j = low; j < high; j++) {  

        // 如果当前元素小于或等于基准  

        if (array[j] <= pivot) {  

            i++;  

            // 交换array[i]和array[j]  

            int temp = array[i];  

            array[i] = array[j];  

            array[j] = temp;  

        }  

    }  



    // 交换array[i + 1]和array[high]（或基准）  

    int temp = array[i + 1];  

    array[i + 1] = array[high];  

    array[high] = temp;  



    // 返回基准的最终位置  

    return i + 1;  

}  



// 打印数组的方法  

public static void printArray(int[] array) {  

    for (int i : array) {  

        System.out.print(i + " ");  

    }  

    System.out.println();  

}  



// 主方法，程序的入口点  

public static void main(String[] args) {  

    // 定义一个待排序的数组  

    int[] array = {10, 7, 8, 9, 1, 5};  

    // 打印排序前的数组  

    System.out.println("排序前的数组:");  

    printArray(array);  

    // 调用快速排序算法对数组进行排序  

    quickSort(array, 0, array.length - 1);  

    // 打印排序后的数组  

    System.out.println("排序后的数组:");  

    printArray(array);  

}

}

在这个示例中，quickSort方法实现了快速排序算法，它接受一个整数数组和两个整数（表示要排序的子数组的低和高索引）作为参数。partition方法是一个辅助方法，它选择一个基准元素，并重新排列数组，使得所有小于基准的元素都在基准的左边，所有大于基准的元素都在基准的右边。然后，quickSort方法递归地对左右两个子数组进行排序。

printArray方法用于打印数组的内容，而main方法是程序的入口点，它创建了一个待排序的数组，调用quickSort方法对其进行排序，并在排序前后打印数组的内容。

运行这个程序，你将看到数组在排序前后的变化。快速排序的平均时间复杂度为O(n log n)，但在最坏的情况下（例如，当数组已经是有序的，并且每次选择的基准都是最大或最小元素时），它的时间复杂度会退化到O(n^2)。不过，通过随机选择基准或使用其他策略（如三数取中法），可以大大降低最坏情况发生的概率。