文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

java排序算法的示例分析

2023-06-20 13:46

关注

这篇文章将为大家详细讲解有关java排序算法的示例分析,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。

一、直接插入排序

基本思想:

将一个记录插入到已排序的有序表中,使插入后的表仍然有序

对初始关键字{49 38 65 97 76 13 27 49}进行直接插入排序

java排序算法的示例分析

package Sort;//插入排序public class InsertSort {    public static void main(String[] args) {        int [] arr={49,38,65,97,76,13,27,49};        sort(arr);       print(arr);    }    private static void sort(int [] arr) {        for (int i = 1; i < arr.length; i++) {           for(int j=i;j>0;j--){               if(arr[j]<arr[j-1]){                  swap(arr,j,j-1);               }           }        }    }    private static void swap(int [] arr,int i,int j){        int temp=0;        temp=arr[i];        arr[i]=arr[j];        arr[j]=temp;    }    private static void print(int [] arr) {        for (int i = 0; i <arr.length ; i++) {            System.out.print(arr[i]+" ");        }    }}

13 27 38 49 49 65 76 97

Process finished with exit code 0

二、 希尔排序

希尔排序又称“缩小增量排序”(Diminishing Increment Sort))属于插入排序类。

基本思想:

先将整个待排序的记录分割成若干子序列分别进行“直接插入排序”,待整个序列中的记录”基本有序“时,再对全体记录进行一次直接插入排序。

java排序算法的示例分析

package Sort;//希尔排序是插入排序的改良public class ShellSort {    public static void main(String[] args) {        int [] arr={16,25,12,30,47,11,23,36,9,18,31};        sort(arr);        print(arr);    }    private static void sort(int [] arr) {        //gap设置优化        int h=1;        while(h<arr.length/3){            h=h*3+1;        }       for(int gap=h;gap>0;gap=(gap-1)/3) {//gap:希尔排序的间距           for (int i = gap; i < arr.length; i++) {               for (int j = i; j >gap-1; j-=gap) {                   if (arr[j] < arr[j - gap]) {                       swap(arr, j, j - gap);                   }               }           }       }    }    private static void swap(int [] arr,int i,int j){        int temp=0;        temp=arr[i];        arr[i]=arr[j];        arr[j]=temp;    }    private static void print(int [] arr) {        for (int i = 0; i <arr.length ; i++) {            System.out.print(arr[i]+" ");        }    }}

9 11 12 16 18 23 25 30 31 36 47

Process finished with exit code 0

三、冒泡排序

冒泡排序

四、快速排序

对冒泡排序的一种改进

基本思想:

通过一趟排序将待排序记录分割成独立的两部分,其中一部分的关键字均比另一部分的关键字小,则可分别对这两部分记录继续分别进行排序,以达到整个序列有序。

java排序算法的示例分析

java排序算法的示例分析

package Sort;import java.util.Arrays;//快速排序public class QuickSort {    public static void main(String[] args) {        int[] arr={49,38,65,97,76,13,27,49};        sort(arr,0,arr.length-1);        System.out.println(Arrays.toString(arr));    }    private static void sort(int [] arr,int start,int end) {       if(start<end){           //把数组的第0个数作为标准数           int stared=arr[start];           //记录要排序的下标           int low=start;           int height=end;           //循环找出比标准数大和比标准数小的数           while(low<height){               //右边数字比标准数大               while(low<height&&stared<=arr[height]){                   height--;               }               //用右边的数字替换左边的数字               arr[low]=arr[height];               //左边数字比标准数小               while(low<height&&stared>=arr[low]){                   low++;               }               //用左边的数字替换右边的数字               arr[height]=arr[low];           }           arr[low]=stared;           sort(arr,start,low);           sort(arr,low+1,height);       }    }    }

[13, 27, 38, 49, 76, 97, 65, 49]

Process finished with exit code 0

五、选择排序(Selection Sort)

选择排序

六、堆排序

  堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

1、大顶堆举例说明:

java排序算法的示例分析

我们对堆中的结点按层进行编号,映射到数组中就是下面这个样子:

java排序算法的示例分析

大顶堆特点:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] // i 对应第几个节点,i从0开始编号

2、小顶堆举例说明

java排序算法的示例分析

小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] // i 对应第几个节点,i从0开始编号

一般升序采用大顶堆,降序采用小顶堆

堆排序基本思想

一、堆排序的基本思想是:

将待排序序列构造成一个大顶堆

此时,整个序列的最大值就是堆顶的根节点。

将其与末尾元素进行交换,此时末尾就为最大值。

然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。

二、代码示例

package Sort;import java.util.Arrays;public class HeapSort {    public static void main(String[] args) {        int [] arr={4,6,8,5,9};        heapSort(arr);    }    //编写一个堆排序的方法    public static void heapSort(int[] arr){        int temp=0;        for(int i=arr.length/2-1;i>=0;i--){            adjustHeap(arr,i,arr.length);        }        //将堆顶元素与末尾元素进行交换,此时末尾就为最大值,将最大值全放在数组最后        //重新调整结构,使其满足堆定义,继续交换堆顶元素与当前末尾元素,反复执行调整交换步骤,使整个序列达到有序        for(int j=arr.length-1;j>0;j--) {            //交换            temp = arr[j];            arr[j] = arr[0];            arr[0] = temp;            adjustHeap(arr, 0, j);        }        System.out.println("数组"+Arrays.toString(arr));    }    //将数组调整为一个大顶堆        public static void adjustHeap(int[]arr,int i,int length){         int temp=arr[i];//先取出当前元素的值,保存在临时变量中        //开始调整        //k=i*2+1;k是i节点的左子节点        for(int k=i*2+1;k<length;k=k*2+1){              if(k+1<length&&arr[k]<arr[k+1]){//说明左子节点的值小于右子节点的值                 k++;//k指向右子节点              }              if(arr[k]>temp){//如果子节点大于父节点                  arr[i]=arr[k];//把较大的值赋给当前节点                  i=k;//!!!i指向k,继续循环比较              }else{                  break;              }        }        //当for循环结束后,已经将以i为父结点的最大值放在了堆顶上(局部)          arr[i]=temp;//将temp的值放在调整后的位置    }}

堆排序结果:

数组[4, 5, 6, 8, 9]

七、归并排序

定义:

又一类不同的排序方法,将两个或两个以上的有序表合并成一个新的有序表。

需要辅助空间:O(n)

整个归并需要 [log2n]

时间复杂度:O(nlog2n)

缺点:归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。

优点:归并排序是一个稳定的排序方法

思路可以推广到“多路归并”

常用于外部排序

java排序算法的示例分析

java排序算法的示例分析

package Sort;//归并排序public class MergeSort {    public static void main(String[] args) {        int [] arr={4,5,7,8,1,2,3,6};        sort(arr);        print(arr);    }    private static void sort(int [] arr) {        int mid=arr.length/2;        int[]temp=new int[arr.length];        int i=0;//标记左边数组        int j=mid+1;//标记右边数组起始点        int k=0;        while(i<=mid&&j<arr.length){            if(arr[i]<=arr[j]){               temp[k]=arr[i];               i++;               k++;            }else{                temp[k]=arr[j];                j++;                k++;            }        }        while(i<=mid){temp[k++]=arr[i++];}//将左边剩余的,复制到数组        while(j<arr.length){temp[k++]=arr[j++];}//将右边剩余的,复制到数组    }    private static void print(int [] arr) {        for (int i = 0; i <arr.length ; i++) {            System.out.print(arr[i]+" ");        }    }}

1 2 3 4 5 6 7 8

Process finished with exit code 0

关于“java排序算法的示例分析”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