`
- 浏览:
923892 次
- 性别:
- 来自:
杭州
-
一。直接插入排序
1。直接插入排序:
直接插入排序是一种简单的排序方法,它的基本思想是将待排序的记录按照其值的大小插入到已排好序的有序表的适当位置,直到全部插入完为止。举个整型的排序例子
2。直接插入排序的伪代码:
insertionsort(data[])
for i=1 to data.length-1
tmp=data[i];
将所有大于tmp的元素data[j]向后移动一位;
将tmp放在正确的位置上;
3.简单例子,以整型为例。
A)ruby语言实现:
def insertion_sort(a)
i=1
while i<a.length
tmp=a[i]
j=i
while j>0
break if tmp>a[j-1]
a[j]=a[j-1]
j-=1
end
a[j]=tmp
i+=1
end
end
a=[10,2,3]
insertion_sort(a)
a.each{|i | print i.to_s+" "}
B)java语言实现:
package com.sohu.blog.denns_zane.sort;
public class InsertSort{
public static void main(String args[]){
int []data={12,2,3,56,90};
insertsort(data);
for(int i=0;i<data.length;i++){
System.out.print(data[i]+" ");
}
}
public static void insertsort(int []data){
for(int i=1,j;i<data.length;i++){
int tmp=data[i];
for(j=i;j>0&&tmp<data[j-1];j--)
data[j]=data[j-1];
data[j]=tmp;
}
}
}
5。算法复杂度:
最好情况:进行n-1次比较和2(n-1)次移动,尽管他们其实都是多余的,复杂度O(n)
最坏情况:具体计算略,O(n*n)
平均情况:O(n*n),也就是接近最坏情况,在平均情况下,数组大小翻倍,它的排序工作将是原来的4倍。
二。选择排序
1。算法描述:选择算法试图先查找一个放错位置的元素并将它放到最终位置上,以此来局部化数组元素的交换。选择值最小的元素并将它和第一个位置上的元素交换。在第i步中,查找data[i],...,data[n-1]中的最小元素,并将它和data[i]进行交换。重复此过程,直到所有的元素都放入正确的位置为止。
2。伪代码描述:
selectionsort(data[])
for i=0 to data.length-2
从data[i],,data[n-1]中选取最小的元素
将它和data[i]交换
3。实现,以整型数组为例:
1)ruby语言实现:
def selection_sort(a)
least=0
for i in (0..(a.length-2))
j=i+1
least=i
while j<a.length
if a[j]<a[least]
least=j
end
j+=1
end
a[least],a[i]=a[i],a[least] unless least==i #交换
end
end
a=[12,4,34,23,45,35]
selection_sort(a)
a.each{|i| print i.to_s+" "}
代码很好理解,不做解释。
2)java语言实现:
package com.sohu.blog.denns_zane.sort;
public class SelectionSort{
public static int[] selection_sort(int [] data){
int i,j,least=0;
for(i=0;i<data.length-1;i++){
for(j=i+1,least=i;j<data.length;j++)
if (data[j]<=data[least])
least=j;
if (least!=i)
swap(data,least,i); //½»»»data[i]ºÍ×îСԪËØ
}
return data;
}
public static void swap(int[]data,int least,int i){
int tmp=data[least];
data[least]=data[i];
data[i]=tmp;
}
public static void main(String args[]){
int[] t={10,29,12,23,56};
selection_sort(t);
for(int i:t){
System.out.print(i+" ");
}
}
}
4.算法效率:
任何情况下,都需要进行n*(n-1)/2次比较,也就是O(n*n)的复杂度
最好情况:数组已经排序,不需要交换任何元素
最坏情况:最大元素在第一个位置而其他元素有序时,需要进行3*(n-1)次交换,即O(n),也是很好的结果
三。冒泡排序
1。算法伪代码描述:
bubblesort(data[])
for i=0 to data.length-2
for j=data.length-1 downto i+1
如果顺序错误,就交换j和j-1位置上的元素
2。实现:
1)ruby语言实现:
def bubble_sort(data)
for i in (0..(data.length-2))
j=data.length-1
while j>i
if data[j]<data[j-1]
data[j],data[j-1]=data[j-1],data[j] #交换
end
j-=1
end
end
end
a=[12,3,56,7,89,87]
bubble_sort(a)
a.each{|i| print i.to_s+" "}
2)java语言实现:
package com.sohu.blog.denns_zane.sort;
public class BubbleSort{
public static void bubble_sort(int [] data){
for(int i=0;i<data.length-1;i++)
for(int j=data.length-1;j>i;j--)
if(data[j]<data[j-1])
swap(data,j,j-1);
}
public static void swap(int[]data,int least,int i){
int tmp=data[least];
data[least]=data[i];
data[i]=tmp;
}
public static void main(String args[]){
int[] t={10,29,12,23,56};
bubble_sort(t);
for(int i:t){
System.out.print(i+" ");
}
}
}
3。算法效率:
冒泡排序的比较次数近似是插入排序的两倍,和选择排序相同;移动次数和插入排序相同,是选择排序的n倍。可以说,插入排序比冒泡排序快两倍。
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大时使用。 合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为...
以单链表为存储结构实现简单选择排序的算法
选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放...
快排算法的简单实现。 快速排序是实际运用中用的最多的算法,虽然它在最坏的情况下会达到n^2,但它的平均性能非常好,期望时间复杂度为nlgn,而且隐含的常数因子非常小,并且是原址排序。 快速排序原理:从一组数...
这是对直接插入方法,简单选择排序,简单交换(冒泡)算法的介绍和实现.
冒泡排序 简单选择排序 c语言基础 排序算法 数组操作 排序算法实验 简单的c语言程序 排序算法输出
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
VC++ 简单选择 排序 一种简单容易实现的排序算法
1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组不同的输入数据作比较;比较...
C++排序算法,用简单方便的算法,实现排序。
VC++简单插入排序 一种简单容易实现的排序算法
简单的堆排序算法:以定长数组为例,动态数组等可以以此类推
第一部分是简单排序算法,后面你将看到他们的共同点是算法复杂度为O(N*N)(因为没有 使用word,所以无法打出上标和下标)。 第二部分是高级排序算法,复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种 ...
数组应用之桶排序课件,用于信息学奥赛基础算法上课应用。课件内容讲解了桶排序的基本思想,问题应用,知识扩展及多维桶等。
Java语言实现的简单比较排序算法,代码里头有详细注释,注释皆为简单英文,因为这个算法比较简单,欢迎新手下载学习使用,欢迎后期的学习交流!
最快的排序算法 最简单的排序算法,排序算法数据结构(01)
最快的排序算法 最简单的排序算法,排序算法数据结构(02)
四种简单的排序算法,简单排序,快速选择排序,希尔排序
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!