基于fortran的算法系列--5.排序算法

首先，由于fortran语言的局限性，贪心算法、广度优先、深度优先搜索、爬山法、回溯su算法、分支界限等实现起来比较麻烦，不做分享。一是有些懒，二是这些东西都可以采用暴力遍历解决，只是时间问题。
下面是经典的排序算法：
注：除了代码，其余东西来自网络。
1、选择排序
首先，找到数组中最小的那个元素，其次，将它和数组的第一个元素交换位置(如果第一个元素就是最小元素那么它就和自己交换)。其次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。


2、插入排序
2.1从数组第2个元素开始抽取元素。
2.2把它与左边第一个元素比较，如果左边第一个元素比它大，则继续与左边第二个元素比较下去，直到遇到不比它大的元素，然后插到这个元素的右边。
2.3继续选取第3，4，….n个元素,重复步骤 2 ，选择适当的位置插入。


3、冒泡排序
3.1把第一个元素与第二个元素比较，如果第一个比第二个大，则交换他们的位置。接着继续比较第二个与第三个元素，如果第二个比第三个大，则交换他们的位置….
3.2我们对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样一趟比较交换下来之后，排在最右的元素就会是最大的数。
3.3除去最右的元素，我们对剩余的元素做同样的工作，如此重复下去，直到排序完成


4、希尔排序
思想是采用插入排序的方法，先让数组中任意间隔为 h 的元素有序，刚开始 h 的大小可以是 h = n / 2,接着让 h = n / 4，让 h 一直缩小，当 h = 1 时，也就是此时数组中任意间隔为1的元素有序，此时的数组就是有序的了。
需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序，而是轮流对每个组进行排序。

5、归并排序
把大的数组分成两个，然后对这两个数组分别进行排序，之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的，所以在合并的时候是很快的。其思想是分治算法

6、快速排序
6.1从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。
6.2从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

7、堆排序

8、计数排序（Counting Sort）
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
8.1找出待排序的数组中最大和最小的元素；
8.2统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
8.3对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
8.4反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。

9、桶排序
桶排序就是把最大值和最小值之间的数进行瓜分，例如分成10个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，可以采用归并排序，也可以采用快速排序之类的。
之后每个桶里面的数据就是有序的了，我们在进行合并汇总。
桶例：一位数桶，两位数桶，三位数桶...

10、基数排序
先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小……
排到最后，就是一组有序的元素了。不过，他在以某位数进行排序的时候，是用“桶”来排序的。
由于某位数（个位/十位….，不是一整个数）的大小范围为0-9，所以我们需要10个桶，然后把具有相同数值的数放进同一个桶里，之后再把桶里的数按照0号桶到9号桶的顺序取出来，这样一趟下来，按照某位数的排序就完成了

这里面还是快速排序最常用……
直接一个sort

谢谢分享

回复看看

谢谢分享

感谢楼主

谢谢分享

感谢楼主

谢谢分享

看着很不错，回复一个看看