当前位置：首页 > news >正文

建设银行的财务网站百度高级搜索首页

news 2025/7/28 5:38:47

建设银行的财务网站,百度高级搜索首页,品牌故事经典案例,国外财经网站是怎么做的探究排序算法：比较与非比较排序算法及性能分析排序算法是计算机科学中的基本问题，它涉及将一组元素按照特定的顺序排列。本文将深入介绍比较排序算法和非比较排序算法，包括每个算法的原理、Java代码示例以及它们的性能分析和比较。比较排…

探究排序算法：比较与非比较排序算法及性能分析

排序算法是计算机科学中的基本问题，它涉及将一组元素按照特定的顺序排列。本文将深入介绍比较排序算法和非比较排序算法，包括每个算法的原理、Java代码示例以及它们的性能分析和比较。

比较排序算法

1. 冒泡排序（Bubble Sort）

原理：冒泡排序通过多次遍历数组，比较相邻元素并交换，使较大的元素逐渐“冒泡”到数组的尾部。

代码示例：

public class BubbleSort {public static void bubbleSort(int[] 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]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}}public static void main(String[] args) {int[] array = {64, 34, 25, 12, 22, 11, 90};bubbleSort(array);System.out.println("冒泡排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

2. 插入排序（Insertion Sort）

原理：插入排序将数组分为已排序和未排序两部分，逐个将未排序元素插入到已排序部分的正确位置。

代码示例：

public class InsertionSort {public static void insertionSort(int[] array) {int n = array.length;for (int i = 1; i < n; i++) {int key = array[i];int j = i - 1;while (j >= 0 && array[j] > key) {array[j + 1] = array[j];j--;}array[j + 1] = key;}}public static void main(String[] args) {int[] array = {12, 11, 13, 5, 6};insertionSort(array);System.out.println("插入排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

3. 选择排序（Selection Sort）

原理：选择排序在未排序部分找到最小元素，然后与已排序部分的末尾元素交换，逐步构建有序序列。

代码示例：

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;}}int temp = array[minIndex];array[minIndex] = array[i];array[i] = temp;}}public static void main(String[] args) {int[] array = {64, 25, 12, 22, 11};selectionSort(array);System.out.println("选择排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

4. 希尔排序（Shell Sort）

原理：希尔排序是插入排序的改进，通过将数组分为多个子序列来进行排序，逐渐减小步长，最终使整个数组基本有序。

代码示例：

public class ShellSort {public static void shellSort(int[] array) {int n = array.length;for (int gap = n / 2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = array[i];int j = i;while (j >= gap && array[j - gap] > temp) {array[j] = array[j - gap];j -= gap;}array[j] = temp;}}}public static void main(String[] args) {int[] array = {12, 34, 54, 2, 3};shellSort(array);System.out.println("希尔排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

5. 快速排序（Quick Sort）

原理：快速排序使用分治法，选择一个基准元素，将数组分成左右两部分，左边的元素小于基准，右边的元素大于基准，然后对左右子数组递归地应用快速排序。

代码示例：

public class QuickSort {public static void quickSort(int[] array, int low, int high) {if (low < high) {int pivotIndex = partition(array, low, high);quickSort(array, low, pivotIndex - 1);quickSort(array, pivotIndex + 1, high);}}public static int partition(int[] array, int low, int high) {int pivot = array[high];int i = low - 1;for (int j = low; j < high; j++) {if (array[j] < pivot) {i++;int temp = array[i];array[i] = array[j];array[j] = temp;}}int temp = array[i + 1];array[i + 1] = array[high];array[high] = temp;return i + 1;}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("快速排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

6. 归并排序（Merge Sort）

原理：归并排序是一种分治算法，将数组逐步分成两个子数组，分别排序后再合并成一个有序数组。

代码示例：

public class MergeSort {public static void mergeSort(int[] array, int left, int right) {if (left < right) {int mid = (left + right) / 2;mergeSort(array, left, mid);mergeSort(array, mid + 1, right);merge(array, left, mid, right);}}public static void merge(int[] array, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int[] leftArray = new int[n1];int[] rightArray = new int[n2];for (int i = 0; i < n1; i++) {leftArray[i] = array[left + i];}for (int j = 0; j < n2; j++) {rightArray[j] = array[mid + 1 + j];}int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArray[i] <= rightArray[j]) {array[k] = leftArray[i];i++;} else {array[k] = rightArray[j];j++;}k++;}while (i < n1) {array[k] = leftArray[i];i++;k++;}while (j < n2) {array[k] = rightArray[j];j++;k++;}}public static void main(String[] args) {int[] array = {12, 11, 13, 5, 6, 7};int n = array.length;mergeSort(array, 0, n - 1);System.out.println("归并排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

非比较排序算法

1. 计数排序（Counting Sort）

原理：计数排序适用于元素范围较小的情况，它统计每个元素出现的次数，然后根据统计信息重新构建有序序列。

代码示例：

public class CountingSort {public static void countingSort(int[] array) {int n = array.length;int max = Arrays.stream(array).max().getAsInt();int min = Arrays.stream(array).min().getAsInt();int range = max - min + 1;int[] count = new int[range];int[] output = new int[n];for (int num : array) {count[num - min]++;}for (int i = 1; i < range; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[array[i] - min] - 1] = array[i];count[array[i] - min]--;}for (int i = 0; i < n; i++) {array[i] = output[i];}}public static void main(String[] args) {int[] array = {4, 2, 2, 8, 3, 3, 1};countingSort(array);System.out.println("计数排序结果：");for (int num : array) {System.out.print(num + " ");}}
}

2. 桶排序（Bucket Sort）

原理：桶排序将数据分成多个桶，每个桶内部使用其他排序算法（通常是插入排序），然后将桶内有序的数据合并起来。

代码示例：

public class BucketSort {public static void bucketSort(double[] array) {int n = array.length;List<Double>[] buckets = new List[n];for (int i = 0; i < n; i++) {buckets[i] = new ArrayList<>();}for (int i = 0; i < n; i++) {int bucketIndex = (int) (n * array[i]);buckets[bucketIndex].add(array[i]);}for (int i = 0; i < n; i++) {Collections.sort(buckets[i]);}int index = 0;for (int i = 0; i < n; i++) {for (double num : buckets[i]) {array[index++] = num;}}}public static void main(String[] args) {double[] array = {0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51};bucketSort(array);System.out.println("桶排序结果：");for (double num : array) {System.out.print(num + " ");}}
}

3. 基数排序（Radix Sort）

原理：基数排序逐位对元素进行排序，先按最低位排序，再按次低位排序，直到最高位。

代码示例：

public class RadixSort {public static void radixSort(int[] array) {int n = array.length;int max = Arrays.stream(array).max().getAsInt();for (int exp = 1; max / exp > 0;exp *= 10) {countingSortByDigit(array, n, exp);}}public static void countingSortByDigit(int[] array, int n, int exp) {int[] output = new int[n];int[] count = new int[10];for (int i = 0; i < n; i++) {count[(array[i] / exp) % 10]++;}for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}for (int i = n - 1; i >= 0; i--) {output[count[(array[i] / exp) % 10] - 1] = array[i];count[(array[i] / exp) % 10]--;}for (int i = 0; i < n; i++) {array[i] = output[i];}}public static void main(String[] args) {int[] array = {170, 45, 75, 90, 802, 24, 2, 66};radixSort(array);System.out.println("基数排序结果：");for (int num : array) {System.out.print(num + " ");}}
}