来自 威尼斯国际官方网站 2019-10-04 13:38 的文章
当前位置: 威尼斯国际官方网站 > 威尼斯国际官方网站 > 正文

威尼斯国际官方网站:中快速排序的学习,排序

最近看了一句话,说的是在现实生活中,会写字的人不见得会写出好文章,学习编程语言就像是学会了写字,学会了编程语言并不一定能写出好程序。

废话不多说,直接上图:

我觉得就是很有道理,以前读书的时候,基本学完了C#中的语法知识,算是入了个门,但是一到写程序就毫无头绪,做出来的程序就像是小学生日记,仅仅只是用一些简单的api把功能拼凑起来,没有一点逻辑性,毫不美观优雅。

威尼斯国际官方网站 1

所以我决定慢慢的开始学习算法知识,虽然我数学很烂,逻辑能力差到极点,看这些算法的代码看的我是心态爆炸,真的头皮发麻,只有长期坚持学习,一点一点的慢慢进步了。

20160916153212716.png

 

图片名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存
(本文代码戳这里)

快速排序是分治法中的一种常见排序算法,主要运用递归求解。

1.冒泡排序

大多数人接触的第一个算法估计就是冒泡排序了,不再赘述。
冒泡也有改进:
1.在某次遍历中如果没有数据交换则说明全部有序,后续的遍历就可以省去。
2.保存最后一次进行交换的位置,下一次比较到此处就停止。
3.鸡尾酒排序,从底到高然后从高到底。

算法思想是将一个数组分为小于等于基准数的子数组和大于基准数的子数组,然后通过递归调用,不断对这两个子数组进行排序,直到数组元素只有0个或1个元素时,停止递归,再将各个排好序的子数组加起来,最终就得到了排好序的数组。

2.选择排序

选择排序就是每次选择数组中最大(小)的数放到数组最后(理解意思即可)。表现稳定(无论给定的数组是怎样的都是O(n2))

 

3.插入排序

每次都将一个待排序的数插入到前面已经排好序的子序列中的适当位置,知道全部插入完毕。
改进:待插入的元素之前的序列是已排好序的,结合二分查找进行。

步骤如下:

4.希尔排序

希尔排序是插入排序的改进,插入排序每次只能移动一步,而希尔排序每次可以向前移动一大步,之后再取小步数移动,到最后就成了插入排序,但此时序列几乎已经排好了,此时再进行插入排序会很快。

1. 选择一个基准值

5.归并排序

归并排序是创建在归并操作上的一种有效的排序算法,效率为O(nlogn),归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用,我们将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作。

2. 将数组分为两个子数组:小于基准值的元素和大于基准值的元素

6.快速排序

在平均状况下,排序n个元素要O(nlogn)次比较。在最坏状况下则需要O(n^2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他O(nlogn)算法更快,因为它的内部循环可以在大部分的架构上很有效率地被实现出来。

快速排序使用分治策略(Divide and Conquer)来把一个序列分为两个子序列。步骤为:

  • 从序列中挑出一个元素,作为"基准"(pivot).
  • 把所有比基准值小的元素放在基准前面,所有比基准值大的元素放
    基准的后面(相同的数可以到任一边),这个称为分区(partition)操作。
  • 对每个分区递归地进行步骤1~3,递归的结束条件是序列的大小是0或1,这时整体已经被排好序了。
    快排优化
    对于分治算法,当每次划分时,算法若都能分成两个等长的子序列时,那么分治算法效率会达到最大。也就是说,基准的选择是很重要的。选择基准的方式决定了两个分割后两个子序列的长度,进而对整个算法的效率产生决定性影响。

3. 对这两个子数组进行排序

7.堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构(通常堆是通过一维数组来实现的),并同时满足堆的性质:即子结点的键值总是小于(或者大于)它的父节点。
我们可以很容易的定义堆排序的过程:

  • 创建一个堆
  • 把堆顶元素(最大值)和堆尾元素互换
  • 把堆的尺寸缩小1,并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
  • 重复步骤2,直到堆的尺寸为1

 

8.计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

接着对子数组重复以上3步,直到子数组无法分解(子数组只有0个或1个元素时)

9.基数排序

基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;

  • 取得数组中的最大数,并取得位数;
  • arr为原始数组,从最低位开始取每个位组成radix数组;
  • 对radix进行计数排序(利用计数排序适用于小范围数的特点);

 

10.桶排序

桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)

  • 设置一个定量的数组当作空桶;
  • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  • 对每个不是空的桶进行排序;
  • 从不是空的桶里把排好序的数据拼接起来。

可以使用函数递归重复上述过程,在递归函数中必须满足2个条件

1.基线条件——指满足某个条件以后,函数不在调用自身进行递归

2.递归条件——满足递归条件就调用自身函数进行递归

 

本文由威尼斯国际官方网站发布于威尼斯国际官方网站,转载请注明出处:威尼斯国际官方网站:中快速排序的学习,排序

关键词: