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

做软装搭配的网站seo免费课程视频

做软装搭配的网站,seo免费课程视频,青岛市网站建设,大型交流论坛平台有哪些在乱序的世界中,快速排序如同一位智慧的园丁, 以轻盈的手法,将无序的花朵们重新安排, 在每一次比较中,沐浴着理性的阳光, 终使它们在有序的花园里,开出绚烂的芬芳。 文章目录 一、快速排序二、…

在乱序的世界中,快速排序如同一位智慧的园丁,
以轻盈的手法,将无序的花朵们重新安排,
在每一次比较中,沐浴着理性的阳光,
终使它们在有序的花园里,开出绚烂的芬芳。

文章目录

  • 一、快速排序
  • 二、发展历史
  • 三、处理流程
  • 四、算法实现
  • 五、快速排序的特性
  • 六、小结
  • 推荐阅读

一、快速排序

快速排序是一种高效的排序算法,它采用了分治的策略。它的基本思想是选择一个基准值,将数组分为两个子数组,一个子数组中的所有元素都小于基准值,另一个子数组中的所有元素都大于基准值,然后对这两个子数组递归地进行排序。

具体来说,快速排序的步骤如下:

  1. 选择一个基准值(通常是数组的第一个元素、最后一个元素或者中间元素)。
  2. 将数组分为两个子数组,一个子数组中的所有元素都小于基准值,另一个子数组中的所有元素都大于基准值。
  3. 对这两个子数组递归地进行排序。
  4. 将排好序的子数组合并起来,即得到有序数组。

快速排序的关键在于分割操作,通过这个操作,它可以将一个大问题分解成两个规模较小的子问题,然后分别解决,最终达到整体有序的目的。

二、发展历史

快速排序是由英国计算机科学家 Tony Hoare 1960 1960 1960 年代提出的。Hoare 最初将这一算法称为 “分区交换排序”,后来更广泛地称为快速排序。他的灵感来自于合并排序和插入排序。

  1. 早期思想: Hoare 注意到合并排序在实践中性能良好,但需要额外内存空间;而插入排序则内存消耗较少,但在大规模数据下性能不佳。他希望能够结合两者的优点,创造出一种既能够节省空间又能够在平均情况下具有良好性能的排序算法。
  2. Hoare 分区法: Hoare 提出了一种称为 Hoare 分区法的分区策略,这成为了快速排序的核心部分。这个方法从数组中选择一个基准值,将数组分成两个部分,左边的部分包含比基准值小的元素,右边的部分包含比基准值大的元素。然后,递归地对这两个部分进行排序。
  3. 论文发表: Hoare 在 1961 1961 1961 年发表了关于快速排序的论文,论文中描述了这一算法的基本原理和实现方法。此后,他不断改进和优化这一算法,使得快速排序成为了一种非常高效的排序算法。
  4. 持续优化: 随着计算机科学的发展,许多学者对快速排序进行了进一步的优化和改进。例如,采用随机化的方式选择基准值,以防止最坏情况的发生;使用三数取中法来选择基准值,以提高算法的稳定性和性能等。
  5. 现代应用: 至今,快速排序仍然是一种非常流行和高效的排序算法,被广泛应用于各种编程语言和实际应用中。其简洁而优雅的设计理念以及优秀的性能使得它成为了排序算法中的经典之作。

三、处理流程

场景假设:我们需要将下列无序序列使用快速排序按从小到大进行排序。
workspace.png
快速排序的流程如下:

  1. 在原序列中选取第一个元素 3 3 3 作为 Pivot 哨兵
  2. 将序列中小于 Pivot 的元素,放在 Pivot 的左边,大于 Pivot 的元素放在 Pivot 的右边
  3. 递归处理 Pivot 左边的序列和右边的序列
  4. 当子序列为长度 1 1 1 时终止

workspace (1).png

四、算法实现

// 快速排序入口
void quickSort(int[] arr, int low, int high) {if (low < high) {// 对数组进行分区操作int pivot = partition(arr, low, high);// 递归排序左半部分quickSort(arr, low, pivot - 1);// 递归排序右半部分quickSort(arr, pivot + 1, high);}
}// 分区操作
int partition(int[] arr, int low, int high) {// 选择最后一个元素作为 pivotint pivot = arr[high];int i = low - 1; // 指向小于 pivot 的区域的边界// 遍历数组,将小于 pivot 的元素放到左侧for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;// 交换元素int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}// 将 pivot 放到正确位置int temp = arr[i + 1];arr[i + 1] = arr[high];arr[high] = temp;// 返回 pivot的位置return i + 1;
}public static void main(String[] args) {int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};// 调用快速排序算法quickSort(arr, 0, arr.length - 1);// 输出排序后的数组System.out.print("Sorted array: ");for (int num : arr) {System.out.print(num + " ");}
}

