常见排序算法分类（排序算法，是算法的基石，你掌握多少？） |
您所在的位置：网站首页 › 怎样给图片分类排序呢 › 常见排序算法分类（排序算法，是算法的基石，你掌握多少？） |
常见排序算法分类（排序算法，是算法的基石，你掌握多少？）
|
前言： 排序算法，是算法的基石，你掌握多少？ 常见排序算法分类
常见排序算法可以分为两大类： 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。如：快速排序、归并排序、堆排序、冒泡排序等。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。如：计数排序、基数排序、桶排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。 常见算法的复杂度分析ps：稳定性通俗地讲，就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。 稳定排序算法：冒泡排序、插入排序、归并排序、计数排序、桶排序与基数排序 不稳定排序算法：希尔排序、选择排序、堆排序与快速排序 ps：判断一个排序是否稳定要看算法中每一次循环比较的步长，如果步长大于1，就是不稳定的，否则就是稳定的。非比较排序是稳定的。 复杂度分析： 数据结构和算法本身解决的是“快”和“省”的问题，衡量算法执行效率的指标就包括复杂度 复杂度分析包括时间复杂度和空间复杂度分析，时间复杂度是指算法执行的时间与数据规模的关系，空间复杂度是指算法占用的空间与数据规模的关系 为什么进行复杂度分析？如何分析？ 为什么分析复杂度：通过测试、统计、监控，可以的得到算法执行的时间和占用的内存大小，但是测试结果非常依赖测试环境，测试结果受数据规模的影响很大；我们需要一个不依赖测试环境和数据规模就可以粗略估算算法执行效率的方法大O时间复杂度表示法：表示代码执行时间随数据规模增长的变化趋势，又称渐进时间复杂度 大O空间复杂度表示法：表示代码执行所占的内存空间随数据规模增长的变化趋势，又称渐进空间复杂度 ps：给出随着增长规模的下界，具体流程：https://www.cnblogs.com/zxhyJack/p/10596735.html 大O复杂度表示法算法的执行效率，粗略地讲就是算法的执行时间。下面的代码是求1，2，3...n累加的和。 cal(int n) { int sum = 0; int i = 1; for (; i 运算 -> 写数据，如果每一个操作都是unit_time，第二行和第三行是一个unit_time，而第四行和第五行的for循环是2n个unit_time，加上return操作。时间复杂度就是2n+3，一般计算的时候会把常量省略，所以这个程序的时间复杂度就是n。所以就可以推断出，所以代码的执行时间T(n)与每行代码的的执行次数成正比。引出重要概念，所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正。即T(n) = O(f(n)) 复杂度分析法则 单段代码，看循环的次数。 多段代码，看代码循环量级。 嵌套代码求乘积，比如递归和多重循环。 多个规模求加法，方法中并行的两个循环。 常用的复杂度级别 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长，包括，O(1)(常数阶)、O(logn)(对数阶)、O(n)(线性阶)、O(nlogn)(线性对数阶)、O(n2)(平方阶)、O(n3)(立方阶)。 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用暴增，这列算法性能极差。包括，O(2^n)(指数阶)、O(n!)(阶乘阶) 复杂度分析的四个概念 最坏情况时间复杂度：代码在最坏情况下执行的时间复杂度。 最好情况时间复杂度：代码在最理想情况下执行的时间复杂度。 平均时间复杂度：用代码在所有情况下执行的次数的加权平均值表示。 均摊时间复杂度：在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。 ps：区分平均时间复杂度和均摊时间复杂度 平均时间复杂度：代码在不同情况下复杂度出现量级差别，则用代码所有可能情况下执行次数的加权平均值表示。 均摊时间复杂度：两个条件满足时使用：1）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度；2）低级别和高级别复杂度出现具有时序规律。均摊结果一般都等于低级别复杂度。 1、冒泡排序基本思想：每次此循环确定未排序的数组的最大值（每轮遍历固定一个元素），出现逆序交换元素，通过比较元素的大小，将较大的数依次交换到最后面。（或者每次寻找最小值，依次交换到最前边）。 复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)。 代码实现： public void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = arr.length - 1; i >= 0; i--) { for (int j = 1; j < i; j++) { if (arr[j] < arr[j - 1]) { swap(arr, j, j - 1); // 逆序交换元素 } } } } private void swap(int[] arr, int i, int j) { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; } 2、选择排序基本思想：在未排序序列中找到最小元素，存放到排序序列起始位置。再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。（或者每次在未排序的数组中找最大值，加入排序序列） 复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)。 代码实现： public void selectSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length - 1; i++) { int minIndex = i; // 初始化最小值索引 for (int j = i + 1; j < arr.length; i++) { minIndex = arr[j] < arr[minIndex] ? j : minIndex; // 更新最小值索引 } swap(arr, i, minIndex) } } private void swap(int[] arr, int i, int j) { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; } 3、插入排序基本思想：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。可以理解为玩扑克牌时的理牌； 复杂度分析：时间复杂度O(N^2)，空间复杂度O(1)。 代码实现： public void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j > 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); // 从后向前遍历已经排序数组，寻找插入位置 } } } private void swap(int[] arr, int i, int j) { arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; } 4、希尔排序基本思想：希尔排序是插入排序的一种高效率的实现，也叫缩小增量排序。先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序。 问题：增量的序列取法？ 关于取法，没有统一标准，但最后一步必须是1；因为不同的取法涉及时间复杂度不一样，具体了解可以参考《数据结构与算法分析》；一般以length/2为算法。（再此以gap=gap*3+1为公式） 复杂度分析：时间复杂度O(N^3/2 )，最坏时间复杂度O(N^2)，空间复杂度O(1)。 代码实现： private static void sort(int[] array) { int n = array.length; int h = 1; while (h < n / 3) { //动态定义间隔序列 h = 3 * h + 1; } while (h >= 1) { for (int i = h; i < n; i++) { for (int j = i; j >= h && (array[j] < array[j - h]); j -= h) { int temp = array[j]; array[j] = array[j - h]; array[j-h]= temp; } } h /= 3; } } 5、归并排序基本思想：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。它使用了递归分治的思想。简言之，先递归的分解数组，再合并有序数组。 复杂度分析：时间复杂度O(NlogN)，空间复杂度O(N)。 代码实现： public static void mergeSort(int[] arr) { // 主函数 if (arr == null || arr.length < 2) { return; } mergeSort(arr, 0, arr.length - 1); } //1.递归分解数组 public static void mergeSort(int[] arr, int l, int r) { if (l == r) return; int m = l + ((r - l) >> 1); //注：算数运算符优先级大于移位！ mergeSort(arr, l, m); mergeSort(arr, m + 1, r); merge(arr, l, m, r); } //2.合并成有序数组 public static void merge(int[] arr, int l, int m, int r) { int[] help = new int[r - l + 1]; int index = 0; int p1 = l, p2 = m + 1; while (p1 arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } //使用异或当(即位运算交换两个数)i=j时可能会出错 public static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } //当出现某个位置的数值改变怎么调整 public static void heapify(int[] arr, int index, int heapSize) { int left = index * 2 + 1; while (left < heapSize) { //找最大值的下标 (算术运算符的优先级大于关系运算符) int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left; //左右孩子的最大值和父节点比较 largest = arr[largest] > arr[index] ? largest : index; if (index == largest) { break; } swap(arr, index, largest); index = largest; left = index * 2 + 1; } } 8、计数排序基本思想：将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。复杂度分析：时间复杂度O(N + K)，空间复杂度O(N + K)。 代码实现： /** * 输入数组的元素都是介于0..k之间的 * @param data 待排序数组 * @param k 最大元素 * @return 排序结果 */ public static int[] countingSort(int[] data, int k) { // 存放临时数据的数组tmp，初始元素都是0；k为数组中最大元素 int[] tmp = new int[k + 1]; // 计算数组中每个元素i出现的次数，存入数组tmp中的第i项，即原数组中的元素值为tmp数组中的下标 for (int i = 0; i = 0; j--) { int tempKey = (temp[j]/divide)%radix; count[tempKey]--; array[count[tempKey]] = temp[j]; } divide = divide * radix; } }应用场景分析： （1）若数据规模较小（如n |
【本文地址】