来源:
http://blog.csdn.net/fenglibing/article/details/1756473
算法复杂度
http://blog.sina.com.cn/s/blog_771849d301010ta0.html
快速排序:
http://wangyu.iteye.com/blog/198474
1、冒泡排序 Bubble Sort
最简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序。这个算法可实现如下。
算法如下:
/**
*冒泡排序
*@paramsrc待排序数组
*/
void doBubbleSort(int[] src)
{
int len=src.length;
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
int temp;
if(src[i]>src[j])
{
temp=src[j];
src[j]=src[i];
src[i]=temp;
}
}
printResult(i,src);
}
}
2、选择排序 Selection Sort
选择排序的基本思想是:对待排序的记录序列进行n-1遍的处理,第1遍处理是将L[1..n]中最小者与L[1]交换位置,第2遍处理是将L[2..n]中最小者与L[2]交换位置,......,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置就已经按从小到大的顺序排列好了。
当然,实际操作时,也可以根据需要,通过从待排序的记录中选择最大者与其首记录交换位置,按从大到小的顺序进行排序处理。
算法如下:
/**
*选择排序
*@paramsrc待排序的数组
*/
void doChooseSort(int[] src)
{
int len=src.length;
int temp;
for(int i=0;i<len;i++)
{
temp=src[i];
int j;
int samllestLocation=i;//最小数的下标
for(j=i+1;j<len;j++)
{
if(src[j]<temp)
{
temp=src[j];//取出最小值
samllestLocation=j;//取出最小值所在下标
}
}
src[samllestLocation]=src[i];
src[i]=temp;
printResult(i,src);
}
}
3、插入排序 Insertion Sort
插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i]騆[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。
简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种,这里只介绍直接插入排序,折半插入排序留到“查找”内容中进行。
图1演示了对4个元素进行直接插入排序的过程,共需要(a),(b),(c)三次插入。
图1 对4个元素进行插入排序
在下面的插入排序算法中,为了写程序方便我们可以引入一个哨兵元素L[0],它小于L[1..n]中任一记录。所以,我们设元素的类型ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定L[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将L[i]放入L[0]中,这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。
算法如下:
/**
*插入排序(WHILE循环实现)
*@paramsrc待排序数组
*/
void doInsertSort1(int[] src)
{
int len=src.length;
for(int i=1;i<len;i++)
{
int temp=src[i];
int j=i;
while(src[j-1]>temp)
{
src[j]=src[j-1];
j--;
if(j<=0)
break;
}
src[j]=temp;
printResult(i+1,src);
}
}
/**
*插入排序(FOR循环实现)
*@paramsrc待排序数组
*/
void doInsertSort2(int[] src)
{
int len=src.length;
for(int i=1;i<len;i++)
{
int j;
int temp=src[i];
for(j=i;j>0;j--)
{
if(src[j-1]>temp)
{
src[j]=src[j-1];
}else//如果当前的数,不小前面的数,那就说明不小于前面所有的数,
//因为前面已经是排好了序的,所以直接通出当前一轮的比较
break;
}
src[j]=temp;
printResult(i,src);
}
}
快速排序:
public class QuickSort {
public static void main(String[] args) {
Random random=new Random();
int[] pData=new int[10];
for(int i=0;i<pData.length;i++){ //随机生成10个排序数
Integer a =random.nextInt(100);
pData[i]= a;
System.out.print(pData[i]+" ");
}
System.out.println();
int left=0;
int right=pData.length-1;
Sort(pData,left,right);
for(int i=0;i<pData.length;i++){
System.out.print(pData[i]+" ");
}
System.out.println();
}
public static int[] Sort(int[] pData, int left, int right){
int middle,strTemp;
int i = left;
int j = right;
middle = pData[(left+right)/2];
do{
while((pData[i]<middle) && (i<right))
i++;
while((pData[j]>middle) && (j>left))
j--;
if(i<=j){
strTemp = pData[i];
pData[i] = pData[j];
pData[j] = strTemp;
i++;
j--;
}
for(int k=0;k<pData.length;k++){
System.out.print(pData[k]+" ");
}
System.out.println();
}while(i<j);//如果两边扫描的下标交错,完成一次排序
if(left<j)
Sort(pData,left,j); //递归调用
if(right>i)
Sort(pData,i,right); //递归调用
return pData;
}
}
http://blog.csdn.net/fenglibing/article/details/1756473
算法复杂度
http://blog.sina.com.cn/s/blog_771849d301010ta0.html
快速排序:
http://wangyu.iteye.com/blog/198474
1、冒泡排序 Bubble Sort
最简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序。这个算法可实现如下。
算法如下:
/**
*冒泡排序
*@paramsrc待排序数组
*/
void doBubbleSort(int[] src)
{
int len=src.length;
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
int temp;
if(src[i]>src[j])
{
temp=src[j];
src[j]=src[i];
src[i]=temp;
}
}
printResult(i,src);
}
}
2、选择排序 Selection Sort
选择排序的基本思想是:对待排序的记录序列进行n-1遍的处理,第1遍处理是将L[1..n]中最小者与L[1]交换位置,第2遍处理是将L[2..n]中最小者与L[2]交换位置,......,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置就已经按从小到大的顺序排列好了。
当然,实际操作时,也可以根据需要,通过从待排序的记录中选择最大者与其首记录交换位置,按从大到小的顺序进行排序处理。
算法如下:
/**
*选择排序
*@paramsrc待排序的数组
*/
void doChooseSort(int[] src)
{
int len=src.length;
int temp;
for(int i=0;i<len;i++)
{
temp=src[i];
int j;
int samllestLocation=i;//最小数的下标
for(j=i+1;j<len;j++)
{
if(src[j]<temp)
{
temp=src[j];//取出最小值
samllestLocation=j;//取出最小值所在下标
}
}
src[samllestLocation]=src[i];
src[i]=temp;
printResult(i,src);
}
}
3、插入排序 Insertion Sort
插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i]騆[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。
简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种,这里只介绍直接插入排序,折半插入排序留到“查找”内容中进行。
图1演示了对4个元素进行直接插入排序的过程,共需要(a),(b),(c)三次插入。
图1 对4个元素进行插入排序
在下面的插入排序算法中,为了写程序方便我们可以引入一个哨兵元素L[0],它小于L[1..n]中任一记录。所以,我们设元素的类型ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定L[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将L[i]放入L[0]中,这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。
算法如下:
/**
*插入排序(WHILE循环实现)
*@paramsrc待排序数组
*/
void doInsertSort1(int[] src)
{
int len=src.length;
for(int i=1;i<len;i++)
{
int temp=src[i];
int j=i;
while(src[j-1]>temp)
{
src[j]=src[j-1];
j--;
if(j<=0)
break;
}
src[j]=temp;
printResult(i+1,src);
}
}
/**
*插入排序(FOR循环实现)
*@paramsrc待排序数组
*/
void doInsertSort2(int[] src)
{
int len=src.length;
for(int i=1;i<len;i++)
{
int j;
int temp=src[i];
for(j=i;j>0;j--)
{
if(src[j-1]>temp)
{
src[j]=src[j-1];
}else//如果当前的数,不小前面的数,那就说明不小于前面所有的数,
//因为前面已经是排好了序的,所以直接通出当前一轮的比较
break;
}
src[j]=temp;
printResult(i,src);
}
}
快速排序:
public class QuickSort {
public static void main(String[] args) {
Random random=new Random();
int[] pData=new int[10];
for(int i=0;i<pData.length;i++){ //随机生成10个排序数
Integer a =random.nextInt(100);
pData[i]= a;
System.out.print(pData[i]+" ");
}
System.out.println();
int left=0;
int right=pData.length-1;
Sort(pData,left,right);
for(int i=0;i<pData.length;i++){
System.out.print(pData[i]+" ");
}
System.out.println();
}
public static int[] Sort(int[] pData, int left, int right){
int middle,strTemp;
int i = left;
int j = right;
middle = pData[(left+right)/2];
do{
while((pData[i]<middle) && (i<right))
i++;
while((pData[j]>middle) && (j>left))
j--;
if(i<=j){
strTemp = pData[i];
pData[i] = pData[j];
pData[j] = strTemp;
i++;
j--;
}
for(int k=0;k<pData.length;k++){
System.out.print(pData[k]+" ");
}
System.out.println();
}while(i<j);//如果两边扫描的下标交错,完成一次排序
if(left<j)
Sort(pData,left,j); //递归调用
if(right>i)
Sort(pData,i,right); //递归调用
return pData;
}
}
发表评论
-
jvm default value
2015-07-17 21:32 526http://www.cnblogs.com/redcreen ... -
加密解密
2013-10-10 14:55 438Java安全之对称加密、非对称加密、数字签名 http ... -
xml 文档 xsd与dtd ,webservices
2013-08-15 19:31 463http://www.ibm.com/developerw ... -
tomcat
2013-08-14 19:11 461tomcat工作原理 http://www.cnblog ... -
类加载器
2013-08-14 19:02 529类加载器:http://blog.csdn.ne ... -
Java中堆内存和栈内存详解
2013-05-15 18:15 540http://www.cnblogs.com/whgw/a ... -
jvm 类编译 加载 监控工具
2013-05-06 22:42 516http://simpleframework.net/bl ... -
print gc parameter
2013-05-01 21:43 466http://lanmaohome.blog.sohu.com ... -
JDK7 AIO (非阻塞IO)实现大并发TCPServer和TCPClient
2013-04-10 17:56 1008http://blog.sina.com.cn/s/blo ... -
CopyOnWriteArrayList LinkedBlockingQueue BlockingQueue
2013-04-09 16:54 634http://blog.163.com/among_198 ... -
java 死锁解决方式
2013-04-08 21:16 663解决方式: 1)尽量使用tryLock(long time ... -
虚拟机调优
2013-04-08 11:58 0通过对JVM的参数设置,达到控制gc回收的频率以 ... -
cglib
2013-03-31 18:45 552文章come from : http://www.uml. ... -
linux 存储过程
2013-03-27 14:06 745出处:http://blog.csdn.net/qinde0 ... -
比较好的 JMS讲解,java
2013-05-12 22:40 436http://blog.csdn.net/zhangxs_ ... -
java 集合类
2013-03-25 14:31 578出处:http://blog.csdn.net/touchS ... -
java 集合类
2013-03-25 13:57 521出处:http://developer.51cto.c ... -
Java NIO
2013-03-21 13:36 660原文出自【比特网】,转载请保留原文链接:http://sof ... -
HashMap原理及冲突之简谈
2013-03-19 16:09 653文章出处: http://space.itpub.net/ ... -
HashMap 结构
2013-03-19 15:24 627文章出处: http://java.chinaitlab. ...
相关推荐
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法,排序算法数据结构
最快的排序算法 最快的内部排序法—桶排序法 (1),排序算法数据结构
合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为O(nlogn)。在本次实验中将数据量提到5万的时候,该类算法运行时间仍在几毫秒左右,而上面的3种算法运行时间已经到达十几秒左右,效率...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
之前说过轴的选择是快速排序法的效率关键之一,在这边的快速排序法的轴选择方式更加快了快速排序法的效率,它是来自演算法名书 Introduction to Algorithms 之中。
常用排序算法的动态演示系统的开发,演示冒泡排序法、快速排序法、直接插入排序法、折半插入排序法、树形选择排序法
常见经典排序算法(C语言)1希尔排序 二分插入法 直接插入法 带哨兵的直接排序法 冒泡排序 选择排序 快速排序 堆排序.docx
总结了各种排序算法,并用C++代码实现,并有演示
桶式排序法桶式排序法桶式排序法桶式排序法
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
在STM8S003单片机上实现数组排序,用3种冒泡排序法对数组进行排序,并通过串口打印排序过程。
1、常见排序算法实现(1-6选择几个算法练习) 1)问题描述:输入一组关键字序列分别实现下列排序。 (1)实现简单选择排序、直接插入排序和冒泡排序。 (2)实现希尔排序算法。 (3)实现折半插入排序。 ...
使用简单数组实现下面各种排序算法的功能,并进行比较, 排序算法如下: a) 插入排序; b) 希尔排序; c) 冒泡排序; d) 快速排序; e) 简单选择排序; f) 堆排序; g) 归并排序; h) 基数排序(选作); i) 其他; ...
在之前所介绍过的排序方法,都是属于「比较性」的排序法,也就是每次排序时 ,都是比较整个键值的大小以进行排序。 这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数...