共有回帖数 0 个
-
从小学5年级学习编程开始，已经过了5个春秋。
感觉收获了很多很多。
我最初接触的语言是pascal，后来自学了c，对c#，java等也有一定研究。
在这里总结一下排序算法，各种冷门的算法
字要一点点码，可能比较慢。
以下所有代码统一使用伪代码（承认有点偷懒。。）但也是为用其他语言的人一点点考虑。。
首先，排序算法有很多种。可以分为基于比较的与基于地址的。
比较就是比较元素大小，交换位置。
地址就比如计数排序了、、
比较算法Ω（nlog2n）是极限了，算法导提到用决策树证明。我们这里不讨论它。
地址的很多都是线性期望界。。。
从最简单，大家最熟悉的算法讲起吧。
冒泡排序（这段是从维基百科抄的）
Bubble Sort
是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对
个项目需要O(
)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。 冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要
次交换，而插入排序只要最多
交换。冒泡排序的实现（类似下面）通常会对已经排序好的数列拙劣地执行（
），而插入排序在这个例子只需要
个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部循环第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到
。在这个情况，在已经排序好的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以稍微地改进效率。有时候称为往返排序，因为算法会从数列的一端到另一端之间穿梭往返。 冒泡排序算法的运作如下：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 由于它的简洁，冒泡排序通常被用来对于程式设计入门的学生介绍算法的概念。
——————————————————————————————————————
抄了一些思想的，这些基本的相信只要不是一点不懂的都能 看懂的。。
我也写一下伪代码
Bubble_Sort(A)
for i-1 to A.length-1 do
for j-i+1 to A.length do
if AA[j] then
exchange A-A[j]
它是各种排序代码的基础
选择排序
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
最好是在数据有序时，n
最坏n^2
平均n^2
根据个人经验,会比冒泡排序快那么一点，因为比较次数差不多，交换次数少多了。交换大概需要3个单位时间的。。。
附上伪代码
Select_Sort(A)
__for i- 1 to A.length-1 do
____max-i
____for j-i+1 to A.length do
______if A[j]A[max] then
________max-j
____exchange A-A[max]
下划线是为了防止度娘吞空格
插入排序
步骤如下：
1从第一个元素开始，该元素可以认为已经被排序
2取出下一个元素，在已经排序的元素序列中从后向前扫描
3如果该元素（已排序）大于新元素，将该元素移到下一位置
4重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5将新元素插入到该位置后
重复步骤2~5...
伪代码如下：
Insert_Sort(A)
__For i-2 to A.length
____j-1
______while A[j]A
________j-j+1
____temp-A
____for k-j+1 to j
______A[j]-A[j-1]
____A[j]-temp
插入排序用的不是很多。。至少我身边人是这样
找插入点过程中，用二分查找似乎会快一点，但写起来非常麻烦，而且用线性表（数组）不可避免要n^2.因为后移非常麻烦，而用链表的话，二分查找要基于地址来做，没办法弄二分查找。总之鱼和熊掌不可兼得，优化起来很麻烦……
快速排序
对区间A[X..Y]，取基准mid，对其就地排序，使a[X..K]内全小于mid，a[k+1,Y]全大于等于mid。递归调用自身，使左右区间全部有序。
伪代码如下
Quick_Sort(A,X,Y)
__i-x
__j-y
__mid-A[y] Δ注意不能写成mid-Y
__while (true)
____while Amid
______i-i+1
____while A[j]mid
______j-j-1
____if ij
______then exchange A-A[j]
______else return
__if x+1=y then return
__Quick_Sort(x,j)
__Quick_Sort(i,y)
不过这么实现能够将基准定位，c语言如下：
void quick_sort(int a[], int left, int right)
{
int i = left + 1, j = right;
int key = a[left];
if (left = right) return;
/* 从i++和j--两个方向搜索不满足条件的值并交换 *
* 条件为：i++方向小于key，j--方向大于key */
while (1) {
while (a[j] key) j--;
while (a key) i++;
if(i = j) break;
swap(&a,&a[j]);
if(a==key)j--;
else i++;
}
/* 关键数据放到‘中间’ */
swap(&a[left],&a[j]);
if(left i - 1) quick_sort(a, left, i - 1);
if(j + 1 right) quick_sort(a, j + 1 , right);
}
这上面给的划分算法是horer提出的。
不过个人对intro的更有爱一些，因为更容易理解：
Quick_Sort(A,x,y)
__j-x
__for i-x to y-1
____if A[r]A then
______exchange A-A[j]
______j-j+1
__exchange A[r]-A[j]
__if x+1=y then return
__Quick_Sort(A,x,j-1)
__Quick_Sort(A,j+1,y)Sort(A,x,y)
Pretiton(A,x,y)
if x+1=y
then return
Sort(A,x,x+下取整(y-x-1)/2)
Sort(A,x+下取整(y-x-1)/2+1,y)
Pretiton(A,x,y)
for i←0 to 下取整(y-x-1)/2
if A[x+i]A[y-i]
then
exchange A[x+i]←-A[y-i]
if x+1=y
then return
Pretiton(A,x,x+下取整(y-x-1)/2)
Pretiton(A,x+下取整(y-x-1)/2+1,y)
for i←0 to 下取整(y-x-1)/2
if A[x+i]A[y-i]
then
exchange A[x+i]←-A[y-i]
if x+1=y
then return
时间上的常数因子与快排平均情况相近，但平均情况比快排更好的~
证明
n个数，SOrt要T1(n) pretitong要t2(n)
那么
t1(n)=O(1) t=1
=2*T1(n/2)+T2(n) t∈(1,+∞)
t2(n)=O(1) t=1
=2*T2(n/2)+O(n) t∈(1,+∞)
解得
t2(n)=O(nlog2n)
t1(n)=O(n（log2n）^2)
t1时间与快排平均情况类
那我来介绍一种有趣的算法了：珠排序
珠排序是一种自然排序算法，由Joshua J. Arulanandham, Cristian S. Calude 和 Michael J. Dinneen 在2002年发展而来，并且在欧洲理论计算机协会（European Association for Theoretical Computer Science，简称EATCS）的新闻简报上发表了该算法。无论是电子还是实物上的实现，珠排序都能在O(n)时间内完成；然而，该算法在电子上的实现明显比实物要慢很多，并且只能用于对正整数序列进行排序。并且，即使在最好的情况，该算法也需要O(n2) 的空间。
在珠排序中，一行表示一个数字。如果一行里有2颗珠子，该行代表数字2；如果一行里有4颗珠子，该行代表数字4。给定一个数组，数组里有多少个数字，就要有多少行；数组里最大的数字是几，就要准备多少根杆子。准备就绪后，释放珠子，珠子（按重力）下落，就完成了排序。珠排序可以类比于珠子在平行的竖直杆上滑动，就像算盘一样，然而，每一竖直杆都有珠子数目的限制。因此，初始化就相当于在竖直的杆上悬挂珠子，在第一步中，排列就被显示为n=5行的珠子在m=4列队竖直杆上。每一行右边的数字意味着该行在问题中被表示的数；第1，2行表示正整数3（因为它们都有3个珠子）而顶层的一行表示正整数2（因为它只含有2个珠子）。如果我们要允许珠子掉落，那么每行表示已排序的整数。第1行表示在集合中最大的数，而第n行表示最小的数。如果按照前面提到的规则（行包含一系列在竖直杆1到k的珠子，并且让k+1到m竖直杆都空），那么它会出现这种情况。允许珠子掉落的行为在物理意义上就是允许珠子从高的行掉落至低的行。如果被行a表示的值小于被行a+1表示的值，那么一些珠子就会从a+1掉落至a；因为行a不包含足够的珠子防止珠从a+1行掉落，所以这一定会发生。用机械装置实现的珠排序类似于计数排序；每一杆上的数字与那些在所有数中等于或少于该数字的数量相当。
可以是以下复杂度级别：
O(1)：即所有珠子都同时移动，但这种算法只是概念上的，无法在计算机中实现。
O(
)：在真实的物理世界中用引力实现，所需时间正比于珠子最大高度的平方根，而最大高度正比于n。
O(n)：一次移动一列珠子，可以用模拟和数字的硬件实现。
O(S)，S是所有输入数据的和：一次移动一个珠子，能在软件中实现。
楼主 2016-04-09 18:01 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
