数据结构与算法之比较排序【Java】
2018-06-18 01:15:18来源:未知 阅读 ()
比较排序与非比较排序的对比
比较排序
常见的比较排序主要有以下几种:
- 插入排序:直接插入排序、二分法插入排序、希尔排序。
- 选择排序:简单选择排序、堆排序。
- 交换排序:冒泡排序、快速排序。
- 归并排序
一、插入排序
?思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置,直到全部插入排序完为止。
?关键问题:在前面已经排好序的序列中找到合适的插入位置。
?方法:
–直接插入排序
–二分插入排序
–希尔排序
①直接插入排序(从后向前找到合适位置后插入)
1、基本思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。
2、算法实现
1 package com.allSorts; 2 3 /** 4 * Created by Demrystv. 5 */ 6 public class ChaRu_ZhiJie { 7 public static void main(String[] args) { 8 9 int[] a = {32,63,13,47}; 10 System.out.println("排序前:"); 11 for(int i=0;i<a.length;i++){ 12 System.out.print(a[i]+" "); 13 } 14 15 for(int i=1;i<a.length;i++){ 16 int temp = a[i]; 17 int j; 18 for(j=i-1;j>=0;j--){ 19 if(a[j]>temp){ 20 a[j+1] = a[j]; 21 }else { 22 break; 23 } 24 } 25 a[j+1] = temp; 26 } 27 28 System.out.println(""); 29 System.out.println("排序后:"); 30 for(int i=0;i<a.length;i++){ 31 System.out.print(a[i]+" "); 32 } 33 } 34 }
3、分析
②二分法插入排序(按二分法找到合适位置后插入)
1、基本思想:二分法插入排序的思想和直接插入一样,只是找合适的插入位置的方式不同,这里是按二分法找到合适的位置,可以减少比较的次数。
2、算法实现
1 package com.allSorts; 2 3 /** 4 * Created by Demrystv. 5 */ 6 public class ChaRu_ErFenFa { 7 public static void main(String[] args) { 8 int[] a = {32,86,12,95}; 9 System.out.println("排序前:"); 10 for(int i=0;i<a.length;i++){ 11 System.out.print(a[i]+" "); 12 } 13 14 sort(a); 15 16 System.out.println(""); 17 System.out.println("排序后:"); 18 for(int i=0;i<a.length;i++){ 19 System.out.print(a[i]+" "); 20 } 21 } 22 23 //二分法插入排序 24 private static void sort(int[] array){ 25 for (int i=0;i<array.length;i++){ 26 int temp = array[i]; 27 int left = 0; 28 int right = i-1; 29 int mid = 0; 30 31 while (left<=right) { 32 mid = left + (right - left) / 2; 33 if (array[mid] > temp) { 34 right = mid - 1; 35 } else { 36 left = mid + 1; 37 } 38 } 39 40 for(int j=i-1;j>=left;j--){ 41 array[j+1] = array[j]; 42 } 43 44 if(left!=i){ 45 array[left] = temp; 46 } 47 } 48 } 49 }
3、分析
当然,二分法插入排序也是稳定的。
二分插入排序的比较次数与待排序记录的初始状态无关,仅依赖于记录的个数。当n较大时,比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同,最坏的情况为n2/2,最好的情况为n,平均移动次数为O(n2)。
③希尔排序
1、基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
2、算法实现
二、选择排序
?思想:每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置,直到全部排完。
?关键问题:在剩余的待排序记录序列中找到最小关键码记录。
?方法:
–直接选择排序
–堆排序
①直接选择排序
1、基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
2、算法实现
3、分析
简单选择排序是不稳定的排序。
时间复杂度:T(n)=O(n2)。
②堆排序
1、基本思想:
堆排序是一种树形选择排序,是对直接选择排序的有效改进。
堆的定义:具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
2、算法实现
3、分析
堆排序也是一种不稳定的排序算法。
堆排序优于简单选择排序的原因:
直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。
堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
三、交换排序
①冒泡排序
1、基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
2、算法实现
3、分析
冒泡排序是一种稳定的排序方法。
?若文件初状为正序,则一趟起泡就可完成排序,排序码的比较次数为n-1,且没有记录移动,时间复杂度是O(n)
?若文件初态为逆序,则需要n-1趟起泡,每趟进行n-i次排序码的比较,且每次比较都移动三次,比较和移动次数均达到最大值∶O(n2)
?起泡排序平均时间复杂度为O(n2)
②快速排序
1、基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
2、算法实现
3、分析
快速排序是不稳定的排序。
快速排序的时间复杂度为O(nlogn)。
当n较大时使用快排比较好,当序列基本有序时用快排反而不好。
四、归并排序
1、基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
2、算法实现
3、分析
归并排序是稳定的排序方法。
归并排序的时间复杂度为O(nlogn)。
速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- DES/3DES/AES 三种对称加密算法实现 2020-06-11
- 数据结构:用实例分析ArrayList与LinkedList的读写性能 2020-06-04
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-06-03
- 基础排序算法(附加java实现) 2020-06-02
- 终于有人把最适合学习算法的书单找出来了,面试必备! 2020-05-29
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash