贵州省住房与城乡建设厅门户网站,seo查询排名系统,软件开发流程设计,合肥网络公司注册探究排序算法#xff1a;比较与非比较排序算法及性能分析
排序算法是计算机科学中的基本问题#xff0c;它涉及将一组元素按照特定的顺序排列。本文将深入介绍比较排序算法和非比较排序算法#xff0c;包括每个算法的原理、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;ListDouble[] 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 );}}
}排序算法的性能分析和比较
排序算法的性能在不同场景下会有所不同。比较排序算法的平均时间复杂度如下
冒泡排序O(n^2)插入排序O(n^2)选择排序O(n^2)希尔排序取决于步长序列一般在 O(n log n) 到 O(n^2) 之间快速排序O(n log n) 平均最坏情况为 O(n^2)归并排序O(n log n)堆排序O(n log n)
非比较排序算法的时间复杂度如下
计数排序O(n k)其中 k 是数据范围桶排序O(n^2) 最坏情况平均情况较好基数排序O(n * k)其中 k 是数字的位数
综合来看在大多数情况下快速排序和归并排序是较优的选择具有较快的平均性能。计数排序和基数排序在特定情况下也能表现优异。
