交换排序,插入排序和选择排序都是很简单也很基础的排序算法。在世面上各种各样的算法和数据结构的书中都很轻易地找的到他们的踪影。在这儿写出来不外乎是加深自己的印象,也为有需要的朋友做一个参考。
1 交换排序
交换排序是一种很简单的排序方法。其主要思想如下:
(1)利用要排序范围中的第0个数据d[i]与范围中其它数据d[j]相比较。如果前面的数据比后面大,那么就交换这两个数据(就是把较小的数据放在第0个位置)。然后再和排序范围内下一个数据d[j+1]相比较。依此类推。
(2)当执行完步骤(1)后,最小值即位于范围中的第0个位置。然后在剩下的数据中找到一个最小的,放在第1个位置,这样循环查找下去直到所有数据结束,最后可以得到由小到大的排序结果。
交换排序的思想和冒泡排序的思想很类似,实现的代码也非常相似。下面是一个简单的说明例子。
假设要排序的数据是:6 2 5 1 3 4
步骤一:
因为6>2,所以2和6交换
2 6 5 1 3 4
步骤二:因为2<5,所以不交换
2 6 5 1 3 4
步骤三:因为2>1,所以交换
1 6 5 2 3 4
步骤四:因为1<3,所以不交换
1 6 5 2 3 4
步骤五:因为1<4,所以不交换
1 6 5 2 3 4
这样我们叫找到了最小值1,按照同样的办法,就可以找到第二个,第三个最小值。。完成排序。
实现代码非常简单,如下所示:
/// <summary>
/// 交换排序的思想非常简单,从第一个数据开始,在剩下的数据中找
/// 比它小的数据,如果找到了,就交换两者。
/// 第一次查找可以找到最小的数据,和第0个数据交换
/// 第二次在剩下的n-1个数据中查找,找个最小的和第一个数据交换
/// 依次交换剩下的所有数据使之有序
/// </summary>
/// <param name="myArray"></param>
public static void ExchangeSort(int [] myArray)
{
int i, j;
for(i=0; i<myArray.Length-1; i++) //从第0个数据开始
{
for(j=i+1; j<myArray.Length; j++)//在剩下的数据中循环
{
if(myArray[j] < myArray[i]) //如果有比它小的,交换两者
{
Swap(ref myArray[j], ref myArray[i]);
}
}
}
}
2 选择排序
选择排序也是很简单的排序方法之一。其主要思想如下:
(1)第一次在数组中查找出最小的值a[i],将其和第0个位置交换。
(2)此时剩下n-1个值,同样从中找出最小的值a[j],a[j]和第一个数据交换
(3)重复上面的步骤,在剩下的范围中找出最小的值和最小数组下标的值进行交换。
一般会设置一个额外变量small来记录最小值的下标,以便于在循环之后,交换指定位置和最小值位置的值。根据上面的描述,我们可以很容易地就写出选择排序的算法。
/// <summary>
/// 选择排序的中心思想是每次都从未排序的数据中选出最小的数据,
/// 和未排序数据的第一个数据交换。
/// 第一次选出最小的数据放在第0个位置
/// 第二次在剩下的n-1个数据中选出最小的数据放在第一个位置
/// 依次下去,将所有数据排序
/// </summary>
/// <param name="myArray"></param>
public static void SelectSort(int [] myArray)
{
int i, j, small;
for(i=0; i<myArray.Length-1; i++) //数据起始位置,从0到倒数第二个数据
{
small = i; //记录最小数据的下标
for(j=i+1; j<myArray.Length; j++) //在剩下的数据中寻找最小数据
{
if(myArray[j] < myArray[small])
{
small = j; //如果有比它更小的,记录下标
}
}
Swap(ref myArray[i], ref myArray[small]); //将最小数据和未排序的第一个数据交换
}
}
3 插入排序
插入排序也是一种原理非常简单的排序方法,属于插入方法的排序。其主要思想如下:
(1)首先从第一个数据开始,将该值插入到其前面已经排好序的数据当中。插入的位置是第一个大于该数据的记录的前面。如果没有大于它的数据,就将其放在排好序的数据的最后。由于现在排序尚未开始,因此只有第1个元素。
(2)接着是第二个元素,用步骤1的方法插入到大于它的数的前面。现在第一个,第二个数据都是有序的了。
(3)依次可以排第三个,第四个数据,直到所有的数据完全排好序。可以从下面例子看出详细的过程。
还是假设要排序的数字为:6 2 5 1 3 4
步骤1:移动第一个
6 2 5 1 3 4
步骤2:移动第二个,因为2<6,所以将2放在6前面
2 6 5 1 3 4
步骤3:移动第三个,因为2<5<6,所以将5放在6前面
2 5 6 1 3 4
步骤4:移动第四个,因为1<2<5<6,所以将1放在最前面
1 2 5 6 3 4
步骤5:移动第五个,因为2<3<5<6,所以将3放在2后面
1 2 3 5 6 4
步骤6:移动第六个,因为3<4<5<6,所以将4将在3后面
1 2 3 4 5 6
这样所有的数据就都排好序了。
其实现的算法如下:
/// <summary>
/// 插入排序的中心思想在于将未排序的数据插入一个有序表中
/// 第一次将第一个数据放入一个有序表中,该有序表只有一个数据
/// 第二次将第二个数据插入有序表中,使之小的在前,大的在后
/// 第三次将第三个数据插入有序表中
/// 依次下去,将所有数据放入有序表中
/// </summary>
/// <param name="myArray"></param>
public static void InsertSort(int[] myArray)
{
int i, j, temp;
for(i=1; i<myArray.Length; i++)
{
temp = myArray[i]; //保存当前数据
j = i-1;
//将数据插入有序表中,如果表中的数据比该数据大,
//那么就依次向后移动有序表中的数据,直到找到第一个比它小的数据,
//将它放在那个数据后面
while(j>=0 && myArray[j]>temp)
{
myArray[j+1] = myArray[j];
j--;
}
myArray[j+1] = temp; //将数据插入有序表中
}
}
4 效率比较
在实现这三种算法以后,这三种算法都是O(n^2)的算法。效率并不高。还是做个小小的试验来验证一下效率,还是使用1+1中的随机数来测试,可以得到下表,看到这几种算法的效率区别。单位为毫秒
|
500随机数 |
5000随机数 |
20000随机数 |
基本冒泡 |
1.5625 |
160.9375 |
2457.8125 |
交换排序 |
1.5625 |
118.75 |
1895.3125 |
选择排序 |
1.5625 |
68.75 |
1081.25 |
插入排序 |
1.5625 |
34.375 |
543.75 |
从上面的表格中可以看到,插入排序比其余的几种排序方法快得多。在数据量越大的时候越明显。还有更快的排序方法吗?答案是肯定的。
/******************************************************************************************
*【Author】:flyingbread
*【Date】:2007年1月27日
*【Notice】:
*1、本文为原创技术文章,首发博客园个人站点(
http://flyingbread.cnblogs.com/),转载和引用请注明作者及出处。
*2、本文必须全文转载和引用,任何组织和个人未授权不能修改任何内容,并且未授权不可用于商业。
*3、本声明为文章一部分,转载和引用必须包括在原文中。
******************************************************************************************/
分享到:
相关推荐
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort 插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序...
从排序的基本概念讲起,详细讲解了插入排序、交换排序、选择排序、归并排序等排序算法的原理以及实现代码
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
实现了四类排序算法,插入排序、交换排序、选择排序、归并排序,详情请看文档,其中 树形选择排序算法--选择排序、 堆排序--选择排序 这两种算法还没实现,有兴趣的自行解决
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高。 介绍一些排序的基本算法.包括交换法,冒泡法等等...
If NoSwap Then Return//本趟排序中未发生交换,则终止算法// end End; //BubbleSort// 该算法的时间复杂性为O(n2),算法为稳定的排序方 冒泡排序-冒泡排序法的改进 比如用冒泡排序将4、5、7、1、2、3这6个数...
这是对直接插入方法,简单选择排序,简单交换(冒泡)算法的介绍和实现.
C语言排序算法
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
合并排序的合并算法一般是异地交换,本文件通过本地交换和异地交换两种方式实现了合并排序,在VC开发环境下验证通过
经典排序算法,有选择排序,冒泡排序,交换排序,谢尔排序,插入排序基数排序
内部排序算法比较 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 ...
java实现的常用的几种基本排序算法,插入、交换、选择、归并
利用C++实现了常用的排序算法,包括:冒泡排序、插入排序、选择排序、归并排序、快速排序、0-交换排序。利用简单的数字序列排序为例,希望能帮助对以上算法有更深理解。
经典的数据结构 交换排序算法 非常实用 可以给初学者使用 也可以作为工具提供给编程人员
1.直接插入排序--增量法 2.希尔排序 3.交换排序 4.快速排序 5.直接选择排序 6.堆排序 7.归并排序
在实际应用中,插入排序和现则排序因为实现简单,使用的比较多,但是在对效率要求比较高、且待排序数据量大的场合,还是应该采用时间复杂度较低的排序算法,因此对排序算法进行试验比较,增强实践认识很有必要。...
内部排序算法主要分为5 大类,有十二个算法。插入排序类、交换排序类、选择排序类、归并排序类和基数排序类。算法主要包括:插入排序、折半插入排序、选择排序、冒泡排序、希尔排序、快速排序、堆排序、归并排序、...
本文件是7种常用排序算法的实现(C++),包括冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序。代码详细有注释且有测试用例。