美文网首页
java实现五大排序算法

java实现五大排序算法

作者: clshinem | 来源:发表于2017-10-19 20:06 被阅读0次

1:冒泡排序BubbleSort

我觉得这个没啥好说的,代码如下

package algorithm;

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {5,3,8,6,4};
        BubbleSort.sort(arr);
        for(int a:arr) {
            System.out.print(a+" ");
        }
    }
    public static void sort(int[] arr) {
        for (int i =0;i<arr.length;i++) {
            for (int j = arr.length-1;j>i;j--) {
                if (arr[j]<arr[j-1]) {
                    swap(arr,j,j-1);
                }
            }
        }
    }
    public static void swap(int[] arr,int i ,int j) {
        int temp = arr[i];
        arr[i]= arr[j];
        arr[j] = temp;
    }
}

2:插入排序

这个有一点点说的,之前写python插入排序的时候可能没注意到这个地方;第二个循环在循环的时候:如果前面的数比这个数大,就把它往后放,直到找到第一个比他小的数(这时候也就找到了这个位置)代码是while(j>0&&target<arr(j-1))
剩下的附上代码

public class InsertSort {
    public static void main(String[]args) {
        int[] arr= {5,3,9,6,4,0};
        InsertSort.sort(arr);
        for(int a:arr) {
            System.out.println(a+" ");
        }
    }
    public static void sort(int[] arr) {
        for (int i =1;i<arr.length;i++) {
            int j =i;
            int target = arr[i];
            
            while(j>0&&target<arr[j-1]) {
                arr[j] = arr[j-1];
                j--;
            }
            arr[j] = target;
        }
    }
    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

3:选择排序,我觉得还是没啥好说的

package algorithm;
//插入排序的思想就是找到最小或者最大的值,依次从前往后放在该在的位置上;要注意的地方是,找最小(大)值时,要比较的是arr[target]而不是arr[i]
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {5,3,8,6,4};
        SelectSort.sort(arr);
        for(int a:arr) {
            System.out.println(a);
        }
    }
    public static void sort(int[] arr) {
        for (int i = 0;i<arr.length;i++) {
            int target = i;
            for (int j=i;j<arr.length;j++) {
                if (arr[j] <arr[target]) {
                    target = j;
                }
            }
            swap(arr,i,target);

        }
    }
    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

4:快速排序,大概要注意的点在python实现的时候我都写过了,代码如下

package algorithm;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5,3,8,6,4,7};
        QuickSort.sort(arr, 0, 5);
        for(int a:arr) {
            System.out.println(a+" ");
        }
            
    }
    public static int partition(int[] arr,int i,int j) {
        int TargetIndex = i;
        int TargetNum = arr[i];
        while(i<j) {
            while(i<j && arr[j] >= TargetNum) {
                j--;
            }
            while(i<j && arr[i] <= TargetNum) {
                i++;
            }
            swap(arr,i,j);
        }
        swap(arr,i,TargetIndex);
        return i;
    }
    public static void sort(int[] arr,int i,int j) {
        if (i >=j) {
            return ;
        }
        int target = partition(arr,i,j);
        sort(arr, i, target-1);
        sort(arr,target+1,j);
    }
    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

5:归并排序

这个大概是我今天遇见最大的坑
之前使用python的切片,直接返回了两个子数组,所以打算java也这么做
然后查了arrays的api发现有个方法是 从copyOfRange(int[] arr,int start,int end)
但是要获取到每次传入这个数组的第一个位置,(也就是传入数组在原数组的位置)可能有机会实现,但是我感觉太复杂了,而且不允许空开这个参数,所以换了用下标的这个做法
然后第二个坑就是,merge并不返回一个新数组,而是把原来的数组排序,也就是说两个方法的返回值都是void,通过改变引用类型参数来达到数组排序的目的
第三个坑:这个很智障的问题,出现在原地归并的实现中
归并是通过两两有序的方式来实现的,所以最后合并的两个数组是分别有序的。
剩下的要注意的点就是看代码拉

package algorithm;


public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {5,3,8,6,4};
        MergeSort.sort(arr, 0, 4);
        for(int a:arr) {
            System.out.println(a);
        }
    }
    public static void sort(int[] arr,int i,int j) {
        if (i >=j) {
            return;
        }
        int mid = (i + j)/2;
        sort(arr,i,mid);
        sort(arr,mid+1,j);
        merge(arr,i,mid,j);
        
    }
    public static void merge(int[] arr ,int i ,int mid,int j) {
        int [] temp = new int[j-i+1];
        int left = i;
        int right = mid+1;
        int k = 0;
        while(left <mid+1 && right <=j) {
            if(arr[left]<arr[right]) {
                temp[k++] = arr[left++];
            }else {
                temp[k++] = arr[right++];
            }
        }
        while(left<mid+1) {
            temp[k++] = arr[left++];
        }
        while (right<=j) {
            temp[k++] = arr[right++];
        }
        for(int p = 0;p<temp.length;p++) {
            arr[i+p] = temp[p];
        }
    }
}

原地归并还没实现,先把对原地归并的再次理解放上来(给你活动下颈椎,不用谢我)

7d13f93f5fa8177d8e303a6a80c96102.JPEG

大致今天的上班摸鱼就摸了这些,最近发现自己效率好低,写了五个算法,写了一天,还是建立在就把python改一下java的前提下,看东西也效率比较低。努力改正。


image.png

相关文章

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • java 实现排序算法之「插入排序」

    java 实现排序算法系列 这是 Java 实现排序算法的第三篇文章——插入排序算法。插入排序可以说成是「一类」简...

  • 排序

    八大排序算法 一、归并排序 递归及非递归的JAVA实现 二、快速排序 快排算法JAVA实现 三、堆排序 堆排序堆排...

  • 一文搞定十大经典排序算法(Java实现)

    本文总结十大经典排序算法及变形,并提供Java实现。参考文章:十大经典排序算法总结(Java语言实现)快速排序算法...

  • 快速排序

    手写java版快速排序算法实现

  • 排序算法

    常见排序算法比较 参考资料:各种排序算法比较 参考资料:快速排序算法 必须知道的八大种排序算法【java实现】(一...

  • 排序算法最强总结及其代码实现(Python/Java)

    前言 本文总结了常用的全部排序算法,内容包括: 排序算法的定义和思路 排序算法的代码实现:Python和Java,...

  • 7大经典的排序算法总结实现

    作者 : 专注J2EE来源 : 博客园 常见排序算法总结与实现 本文使用Java实现这几种排序。以下是对排序算法总...

  • 【算法】排序(一)选择排序

    在排序算法中,最简单的莫过于选择排序了。 本文将介绍以下内容 排序思路算法实现(JAVA)测试阶段算法分析 排序思...

  • 常用数据结构及算法

    数据结构与算法——常用排序算法及其Java实现 - QueenKing - SegmentFault 思否

网友评论

      本文标题:java实现五大排序算法

      本文链接:https://www.haomeiwen.com/subject/ufepuxtx.html