今天重新学习了一下简单排序:冒泡排序、选择排序、插入排序
1.冒泡排序
核心代码:
//a代表数组a,nElems代表数组长度
public void bubbleSort(){
int out,in;
for(out=nElems-1;out>1;out--){
for(in=0;in<out;in++){//先将最大的数据放在最后
if(a[in]>a[int+1])//比较
swap(in,in+1);//交换数据
}
}
}
思路:将最大的数据放在最后!从后面开始排序
效率:假设数据中有N个数据项,则共做了N*(N-1)/2次比较,交换次数平均大约为N²/4次, 此算法的运行时间为O(N²)
不变性:out右边的所有数据项均为有序
特点:运行比较慢,是排序算法中最简单的
2.选择排序
核心代码:
//a代表数组a,nElems代表数组长度
public void selectionSort(){
int out,in,min;
for(out=0;out<nElems-1;out++){
min = out;//从开始把初值附给min
//从第out的下一个数开始和min比较,直到找到最小的值
for(in=out+1;in<nElems;in++){
if(a[in]<a[min])//如果比a[min]小,则把最小值的下标附给min
min = in;
}
swap(out,min);//交换数据
}
}
思路:将最小的数据放在最前面,从前面开始排序
效率:假设数据中有N个数据项,则共做了N*(N-1)/2次比较,但交换比冒泡排序少的多O(N)!算法的运行时间为O(N²)
不变性:下标小于或等于out的数据项总是有序的
特点:运行比冒泡快一点
3.插入排序
核心代码:
//a代表数组a,nElems代表数组长度
public void insertionSort(){
int out,in;
for(out=1;out<nElems;out++){
long temp = a[out];//声明一个被标记的变量
in = out;//从out开始
while(in>0&&a[in-1]>=temp){
a[in] = a[in-1]//a[in]如果比a[in-1]小,则进行附值,直接替换
--in; //in自减1,意思是向左移一位
}
a[in] = temp;//in已经找到位置,左边的都是比a[in]小的
}
}
思路:选择一个标记,在这个标记的左边已经是局部有序的了,然而左边数据的最终位置还没有确定!
效率:假设数据中有N个数据项,则共做了N*(N-1)/4次比较,但交换比冒泡排序少的多O(N)!算法的运行时间为O(N²)
对于有序或者基本有序的数据来说,插入排序要好的多,只需要O(N)的时间。
不变性:在每次结束时,在将temp位置的项插入后,比outer变量下标小的数据项总是局部有序的
特点:相对于随机数据,运行比冒泡快一倍,比选择排序要快一点
- 描述: 冒泡排序图
- 大小: 66 KB
- 描述: 选择排序图
- 大小: 87 KB
- 描述: 插入排序图
- 大小: 71.9 KB
分享到:
相关推荐
这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小...
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
八大排序方法详细图形解释,和算法复杂度分析,及最后总结。 1.直接插入排序 2.希尔排序 3.简单选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 8.基数排序
最经典的8大排序算法总结,插入排、冒泡排序、快速排序、简单选择排序、归并排序、二叉树排序、基数排序等。
西安交大兵马俑BBS神作 关于海量排序独到总结 简单易懂 完整
经典排序总结(附代码),包含开发过程中遇到的各种常见的排序算法,比较简单,比较适合初学者理解。
常用排序算法总结 各种内排序方法的选择 对元素个数较多的排序,可以选快速排序、堆排序、归并排序,元素个数较少时,可以选简单的排序方法。
数据结构实验报告学习、实现、对比各种排序算法,掌握各种排序算法的优劣,以及各种算法使用的情况。 实验内容: 使用链表实现下面各种排序算法,并进行比较。 排序算法: ...4、简单选择排序 5、其他
对开发时排序算法的总结,有简单排序,冒泡排序,二分法排序,且有对各种排序的优劣势的分析,谨供大家参考
排序算法总结常见排序算法如下:直接插入排序希尔排序简单选择排序堆排序冒泡排序快速排序归并排序技术排序它们都属于内部排序,也就是只考虑数据量较小仅需要使用内部的排
数据结构中九大排序算法:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,归并排序,基数排序,就时间复杂度,空间复杂度,稳定性,基本原理的简要总结与比较
左子树的数据总是小于根和右子树的数据,这种就叫做二叉排序树,简单一点,二叉排序树左边的数据小于右边. 1)编程实现二叉排序树, 包括生成、插入,删除; 2)对二叉排序树进行先根、中根、 和后根非递归遍历; ...
对冒泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序这六种常用的内排序方法的掌握,通过对各种排序算法的分析,对其关键字的比较次数和移动次数进行分析,运用数据结构所学的知识将其用程序实现。
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
总结了一下比较常见的几种排序方法,用c程序实现,包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,简单选择排序,堆排序,树型排序,归并排序,分配排序,这些算法的实现都有,很全的
个人原创总结的常用排序算法C语言示例代码解说PDF...包含有直接插入排序,折半插入排序,2路直接插入排序,起泡排序,简单选择排序,快速排序,堆排序,(希尔排序,归并排序,基数排序为空白),供学习排序算法的爱好者参考。
几乎把网上的排序算法小结找遍了,简单地小结一下算法的思路(不含代码,只是用易懂的话说清楚算法是怎么做的),算法时间复杂度和空间复杂的求法(用理解的方式而不是分析代码),各种排序算法的优缺点,稳定与否...
本文首先举例阐述了两种排序方法的操作步骤,然后列出了用python进行的实现过程,最后对桶式排序方法的优劣进行了简单总结。 一、桶排序: 排序一个数组[5,3,6,1,2,7,5,10] 值都在1-10之间,建立10个桶: [0 0 0 0 0...
该 ppt 为课程讲义,讲解冒泡排序算法原理,及用一个简单实例进行具体分析,还有冒泡排序算法原理的总结等。
总结简单PLSQL查询语句,包括删除,in,逻辑语句,排序等