算法时间复杂度分析:

情况时间复杂度计算公式公式解释
最好情况 O ( n l o g n ) O(nlogn) O(nlogn) T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\frac{n}{2}) + n T(n)=2T(2n)+n在最优情况下,每次划分都能将数组均匀地分成两部分。因此,我们有两个大小为 n 2 \frac{n}{2} 2n 的子问题,所以有 2 T ( n 2 ) 2T(\frac{n}{2}) 2T(2n)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 2 T ( n 2 ) + n 2T(\frac{n}{2}) + n 2T(2n)+n
平均情况 O ( n l o g n ) O(nlogn) O(nlogn) T ( n ) = T ( n 2 ) + T ( n 2 ) + n T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + n T(n)=T(2n)+T(2n)+n在平均情况下,我们假设每次划分都能将数组均匀地分成两部分。因此,我们有两个大小为 n 2 \frac{n}{2} 2n 的子问题,所以有 T ( n 2 ) + T ( n 2 ) T(\frac{n}{2}) + T(\frac{n}{2}) T(2n)+T(2n)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 T ( n 2 ) + T ( n 2 ) + n T(\frac{n}{2}) + T(\frac{n}{2}) + n T(2n)+T(2n)+n
最坏情况 O ( n 2 ) O(n^2) O(n2) T ( n ) = T ( n − 1 ) + n T(n) = T(n - 1) + n T(n)=T(n1)+n在最坏情况下,每次划分只能将数组划分为一份有 n − 1 n - 1 n1 个元素,另一份有 0 0 0 个元素。因此,我们有一个大小为 n − 1 n - 1 n1 子问题,所以有 T ( n − 1 ) T(n - 1) T(n1)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 T ( n − 1 ) + n T(n - 1) + n T(n1)+n

五、快速排序的特性

快速排序具有以下特性:

  1. 稳定性: 在一般情况下,快速排序是不稳定的,即相同元素在排序后可能会改变相对位置。
  2. 原地性: 快速排序是一种原地排序算法,不需要额外的辅助空间,只需要使用原始数组进行排序。
  3. 适应性: 快速排序适用于各种数据类型,并且对部分有序的数据排序效果良好。
  4. 高效性: 快速排序在平均情况下具有 O ( n l o g n ) O(nlogn) O(nlogn) 的时间复杂度,使其成为处理大规模数据的理想选择。

六、小结

快速排序是一种非常重要且高效的排序算法,适用于各种数据类型和应用场景。其原地性、高效性以及简单直观的实现使得它成为了排序算法中的经典之作。

推荐阅读

  1. Spring 三级缓存
  2. 深入了解 MyBatis 插件:定制化你的持久层框架
  3. Zookeeper 注册中心:单机部署
  4. 【JavaScript】探索 JavaScript 中的解构赋值
  5. 深入理解 JavaScript 中的 Promise、async 和 await
http://www.tj-hxxt.cn/news/9031.html

相关文章:

  • 怎么做移动网站吗百度关键词
  • 免费网站建站+凡科建站自己的网站
  • 做付费软件网站怎么做今天最新的新闻头条新闻
  • 深圳网站建设公司乐云seoseo如何优化
  • 那个网站做粮油批发APPsns营销
  • 个人网站效果图咋做怎么自己做网址
  • 简单大气网站源码百度手机助手app下载
  • div css网站模板素材免费信息推广网站
  • 网页设计网站欣赏唯尚广告联盟平台
  • 微信手机网页版新手学seo
  • 淘宝联盟 网站怎么做广告公司是做什么的
  • 农业信息中心网站建设2023全民核酸又开始了
  • wordpress插件排名快速seo优化
  • 网站建设 常见问题广告营销是做什么的
  • 做百度收录的网站电商网站卷烟订货流程
  • 重庆建设工程公司网站网址收录平台
  • 大连手机网站开发网站友情链接有什么用
  • 网站建设要做哪些中央广播电视总台
  • 网站的价值与网站建设的价格成都做整站优化
  • 做网站现在什么最赚钱吗google下载
  • mirana wordpress优化营商环境工作开展情况汇报
  • 简阳网站建设制作公司网站大概多少钱
  • 详情页设计说明seo关键词优化的技巧和方法
  • 十堰网站建设网站seo检测
  • 北京建设职工大学网站今日最新足球推荐
  • 做网站鼎盛长春seo推广
  • 网站建设管理汇报搜索引擎平台
  • 网站开发中常见的安全漏洞乐事薯片软文推广
  • 中国疫情又爆发了aso优化平台有哪些
  • 广州模板建站系统做网站哪个公司最好