数据结构与算法系列十（排序算法概述）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构与算法系列十（排序算法概述），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3854字，纯文字阅读大概需要6分钟。

内容图文

1.引子

1.1.为什么要学习数据结构与算法？

有人说，数据结构与算法，计算机网络，与操作系统都一样，脱离日常开发，除了面试这辈子可能都用不到呀！

有人说，我是做业务开发的，只要熟练API，熟练框架，熟练各种中间件，写的代码不也能“飞”起来吗？

于是问题来了：为什么还要学习数据结构与算法呢？

#理由一：
    面试的时候，千万不要被数据结构与算法拖了后腿
#理由二：
    你真的愿意做一辈子CRUD Boy吗
#理由三：
    不想写出开源框架，中间件的工程师，不是好厨子

1.2.如何系统化学习数据结构与算法？

我想好了，还是需要学习数据结构与算法。但是我有两个困惑：

1.如何着手学习呢？

2.有哪些内容要学习呢？

学习方法推荐：

#学习方法
1.从基础开始，系统化学习
2.多动手，每一种数据结构与算法，都自己用代码实现出来
3.思路更重要：理解实现思想，不要背代码
4.与日常开发结合，对应应用场景

学习内容推荐：

数据结构与算法内容比较多，我们本着实用原则，学习经典的、常用的数据结构、与常用算法

#学习内容：
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
    数组、链表、栈、队列
    散列表、二叉树、堆
    跳表、图
5.常用算法
    递归、排序、二分查找
    搜索、哈希、贪心、分治
    动态规划、字符串匹配

2.考考你

在前面两篇，我们详细看了常用算法的第一个主题：递归。接下来我们来看常用算法的第二个主题：排序。排序内容有点多，常见的排序算法就有：冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序。

这些排序算法中，不知道有没有你熟悉的，或者不熟悉的。让我们开启排序算法之旅吧。首先第一篇中，我们先来对排序算法做一个总体上的认识。

#考考你：
1.你知道常用的排序算法有哪些吗？
2.你知道如何衡量排序算法的优劣吗？
3.你知道排序算法的基础概念：有序度、逆序度、满有序度吗？

3.案例

3.1.排序算法分类

在考考你中，我们说排序算法有：冒泡排序、插入排序、选择排序、归并排序、快速排序、桶排序、计数排序、基数排序。这样看起来有点散乱，能不能给它们归一下类呢？答案是可以的。

对于排序算法，我们可以从时间复杂度上进行归类：

 

 

 

3.2.从三个角度分析排序算法

在实际软件开发中，有众多的排序算法，如何选择和取舍呢？真的会有选择困难症啊！有没有一些好的、可行的方法，去综合衡量排序算法的优劣呢？

答案是：有

我们可以从三个角度去综合分析排序算法：时间复杂度、空间复杂度、算法稳定性

#时间复杂度
  1.分析最好情况、最坏情况、平均情况时间复杂度
  2.复杂度分析中，关于系数、常数、低阶平常可以省略
  3.但是，需要特别注意：在排序算法中，我们需要考虑进来

#空间复杂度
  1.空间复杂度分析，主要看是否是：原地排序算法
  2.原地排序算法，是指：空间复杂度是O(1)
  3.注意：在实际软件开发中，这一条很重要

#算法稳定性
  1.算法稳定性，是指如果待排序序列中，有值相同的元素
  2.如果经过排序后，原来值相同的元素，顺序保持不变
  3.那么我们说，该排序算法是稳定的排序算法
  4.否则，该排序算法是不稳定排序算法
  
  5.比如，有一个待排序序列：3,6,5,2,6,8
  6.待排序序列中，有两个值为6的元素
  7.假设用数组a来存储，对应的下标是：a[1]=6,a[4]=6
  8.排序后：a[3]=6,a[4]=6
  9.这里的a[3]是排序前的a[1]
  10.这里的a[4]还是排序前的a[4]
  11.这就是稳定排序算法的要求，如下图：

理解排序算法稳定性：

 

 

3.3.排序基础概念：有序度、逆序度、满有序度

在排序算法中，我们需要关注三个基础概念：有序度、逆序度、满有序度。

整个排序过程，我们可以理解为：增加有序度，减少逆序度，最终达到满有序度的过程。

那么，它们具体的含义是什么呢？

#有序度：
  待排序序列中，如果下标索引：i<j，且a[i]<a[j],则称为有序度
#逆序度
  待排序序列中，如果下标索引：i<j，且a[i]>a[j],则称为逆序度
#满有序度
  1.待排序序列中，如果有序度达到：n(n-1)/2，则称为满有序度
  2.即此时待排序序列，其实是有序的

以上关于有序度、逆序度的概念，相信很多朋友都能理解。这里我们解释一下关于满有序度的公式：n(n-1)/2。

要理解满有序度的概念，你可能需要回顾一下数学中的：排列、组合知识点，应该是在高二的时候学的，可以这样去理解它们：

#排列：
  1.有n个元素，如果每两个元素，组成一个排列
  2.则总共有排列数：n(n-1)
  3.比如，有3个元素：a b c
  4.每两个元素组成排列数是：3*(3-1)=6
  5.组成的排列有：(a,b) (a,c) (b,a) (b,c) (c,a) (c,b)
  
#组合：
  1.有n个元素，如果每两个元素，组成一个组合
  2.则总共有组合数：n(n-1)/2
  3.比如，有3个元素：a b c
  4.每两个元素组成的组合数是：3(3-1)/2=3
  5.组成的组合有：(a,b) (a,c) (b,c)
  
#综合结论：
   1.假设待排序序列有n个元素
   2.如果有序度，等于每2个元素的组合数：n(n-1)/2
   3.那么该待排序序列，其实是有序的
   4.这就是满有序度的概念

 

内容总结

以上是互联网集市为您收集整理的数据结构与算法系列十（排序算法概述）全部内容，希望文章能够帮你解决数据结构与算法系列十（排序算法概述）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---