平面排版网站,什么是网络营销的渠道策略,环球资源网怎么找客户,广州建设技术职业学院有什么专业欢迎并且感谢大家指出我的问题#xff0c;由于本人水平有限#xff0c;有些内容写的不是很全面#xff0c;只是把比较实用的东西给写下来#xff0c;如果有写的不对的地方#xff0c;还希望各路大牛多多指教#xff01;谢谢大家#xff01;#x1f970; 在计算机科学领… 欢迎并且感谢大家指出我的问题由于本人水平有限有些内容写的不是很全面只是把比较实用的东西给写下来如果有写的不对的地方还希望各路大牛多多指教谢谢大家 在计算机科学领域排序算法是基础且重要的算法类别它能够将一组无序的数据按照特定的顺序如升序或降序重新排列。接下来我们将详细探讨冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序和计数排序这八大排序算法。
冒泡排序
基本概念
冒泡排序是一种简单的比较排序算法它通过多次比较相邻元素并交换位置将最大或最小的元素逐步 “冒泡” 到数组的末尾。
核心思想
重复地走访要排序的数列一次比较两个元素如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。
算法步骤
比较相邻的元素。如果第一个比第二个大升序就交换它们两个。
对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。
针对所有的元素重复以上的步骤除了最后一个。
持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
代码实现Java
public class BubbleSort {public 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]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}}
}
优缺点及适用场景
优点实现简单代码量少比较稳定相同元素的相对顺序在排序前后不会改变。
缺点时间复杂度较高为 O (n²)在数据量较大时效率较低。
适用场景适用于数据量较小且对稳定性有要求的场景。
选择排序
基本概念
选择排序是一种简单直观的排序算法它在每一趟选择未排序序列中最小或最大的元素存放到已排序序列的末尾。
核心思想
首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
算法步骤
初始状态无序区为整个数组有序区为空。
第 1 趟排序在无序区中选出最小大的元素将它与无序区的第 1 个元素交换此时有序区增加 1 个元素无序区减少 1 个元素。
重复第 2 步直到无序区为空。
代码实现Java
public class SelectionSort {public static void selectionSort(int[] arr) {int n arr.length;for (int i 0; i n - 1; i) {int minIndex i;for (int j i 1; j n; j) {if (arr[j] arr[minIndex]) {minIndex j;}}int temp arr[minIndex];arr[minIndex] arr[i];arr[i] temp;}}
}
优缺点及适用场景
优点简单直观无论什么数据进去都是 O (n²) 的时间复杂度所以如果数据规模较小可以考虑使用。
缺点时间复杂度高同样为 O (n²)且不稳定。
适用场景适用于数据量较小对时间复杂度要求不高且对稳定性没有要求的场景。
插入排序
基本概念
插入排序是将一个数据插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据。
核心思想
把 n 个待排序的元素看成一个有序表和一个无序表。开始时有序表中只包含 1 个元素无序表中包含 n - 1 个元素排序过程中每次从无序表中取出第一个元素将它插入到有序表中的适当位置使之成为新的有序表重复 n - 1 次可完成排序过程。
算法步骤
从第一个元素开始该元素可以认为已经被排序。
取出下一个元素在已经排序的元素序列中从后向前扫描。
如果已排序元素大于新元素将已排序元素移到下一位置。
重复步骤 3直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤 2~5。
代码实现Java
public class InsertionSort {public static void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {int key arr[i];int j i - 1;while (j 0 arr[j] key) {arr[j 1] arr[j];j j - 1;}arr[j 1] key;}}
}
优缺点及适用场景
优点在数据量较小或者部分有序的情况下效率较高并且是稳定的排序算法。
缺点时间复杂度在最坏情况下为 O (n²)不适用于大规模数据排序。
适用场景适用于数据量较小、部分有序的数据排序以及对稳定性有要求的场景。
希尔排序
基本概念
希尔排序也称递减增量排序算法是插入排序的一种更高效的改进版本。它通过将原始数据分成多个子序列对每个子序列进行插入排序逐步减少增量最终使整个序列有序。
核心思想
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录 “基本有序” 时再对全体记录进行依次直接插入排序。
算法步骤
选择一个增量序列 t1t2…tk其中 ti tj, tk 1。
按增量序列个数 k对序列进行 k 趟排序。
每趟排序根据对应的增量 ti将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。
代码实现Java
public class ShellSort {public static void shellSort(int[] arr) {int n arr.length;for (int gap n / 2; gap 0; gap / 2) {for (int i gap; i n; i) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}}
}
优缺点及适用场景
优点希尔排序的时间复杂度比 O (n²) 要好很多在中等规模数据下表现良好并且实现相对简单。
缺点希尔排序是不稳定的排序算法并且其时间复杂度分析较为复杂。
适用场景适用于中等规模数据的排序对稳定性要求不高的场景。
快速排序
基本概念
快速排序是一种分治的排序算法它通过选择一个基准元素将数组分为两部分使得左边部分的元素都小于基准元素右边部分的元素都大于基准元素然后递归地对左右两部分进行排序。
核心思想
从数列中挑出一个基准值通常选择第一个元素或最后一个元素。
重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区操作。
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
算法步骤
选择基准值 pivot。
初始化两个指针 left 和 rightleft 指向数组的起始位置right 指向数组的末尾位置。
从 right 开始向左移动 right 指针直到找到一个小于 pivot 的元素从 left 开始向右移动 left 指针直到找到一个大于 pivot 的元素。
如果 left right交换这两个元素然后继续步骤 3。
当 left right 时将 pivot 与 left 指向的元素交换此时 pivot 左边的元素都小于它右边的元素都大于它。
递归地对 pivot 左边和右边的子数组进行快速排序。
代码实现Java
public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low high) {int pi partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi 1, high);}}private static int partition(int[] arr, int low, int high) {int pivot arr[high];int i (low - 1);for (int j low; j high; j) {if (arr[j] pivot) {i;int temp arr[i];arr[i] arr[j];arr[j] temp;}}int temp arr[i 1];arr[i 1] arr[high];arr[high] temp;return i 1;}
}
优缺点及适用场景
优点平均时间复杂度为 O (nlogn)在大多数情况下表现非常高效并且是一种原地排序算法不需要额外的大量辅助空间。
缺点在最坏情况下如数组已经有序时间复杂度会退化为 O (n²)并且快速排序是不稳定的排序算法。
适用场景适用于大规模数据的排序对稳定性没有要求的场景。
归并排序
基本概念
归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。它将一个数组分成两个子数组对每个子数组进行排序然后将排序好的子数组合并成一个最终的有序数组。
核心思想
把长度为 n 的输入序列分成两个长度为 n/2 的子序列。
对这两个子序列分别采用归并排序。
将两个排序好的子序列合并成一个最终的有序序列。
算法步骤
分解将数组不断地分成两个子数组直到子数组的长度为 1。
合并将两个有序的子数组合并成一个更大的有序数组。合并时比较两个子数组的元素将较小的元素依次放入一个临时数组中直到其中一个子数组的元素全部放入临时数组然后将另一个子数组的剩余元素也放入临时数组。
将临时数组中的元素复制回原数组完成一次合并。
重复步骤 2 和 3直到所有子数组都合并成一个有序数组。
代码实现Java
public class MergeSort {public static void mergeSort(int[] arr) {int n arr.length;if (n 2) {return;}int mid n / 2;int[] left new int[mid];int[] right new int[n - mid];System.arraycopy(arr, 0, left, 0, mid);System.arraycopy(arr, mid, right, 0, n - mid);mergeSort(left);mergeSort(right);merge(arr, left, right);}private static void merge(int[] arr, int[] left, int[] right) {int i 0, j 0, k 0;while (i left.length j right.length) {if (left[i] right[j]) {arr[k] left[i];i;} else {arr[k] right[j];j;}k;}while (i left.length) {arr[k] left[i];i;k;}while (j right.length) {arr[k] right[j];j;k;}}
}
优缺点及适用场景
优点时间复杂度始终为 O (nlogn)并且是稳定的排序算法适用于大规模数据的排序。
缺点需要额外的空间来存储临时数组空间复杂度为 O (n)。
适用场景适用于对稳定性有要求数据量较大的场景如外部排序。
堆排序
基本概念
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。
核心思想
首先将待排序的数组构建成一个最大堆升序排序时或最小堆降序排序时。
然后将堆顶元素与堆的最后一个元素交换此时堆的最后一个元素就是最大或最小的元素将其从堆中移除实际上是缩小堆的范围。
对剩余的元素重新调整为最大堆或最小堆重复步骤 2直到堆中只剩下一个元素此时数组已经有序。
算法步骤
初始化堆将数组构建成一个最大堆或最小堆。从最后一个非叶子节点开始依次对每个非叶子节点进行向下调整操作使其满足堆的性质。
交换与调整将堆顶元素与堆的最后一个元素交换然后对堆顶元素进行向下调整操作使堆重新满足堆的性质。
重复步骤 2直到堆中只剩下一个元素。
代码实现Java
public class HeapSort {public static void heapSort(int[] arr) {int n arr.length;// 构建最大堆for (int i n / 2 - 1; i 0; i--) {heapify(arr, n, i);}// 一个个取出元素for (int i n - 1; i 0; i--) {int temp arr[0];arr[0] arr[i];arr[i] temp;// 调整堆heapify(arr, i, 0);}}private static void heapify(int[] arr, int n, int i) {int largest i;int left 2 * i 1;int right 2 * i 2;if (left n arr[left] arr[largest]) {largest left;}if (right n arr[right] arr[largest]) {largest right;}if (largest! i) {int swap arr[i];arr[i] arr[largest];arr[largest] swap;// 递归调整受影响的子树heapify(arr, n, largest);}}
}
优缺点及适用场景
优点时间复杂度为 O (nlogn)并且是原地排序算法不需要额外的大量辅助空间。
缺点堆排序是不稳定的排序算法并且实现相对复杂。
适用场景适用于大规模数据的排序对稳定性没有要求并且空间有限的场景。
计数排序
基本概念
计数排序是一种非比较排序算法它通过统计每个元素在数组中出现的次数然后根据统计结果将元素按照顺序输出从而实现排序。
核心思想 1.找出待排序数组中的最大值和最小值确定计数数组的范围。 2.统计每个元素在数组中出现的次数将统计结果存储在计数数组中。 3.根据计数数组将每个元素按照出现的次数依次输出到结果数组中。
算法步骤
确定范围遍历待排序数组找出其中的最大值max和最小值min计算出计数数组的长度countLength max - min 1。初始化计数数组创建一个长度为countLength的计数数组count并将所有元素初始化为 0。统计元素出现次数再次遍历待排序数组对于数组中的每个元素num将count[num - min]的值加 1表示该元素出现的次数。计算前缀和对计数数组进行处理计算每个元素的前缀和。即从计数数组的第二个元素开始每个元素都加上前一个元素的值。这一步的目的是让count[i]表示小于等于i min的元素个数。填充结果数组创建一个与待排序数组长度相同的结果数组result。从待排序数组的末尾开始遍历对于每个元素num根据count[num - min]的值确定其在结果数组中的位置然后将count[num - min]减 1。重复此步骤直到所有元素都放入结果数组中。
代码实现 public class CountingSort {public static void countingSort(int[] arr) {if (arr null || arr.length 0) {return;}int max arr[0];int min arr[0];// 找出最大值和最小值for (int num : arr) {if (num max) {max num;}if (num min) {min num;}}int countLength max - min 1;int[] count new int[countLength];// 统计每个元素出现的次数for (int num : arr) {count[num - min];}// 计算前缀和for (int i 1; i countLength; i) {count[i] count[i - 1];}int[] result new int[arr.length];// 填充结果数组for (int i arr.length - 1; i 0; i--) {result[count[arr[i] - min] - 1] arr[i];count[arr[i] - min]--;}// 将结果复制回原数组System.arraycopy(result, 0, arr, 0, arr.length);}
} 优缺点及适用场景 优点时间复杂度为 O (n k)其中 n 是待排序数组的长度k 是数据的范围。在数据范围不大且数据量较大时效率非常高。并且计数排序是稳定的排序算法。缺点对数据的要求比较苛刻只能用于数据范围较小且数据为整数的情况。同时需要额外的空间来存储计数数组空间复杂度为 O (k) 。适用场景适用于数据范围有限且对稳定性有要求的场景比如对学生成绩分数范围固定进行排序等。
