选择排序
思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
①初始状态:无序区为R[1..n],有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
排序实例
初始关键字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序结果 13 27 38 49 49 65 76 97
Java实现代码如下:
package selectsort;
public class Sort {
public static void main(String[] args)
{
int[] a = {8,77,66,99,2,7,4,6,100,34};
int[] b ;
b = selectsort(a);
for(int i = 0; i < b.length; i++)
{
System.out.println(b[i]);
}
}
public static int[] selectsort(int[] p)
{
int temp = 0;
int minindex = 0;
int[] array = p.clone();
for(int i = 0; i < array.length; i++)
{
minindex = i;
for(int j = i+1; j < array.length; j++)
{
if(array[minindex] > array[j] )
minindex = j;
}
temp = array[i];
array[i] = array[minindex];
array[minindex] = temp;
}
return array;
}
}
结果验证正确。
冒泡法
原理
冒泡排序算法的运作如下:
比较相邻的元素。如果第一个比第二个大,就交换他们两个。
对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤,除了最后一个。
持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
算法分析
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。
Java实现代码:
package bubblesort;
public class Bubblesort {
public static void main(String[] args)
{
int[] a = {8,77,66,99,2,7,4,6,100,34};
int[] b;
b = bubble(a);
for(int i =0; i <b.length; i++ )
{
System.out.println(b[i]);
}
}
public static int[] bubble(int[] a)
{
int[] array = a.clone();
for(int i = 0; i < array.length - 1; i++)
{
for(int j = 0; j < array.length - 1 - i; j++)
{
if(array[j] > array[j+1])
sway(array,j,j+1);
}
}
return array;
}
public static void sway(int[] b, int m, int n)
{
int temp = b[m];
b[m] = b[n];
b[n] = temp;
}
}
插入排序
插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
算法描述一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:从第一个元素开始,该元素可以认为已经被排序取出下一个元素,在已经排序的元素序列中从后向前扫描如果该元素(已排序)大于新元素,将该元素移到下一位置重复步骤3,直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。
Java示例代码如下:
package insertsort;
public class Insert {
public static void main(String[] args)
{
int[] a = {500,77,66,99,2,7,4,6,100,34};
int[] b;
b = insert(a);
for(int i =0; i <b.length; i++ )
{
System.out.println(b[i]);
}
}
public static int[] insert(int[] c)
{
int[] array = c.clone();
for(int i = 1; i < array.length; i++)
{
if(array[i] < array[i - 1])
{
int temp = array[i];
int j = i;
while((j>0)&&(array[j - 1] > temp))
{
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
}
return array;
}
}
希尔排序
希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序,但是到了这步,需排序的数据几乎是已排好的了(此时插入排序较快)。
假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n2)的排序(冒泡排序或插入排序),可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据,所以小数据只需进行少数比较和交换即可到正确位置。
一个更好理解的希尔排序实现:将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += step_size而不是i++)。
例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序(此时就是简单的插入排序了)。
package shellsort;
public class shellsort {
public static void main(String[] args)
{
int[] a = {500,77,66,99,2,7,4,6,100,34};
int[] b;
b = shell(a);
for(int i =0; i <b.length; i++ )
{
System.out.println(b[i]);
}
}
public static int[] shell(int[] a)
{
int[] array = a.clone();
int len = array.length;
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
int gap = len;
do
{
gap = gap / 3 + 1;
for(i=gap; i<len; i+=gap)
{
k = i;
temp = array[k];
for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap)
{
array[j+gap] = array[j];
k = j;
}
array[k] = temp;
}
}while( gap > 1 );
return array;
}
}
快速排序
思想:从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴其关键字设为k1,然后将其余关键字小于k1的记录移到前面去,而将关键字大于k1的记录移到后面,结果将待排序序列分成了两个子表最后将关键字为k1的记录查到其分界线的位置处.
算法步骤:假设待划分序列为r[left],r[left+1],.......r[right],具体实现上述划分过程时,可以设两个指针i和j,他们的初值分别为left,right.首先将基准记录r[left]移至变量x中,是r[left],即r[i]相当于空单元,然后反复进行如下两个扫描过程,直到i和j相遇
(1)j从右向左扫描,直到r[j].key<x.key时,将r[j]移至控单元r[i],此时r[j]相当于控单元。
(2)i从左向后扫描,直到r[i].key>x.key时,将r[i]移至空单元r[j],此时r[i]相当于空单元。
当i和j相遇时,r[i](或r[j])相当与空单元,且r[i]左边所有记录的关键字均不大于基准记录的关键字,而r[i]右边所有记录的关键字均不小于基准记录的关键字,最后将基准记录移至r[i]中,就完成了一次划分过程。最后对子表进行递归调用排序函数进行排序。
Java示例代码如下:
package quicksort;
public class Quick {
public static void main(String[] args)
{
int[] a = {500,77,66,99,2,7,4,6,100,34,1000,888,777,666,555,333,222,111,87,45,69,12,45,};
QuickSort(a,a.length);
for(int i =0; i <a.length; i++ )
{
System.out.println(a[i]);
}
}
public static void swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static int partition(int[] array, int low, int high)
{
int pv = array[low];
while( low < high )
{
while( (low < high) && (array[high] >= pv) )
{
high--;
}
swap(array, low, high);
while( (low < high) && (array[low] <= pv) )
{
low++;
}
swap(array, low, high);
}
return low;
}
public static void QSort(int[] array, int low, int high)
{
if( low < high )
{
int pivot = partition(array, low, high);
QSort(array, low, pivot-1);
QSort(array, pivot+1, high);
}
}
public static void QuickSort(int[] array, int len) // O(n*logn)
{
QSort(array, 0, len-1);
}
}
归并排序归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。值得注意的是归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并操作归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。如 设有数列{6,202,100,301,38,8,1}初始状态:6,202,100,301,38,8,1第一次归并后:{6,202},{100,301},{8,38},{1},比较次数:3;第二次归并后:{6,100,202,301},{1,8,38},比较次数:4;第三次归并后:{1,6,8,38,100,202,301},比较次数:4;总的比较次数为:3+4+4=11,;逆序数为14;算法描述归并操作的工作原理如下:第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置第三步:比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置重复步骤3直到某一指针超出序列尾将另一序列剩下的所有元素直接复制到合并序列尾
Java示例代码如下:
package MergeSortClass;
public class MergeSortClass {
private int[] SortOut;
public void printSortedOutput()
{
for (int i = 0; i < this.SortOut.length; i++)
{
System.out.print(this.SortOut[i] + " ");
}
}
public static void main(String[] args)
{
int[] in = { 2, 5, 3, 8, 6, 7, 1, 4, 0, 9 };
MergeSortClass msTest = new MergeSortClass(in);
msTest.printSortedOutput();
}
public MergeSortClass(int[] in)
{
this.SortOut=this.MergeSort(in);
}
private int[] MergeSort(int[] i_list)
{
if (i_list.length == 1) {
return i_list;
} else {
int[] listL = new int[i_list.length / 2];
int[] listR = new int[i_list.length - i_list.length / 2];
int Center = i_list.length / 2;
for (int i = 0; i < Center; i++) {
listL[i] = i_list[i];
}
for (int i = Center, j = 0; i < i_list.length; i++, j++) {
listR[j] = i_list[i];
}
int[] SortedListL=MergeSort(listL);
int[] SortedListR=MergeSort(listR);
int[] o_list = MergeTwoList(SortedListL, SortedListR);
return o_list;
}
}
private int[] MergeTwoList(int[] listL, int[] listR)
{
int i = 0, j = 0;
int[] o_list = new int[listL.length + listR.length];
int foot = 0;
while (i < listL.length && j < listR.length) {
if (listL[i] <= listR[j]) {
o_list[foot] = listL[i];
i++;
} else {
o_list[foot] = listR[j];
j++;
}
foot++;
}
if (i == listL.length) {
while (j < listR.length) {
o_list[foot++] = listR[j++];
}
} else { // j==listR.length
while (i < listL.length) {
o_list[foot++] = listL[i++];
}
}
return o_list;
}
}
分享到:
相关推荐
包括但不仅限于链表、栈,队列,树,堆,图等经典数据结构及其他经典基础算法(如排序等 Java是一种高性能、跨平台的面向对象编程语言。它由Sun Microsystems(现在是Oracle Corporation)的James Gosling等人在1995...
这里提供了冒泡排序,插入排序,递归排序,基数排序,快速排序,选择排序,希尔排序这几种排序算法。里面有大量的注释,可以理解实现思路
关于 null 的几种处理方式大小写敏感 null 是任何引用类型的初始值 null 只是-种特殊的值使用 Null-Safe 方法null 判断 关于思维导图 Java.IO Java.lang Java.math Java.net Java 基础核心总结 V2.0 IO 传统的 ...
线程中断/恢复的几种方式 178 创建线程的两种方式 179 线程的控制 180 实例分析 182 内容总结 189 独立实践 190 第十二章:高级I/O流 192 学习目标 192 I/O基础知识 193 字节流 193 字符流 194 节点流 194 过程流 ...
准备面试Java开发岗位?不要担心!...解释什么是Java的设计模式,并列举几个常用的设计模式及其应用场景。 这些题目涵盖了Java开发中的核心概念和常见问题,帮助您准备面试。祝您面试成功,取得理想的职位!
准备面试Java开发岗位?不要担心!...解释什么是Java的设计模式,并列举几个常用的设计模式及其应用场景。 这些题目涵盖了Java开发中的核心概念和常见问题,帮助您准备面试。祝您面试成功,取得理想的职位!
准备面试Java开发岗位?不要担心!...解释什么是Java的设计模式,并列举几个常用的设计模式及其应用场景。 这些题目涵盖了Java开发中的核心概念和常见问题,帮助您准备面试。祝您面试成功,取得理想的职位!
8.7 几种ejb的结合应用规则 8.8 提高ejb应用性能的其他途径 小结 第9章 jms性能优化 9.1 jms消息收发模式及其各自适用场合 9.2 发送与接收jms消息 9.3 优化jms中的会话对象 9.4 优化连接对象 9.5 优化消息目的地...
讨论 了几种常见的内部排序算法及其时间复杂度: 插入排序、 起泡排序、 选择排序、 快速排 序、 希尔排序、 堆排序, 并且对这几种排序算法进行 了分析比较。着重提供 了希尔排序和堆 排序的实现程序, 以堆排序...
其它对象对它的访问,访问权限所以有以下几种:private, protected, public, friendly。 1.8.2 对象 把类实例化,我们可以生成多个对象,这些对象通过消息传递来进行交互(消息 传递即激活指定的某个对象的方法以改变...
UDP实现的可靠数据传递的小程序。 考虑了丢包的几种可能性及其处理方法。
从简单的单证数据处理、统计汇总与查询到综合信息服务,以及按照“如果…将会…”(what-if)思维模式进行人-机交互的辅助决策等活动,都是对精心设计的数据库的存取操作。数据位于信息系统的中心。 1.3 数据是稳定的...
10.1.2 java异常的处理 341 10.2 程序式异常处理 343 10.2.1 在try-catch语句中处理异常 343 10.2.2 使用requestdispatcher来处理异常 346 10.3 小结 349 第11章 开发线程安全的servlet 350 11.1 多线程的...
表 5-2工作类名及其工作内容 "类名 "服务器端动作 " "HouseRelative "处理用户的进入、离开房间请求" "Login "处理用户的上线、下线请求 " "Messages "处理用户的消息发送请求 " "UserDelAdd "处理用户注册请求 " ...
10.1.2 java异常的处理 341 10.2 程序式异常处理 343 10.2.1 在try-catch语句中处理异常 343 10.2.2 使用requestdispatcher来处理异常 346 10.3 小结 349 第11章 开发线程安全的servlet 350 11.1 多线程的...
Java异常架构主要由以下几个部分组成: Throwable:这是Java中所有错误或异常的超类。它包含了两个子类:Error和Exception。通常,Error用于指示合理的应用程序不应该试图捕获的严重问题,而Exception则用于指示...
10.1.2 java异常的处理 341 10.2 程序式异常处理 343 10.2.1 在try-catch语句中处理异常 343 10.2.2 使用requestdispatcher来处理异常 346 10.3 小结 349 第11章 开发线程安全的servlet 350 11.1 多线程的...
掌握几种说法 数据元素是…,数据项是… 数据结构中关系的四种基本结构 数据结构的形式定义 算法的五个特征 3. 线性表 线性表的概念和四个特征 顺序表和单链表的类型定义 在顺序表中查找、插入、删除,灵活运用 ...