java实现冒泡排序和快速排序

程序你得看得懂 2024-02-25 09:53:59

冒泡排序和快速排序是两种非常常见的排序算法,它们都有各自的优缺点。下面是这两种排序算法的原理和Java实现。

冒泡排序

原理:

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

Java实现:

public BubbleSort { public static void main(String[] args) { int[] array = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(array); System.out.println("Sorted array: "); printArray(array); } static void bubbleSort(int[] arr) { int n = arr.length; for (int i = 0; i < n-1; i++) { for (int j = 0; j < n-i-1; j++) { if (arr[j] > arr[j+1]) { // swap arr[j+1] and arr[j] int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } /* Prints the array */ static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i] + " "); System.out.println(); } }快速排序

原理:

快速排序使用分治的原则,把一个数组分为两个子数组,将两部分独立地排序。快速排序通过选取一个“主元”(pivot)元素,并把数组分为两个子数组:一个的所有元素都比主元小,另一个的所有元素都比主元大。然后对这两个子数组进行快速排序,最终达到整个数组有序。

Java实现:

public QuickSort { public static void main(String[] args) { int[] array = {10, 7, 8, 9, 1, 5}; int n = array.length; quickSort(array, 0, n-1); System.out.println("Sorted array: "); printArray(array); } static void quickSort(int arr[], int low, int high) { if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // Separately sort elements before partition and after partition quickSort(arr, low, pi-1); quickSort(arr, pi+1, high); } } static int partition(int arr[], int low, int high) { int pivot = arr[high]; // pivot int i = (low - 1); // Index of smaller element for (int j = low; j <= high- 1; j++) { // If current element is smaller than or equal to pivot if (arr[j] <= pivot) { i++; // increment index of smaller element int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } // Swap arr[i+1] and arr[high] int temp = arr[i+1]; arr[i+1] = arr[high]; arr[high] = temp; return (i + 1); } // A utility function to print array of size n static void printArray(int arr[]) { int n = arr.length; for (int i=0; i<n; ++i) System.out.print(arr[i]+" "); System.out.println(); } }

这两种排序算法在实际应用中都有各自的使用场景。例如,如果你的数据集很小,或者大部分数据已经排好序,那么冒泡排序可能是一个好选择。然而,如果你的数据集很大,并且你需要快速的排序,那么快速排序可能会更好。但是请注意,在最坏的情况下(输入数组已经排序或逆序),快速排序可能会变得非常慢,此时的时间复杂度会达到O(n^2)。在实际应用中,通常会使用随机化的快速排序或者三向切分的快速排序来避免这种情况。

0 阅读:19

程序你得看得懂

简介:感谢大家的关注