排序方法文档格式.docx
- 文档编号:3106781
- 上传时间:2023-05-01
- 格式:DOCX
- 页数:23
- 大小:63.84KB
排序方法文档格式.docx
《排序方法文档格式.docx》由会员分享,可在线阅读,更多相关《排序方法文档格式.docx(23页珍藏版)》请在冰点文库上搜索。
5.long
temp
a[out];
6.in
out;
7.boolean
flag=in>
0&
&
a[in-1]>
=temp;
8.while(flag){
9.if(a[in-1]>
=temp){
10.if(in>
0){
11.a[in]=a[in-1];
12.count1++;
13.--in;
14.}
15.}
16.count2++;
17.flag=in>
18.}
19.a[in]
temp;
20.}
21.System.out.println("
复制次数为:
"
+
比较次数为:
count2);
22.}
插入排序法在数据已有一定顺序的情况下,效率较好。
但如果数据无规则,则需要移动大量的数据,其效率就与冒泡排序法和选择排序法一样差了。
∙Java排序算法总结
(二):
选择排序
∙
2011-04-2013:
56
XX
我要评论(0)
选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。
算法不稳定,O
(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的。
在大多数情况下都不推荐使用。
只有在希望减少交换次数的情况下可以用。
基本思想
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(1≤i≤n-1)。
该趟排序从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
class
Test
{
2.public
static
int[]
a
10,
32,
1,
9,
5,
7,
12,
4,
3
};
预设数据数组
3.public
main(String
args[])
4.int
i;
循环计数变量
5.int
Index
a.length;
数据索引变量
6.System.out.print("
排序前:
);
7.for
(i
i
lt;
-
i++)
8.System.out.printf("
%3s"
a);
9.System.out.println("
10.SelectSort(Index
1);
选择排序
11.//
排序后结果
12.System.out.print("
排序后:
13.for
14.System.out.printf("
15.System.out.println("
16.}
17.public
SelectSort(int
Index)
18.int
i,
j,
k;
19.int
MinValue;
最小值变量
20.int
IndexMin;
最小值索引变量
21.int
Temp;
暂存变量
22.for
23.MinValue
32767;
目前最小数值
24.IndexMin
储存最小数值的索引值
25.for
(j
j
Index;
j++)
26.if
(a[j]
MinValue)
找到最小值
27.{
28.MinValue
a[j];
储存最小值
29.IndexMin
j;
30.}
31.Temp
a;
交换两数值
32.a
33.a
34.}
35.System.out.print("
排序中:
36.for
(k
k
k++)
37.System.out.printf("
a[k]);
38.System.out.println("
39.}
40.}
41.}
选择排序法与冒泡排序法一样,最外层循环仍然要执行n-1次,其效率仍然较差。
∙Java排序算法总结(三):
冒泡排序
2011-04-2014:
07
冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面。
下面让我们一起来看冒泡排序在Java中的算法实现。
冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:
1.“编程复杂度”很低,很容易写出代码;
2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列,而堆排序、快速排序均不具有稳定性。
不过,一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快,且具有稳定性,但速度不及堆排序、快速排序。
冒泡排序是经过n-1趟子排序完成的,第i趟子排序从第1个数至第n-i个数,若第i个数比后一个数大(则升序,小则降序)则交换两数。
冒泡排序算法稳定,O
(1)的额外的空间,比较和交换的时间复杂度都是O(n^2),自适应,对于已基本排序的算法,时间复杂度为O(n)。
冒泡算法的许多性质和插入算法相似,但对于系统开销高一点点。
排序过程
设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"
漂浮"
,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。
代码实现:
1.//
冒泡排序
BubbleSort
sort(Comparable[]
data)
4.//
数组长度
len
data.length;
6.for
(int
7.//
临时变量
8.Comparable
null;
9.//
交换标志,false表示未交换
10.boolean
isExchanged
false;
11.for
>
j--)
12.//
如果data[j]小于data[j
1],交换
13.if
(data[j].compareTo(data[j
1])
0)
14.temp
data[j];
15.data[j]
data[j
1];
16.data[j
1]
17.//
发生了交换,故将交换标志置为真
18.isExchanged
true;
19.}//
end
if
20.}//
for
21.//
本趟排序未发生交换,提前终止算法,提高效率
22.if
(!
isExchanged)
23.return;
24.}//
25.}//
26.}//
sort
27.public
main(String[]
args)
28.//
在JDK1.5版本以上,基本数据类型可以自动装箱
29.//
int,double等基本类型的包装类已实现了Comparable接口
30.Comparable[]
c
23,
45,
27,
2
31.sort(c);
32.for
(Comparable
data
:
c)
33.System.out.println(data);
35.}
36.}
使用冒泡排序法对n个数据进行排序,共需要进行n-1次的比较。
如果本来就是有顺序的数据,也需要进行n-1次比较。
冒泡排序法的算法很简单,效率也较差。
∙Java排序算法总结(四):
希尔排序
19
希尔排序(ShellSort)是插入排序的一种。
是针对直接插入排序算法的改进。
该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。
本文主要介绍希尔排序用Java是怎样实现的。
希尔排序(缩小增量法)属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序。
希尔排序并不稳定,O
(1)的额外空间,时间复杂度为O(N*(logN)^2)。
最坏的情况下的执行效率和在平均情况下的执行效率相比相差不多。
基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。
所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序;
然后,取第二个增量d2<
d1重复上述的分组和排序,直至所取的增量dt=1(dt<
dt-l<
…<
d2<
d1),即所有记录放在同一组中进行直接插入排序为止。
%3s
10.ShellSort(Index
ShellSort(int
20.boolean
Change;
数据是否改变
DataLength;
分割集合的间隔长度
22.int
Pointer;
进行处理的位置
23.DataLength
(int)
/
2;
初始集合间隔长度
24.while
(DataLength
!
数列仍可进行分割
25.{
26.//
对各个集合进行处理
27.for
28.Change
29.Temp
暂存Data[j]的值,待交换值时用
30.Pointer
计算进行处理的位置
31.//
进行集合内数值的比较与交换值
32.while
(Temp
a[Pointer]
Pointer
0
33.a[Pointer
DataLength]
a[Pointer];
34.//
计算下一个欲进行处理的位置
35.PointerPointer
36.Change
37.if
(Pointer
||
38.break;
40.//
与最后的数值交换
41.a[Pointer
42.if
(Change)
43.//
打印目前排序结果
44.System.out.print("
45.for
46.System.out.printf("
47.System.out.println("
48.}
49.}
50.DataLengthDataLength
DataLength
计算下次分割的间隔长度
51.}
52.}
53.}
希尔排序几乎没有最坏情况,无论是正序、逆序、乱序,所用时间都不是很多,附加储存是O
(1),的确非常不错。
在没搞清楚快速排序、堆排序之前,它的确是个很好的选择。
希望能给你带来帮助。
∙Java排序算法总结(五):
归并排序
29
手中无剑心中无尘
XX空间
归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。
和快速排序类似,让我们一起来看,归并在Java中的实现。
归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。
然后再把有序子序列合并为整体有序序列。
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法(DivideandConquer)的一个非常典型的应用。
将已有序的子序列合并,得到完全有序的序列;
即先使每个子序列有序,再使子序列段间有序。
若将两个有序表合并成一个有序表,称为2-路归并。
归并排序算法稳定,数组需要O(n)的额外空间,链表需要O(log(n))的额外空间,时间复杂度为O(nlog(n)),算法不是自适应的,不需要对数据的随机读取。
工作原理:
1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
2、设定两个指针,最初位置分别为两个已经排序序列的起始位置
3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
4、重复步骤3直到某一指针达到序列尾
5、将另一序列剩下的所有元素直接复制到合并序列尾
mergeSort(){
2.long[]
workSpace
new
long[nElems];
3.recMergeSort(workSpace,0,nElems-1);
4.}
5.private
recMergeSort(long[]
workSpace,
int
lowerBound,
upperBound){
6.if(lowerBound
==
7.return;
8.}
9.else{
10.int
mid=(lowerBound+upperBound)/2;
11.recMergeSort(workSpace,
mid);
12.recMergeSort(workSpace,
mid+1,
upperBound);
13.merge(workSpace,
14.}
15.}
16.private
merge(long[]
lowPtr,
highPtr,
17.int
lowerBound
lowPtr;
mid
highPtr
n
upperBound-lowerBound+1;
21.while(lowPtr<
=mid&
highPtr<
=upperBound){
22.if(theArray[lowPtr]<
theArray[highPtr]){
23.workSpace[j++]=theArray[lowPtr++];
24.}
25.else{
26.workSpace[j++]=theArray[highPtr++];
27.}
28.}
29.while(lowPtr<
=mid){
30.workSpace[j++]
theArray[lowPtr++];
31.}
32.while(highPtr<
33.workSpace[j++]
theArray[highPtr++];
35.for(j=0;
j<
n;
j++){
36.theArray[lowerBound+j]=workSpace[j];
37.}
38.}
归并排序是比较稳定的排序.即相等的元素的顺序不会改变.如输入记录1
(1)3
(2)2(3)2(4)5(5)(括号中是记录的关键字)时输出的1
(1)2(3)2(4)3
(2)5(5)中的2和2是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.
∙Java排序算法总结(六):
堆排序
2011-04-2015:
06
1991年计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·
弗洛伊德(RobertW.Floyd)和威廉姆斯(J.Williams)在1964年共同发明了著名的堆排序算法(HeapSort)。
本文主要介绍堆排序用Java来实现。
堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。
堆排序是不稳定的排序方法,辅助空间为O
(1),最坏时间复杂度为O(nlog2n)
,堆排序的堆序的平均性能较接近于最坏性能。
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
①先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。
然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 排序 方法