十大常见排序算法（代码实现、复杂度分析与应用场景） |
您所在的位置：网站首页 › 各种排序算法代码 › 十大常见排序算法（代码实现、复杂度分析与应用场景） |
|
常见排序算法分类
常见排序算法可以分为两大类： 非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。如：快速排序、归并排序、堆排序、冒泡排序等。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。 线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。如：计数排序、基数排序、桶排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。 常见算法的复杂度分析参考这里：所谓稳定性是指待排序的序列中有两元素相等,排序之后它们的先后顺序不变.假如为A1,A2.它们的索引分别为1,2.则排序之后A1,A2的索引仍然是1和2.（相同的记录在排序前后相对次序不发生改变，那么就是稳定的排序） 对于不稳定的 排序算法 ，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是， 排序算法是否为稳定的是由具体算法决定的 ，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。例如，对于如下冒泡排序算法，原本是稳定的排序算法，如果将记录交换的条件改成a[j]>=a[j+1]，则两个相等的记录就会交换位置。 稳定性的意义： 1、如果只是简单的进行数字的排序，那么稳定性将毫无意义。 2、如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义（所谓的交换操作的开销已经算在算法的开销内了，如果嫌弃这种开销，不如换算法好了？） 3、如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。 4、除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。 稳定排序算法：冒泡排序、插入排序、归并排序、（计数排序、桶排序与基数排序） 不稳定排序算法：希尔排序、选择排序、堆排序与快速排序复杂度分析： 数据结构和算法本身解决的是“快”和“省”的问题，衡量算法执行效率的指标就包括复杂度 复杂度分析包括时间复杂度和空间复杂度分析，时间复杂度是指算法执行的时间与数据规模的关系，空间复杂度是指算法占用的空间与数据规模的关系为什么进行复杂度分析？如何分析？ 为什么分析复杂度：通过测试、统计、监控，可以的得到算法执行的时间和占用的内存大小，但是测试结果非常依赖测试环境，测试结果受数据规模的影响很大；我们需要一个不依赖测试环境和数据规模就可以粗略估算算法执行效率的方法大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）代码在绝大多数情况下是低级别复杂度，只有极少数情况是高级别复杂度，如hashmap查找元素时间复杂度 O(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--) { // 优化：设置标志位 int flag = 1; for (int j = 1; j < i; j++) { // 是稳定排序，这里如果改成 0 && arr[j] > arr[j + 1]; j--) { // 从后向前遍历已经排序数组，寻找插入位置 swap(arr, j, j + 1); } } } private void swap(int[] arr, int i, int j) { if (i == j) return; arr[i] ^= arr[j]; arr[j] ^= arr[i]; arr[i] ^= arr[j]; }优化：进行二分插入，时间复杂度O(nlogn)。 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 > 1);//计算数组中间的元素的下标 //使用三数取中法选择枢轴 if (arr[mid] > arr[high]) { swap(arr[mid],arr[high]); } if (arr[low] > arr[high]) { swap(arr[low],arr[high]); } if (arr[mid] > arr[low]) { swap(arr[mid],arr[low]); } //此时，arr[mid] 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 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |