logo资料库

程序员必知的8大排序(值得一看).doc

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.97M 资料格式：doc 举报 版权申诉
第1页 / 共14页
第2页 / 共14页
第3页 / 共14页
第4页 / 共14页
第5页 / 共14页
第6页 / 共14页
第7页 / 共14页
第8页 / 共14页
资料共14页，剩余部分请下载后查看
    程序员必知的 8 大排序（java 实现） 前几天，看到一篇前辈的博文“程序员必知的 8 大排序”，不禁的手痒起来，重新翻开严蔚 敏老师的《数据结构》复习了一遍，然后一一的用 java 去实现，其中有不足之处，还望各 位道友指正出来。 先来看看 8 种排序之间的关系： 1， 直接插入排序 （1）基本思想：在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排 好顺序的，现在要把第 n 个数插到前面的有序数中，使得这 n 个数 也是排好顺序的。如此反复循环，直到全部排好顺序。 （2）实例
    （3）用 java 实现 package com.njue; public class insertSort { public insertSort(){ int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23, 34,15,35,25,53,51}; int temp=0; for(int i=1;i=0&&temp
    （3）用 java 实现 public class shellSort { public shellSort(){ int a[]={1,54,6,3,78,34,12,45,56,100}; double d1=a.length; int temp=0; while(true){ d1= Math.ceil(d1/2); int d=(int) d1; for(int x=0;x=0&&temp
    3.简单选择排序 （1）基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交 换； 然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个 数和最后一个数比较为止。 （2）实例： （3）用 java 实现 public class selectSort { public selectSort(){ int a[]={1,54,6,3,78,34,12,45}; int position=0; for(int i=0;i
    4， 堆排序 （1）基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。 堆的定义如下：具有 n 个元素的序列（h1,h2,...,hn),当且仅当满足 （hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。 在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元 素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结构。堆顶为根， 其它为左子树、右子树。初始时把要排序的数的序列看作是一棵顺序存储的二叉 树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根 节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依 此类推，直到只有两个节点的堆，并对它们作交换，最后得到有 n 个节点的有序 序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最 后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是 反复调用渗透函数实现排序的函数。 （2）实例： 初始序列：46,79,56,38,40,84 建堆： 交换，从堆中踢出最大数
    剩余结点再建堆，再交换踢出最大数 依次类推：最后堆中剩余的最后两个结点交换，踢出一个，排序完成。 （3）用 java 实现 import java.util.Arrays; public class HeapSort { int public HeapSort(){ heapSort(a); a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23, 34,15,35,25,53,51}; } public void heapSort(int[] a){ System.out.println("开始排序"); int arrayLength=a.length; //循环建堆 for(int i=0;i
    buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } private void swap(int[] data, int i, int j) { // TODO Auto-generated method stub int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } //对data数组从0到lastIndex建大顶堆 private void buildMaxHeap(int[] data, int lastIndex) { // TODO Auto-generated method stub //从lastIndex处节点（最后一个节点）的父节点开始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在 while(k*2+1<=lastIndex){ //k节点的左子节点的索引 int biggerIndex=2*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的 右子节点存在 if(biggerIndex
    } } } 5.冒泡排序 （1）基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数， 自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上 冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互 换。 （2）实例： （3）用 java 实现 public class bubbleSort { public bubbleSort(){ int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23, 34,15,35,25,53,51}; int temp=0; for(int i=0;ia[j+1]){ temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } for(int i=0;i
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料