常见的几种排序算法总结
对于非科班生的我来说,算法似乎对我来说是个难点,查阅了一些资料,趁此来了解一下几种排序算法。
首先了解一下,什么是程序
关于排序算法通常我们所说的往往指的是内部排序算法,即数据记录在内存中进行排序。
排序算法大体可分为两种:
一种是比较排序,时间复杂度O(nlogn) ~ O(n^2),主要有:冒泡排序,选择排序,插入排序,归并排序,堆排序,快速排序等。
另一种是非比较排序,时间复杂度可以达到O(n),主要有:计数排序,基数排序,桶排序等
冒泡排序它重复地走访过要排序的元素,一次比较相邻两个元素,如果他们的顺序错误就把他们调换过来,直到没有元素再需要交换,排序完成。这个算法的名字由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。
选择排序类似于冒泡排序,只不过选择排序是首先在未排序的序列中找到最小值(最大值),放到序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾,以此类推,直到所有元素均排序完毕。
插入排序比冒泡排序和选择排序更有效率,插入排序类似于生活中抓扑克牌来。
插入排序具体算法描述,以数组[3, 2, 4, 5, 1]为例。
前面三种排序算法只有教学价值,因为效率低,很少实际使用。归并排序(Merge sort)则是一种被广泛使用的排序方法。
它的基本思想是,将两个已经排序的数组合并,要比从头开始排序所有元素来得快。因此,可以将数组拆开,分成n个只有一个元素的数组,然后不断地两两合并,直到全部排序完成。
以对数组[3, 2, 4, 5, 1] 进行从小到大排序为例,步骤如下:
有了merge函数,就可以对任意数组排序了。基本方法是将数组不断地拆成两半,直到每一半只包含零个元素或一个元素为止,然后就用merge函数,将拆成两半的数组不断合并,直到合并成一整个排序完成的数组。
快速排序(quick sort)是公认最快的排序算法之一,有着广泛的应用。
快速排序算法步骤
参考:
常用排序算法总结(一)
阮一峰-算法总结
快速排序算法
快速排序(Quicksort)是对冒泡排序的一种改进。然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。快速排序算法通过多次比较和交换来实现排序,其排序流程如下:(1)首先设定一个分界值,通过该分界值将数组分成左右两部分。(2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。