美文网首页
十大排序算法 (java实现)

十大排序算法 (java实现)

作者: weihy | 来源:发表于2019-11-22 16:46 被阅读0次

转自:https://zhuanlan.zhihu.com/p/80043870

1、冒泡排序(Bubble Sort)

冒泡排序:对每一对相邻的元素比较大小,若顺序错误则交换顺序(正确的顺序由排序方向决定,我们假定数组元素应该从小到大排序);这样从头到尾操作一遍,最大的元素将会在最后一个(操作的一组元素的最后一个);对前面未确认顺序的重复以上操作,直到没有元素可操作即排序完成。

1.1 算法描述:

(1)对一组元素,将相邻两个元素比较大小,如果顺序错误则交换顺序;
(2)对每一对相邻元素作同样的操作,从每一组开头一对到最后一对元素,这样每一组元素最后一个元素会是最大;
(3)循环n次(n为数组长度),每次选择前n - 1 - i个(i为第几次循环)元素重复(1)、(2)步骤;

1.2 代码实现:

    public static int[] bubbleSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        for (int i = 0; i < len; i++){
            for (int j = 0; j < len - 1 - i; j++){
                if (arr[j+1] < arr[j]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }
2、选择排序(Selection Sort)

选择排序:是一种简单直接的排序算法,它的工作原理是:遍历未排序元素,将最小值(或者最大值)和遍历的第一个元素交换位置;然后继续在剩余未排序的元素中重复以上操作,直到将所有元素排序完成。

2.1 算法描述:
(1)初始状态:无序区为R[1..n],有序区为空;
(2)第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
(3)n-1趟结束,数组有序化了。

2.2 代码实现:

    public static int[] selectorSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        for (int i = 0; i < len-1; i++){
            int minIndex = i;
            //遍历出每趟的最小值
            for (int j = i+1; j < len; j++){
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            //把最小值与每趟第一个元素交换位置
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

3、插入排序(Insertion Sort)

插入排序:一种简单直观的排序算法。它的工作原理是:通过构建有序序列,依次取未排序序列元素,在有序序列后面从后往前扫描,找到相应位置插入,插入位置后面的元素需要依次外后移动,为新元素提供位置。

3.1 算法描述
(1)从第一个元素开始,可以认为是已经排好序了
(2)取出下一个新元素,依次从后往前扫描;
(3)如果扫描到的元素比新元素大,则将扫描到的元素依次往后移动一个位置;
(4)重复步骤(3)直到扫描到的元素小于等于新元素,则将新元素插入该位置之后;
(5)重复步骤(2)~(4),直到最后一个元素被插入正确的位置。

3.2 代码实现

    public static int[] insertionSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        for (int i = 0;i < len -1; i++){
            int curr = arr[i+1];  //这是要插入的新元素
            int preIndex = i;
            //从后往前扫描有序序列,如果新元素小于等于扫描到的元素,则将被扫描的元素依次后移一个位置,注意不要下标不要越界
            while (preIndex >= 0 && arr[preIndex] > curr){
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            //上面的while循环跳出则表示当前preIndex的元素比新元素小或者已经越界,应该把新元素插入preIndex+1位置
            arr[preIndex+1] = curr;
        }
        return arr;
    }
4、希尔排序(Shell Sort)

希尔排序:是插入排序的改良版本,又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

4.1 算法描述:
在此我们选择增量为gap = length / 2,继续缩小增量gap = gap / 2直到 gap == 1,我们用一个序列来表示这些增量{len/2, (len/2)/2, ....,1} 这种增量序列的选择和证明是一种数学难题,在此选择的增量是比较常见的,也是希尔建议的称之为希尔增量。

先将整个待排序的序列分割为若干个子序列分别进行插入排序,具体如下
(1)选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
(2)按增量序列个数k,对序列进行k 趟排序;
(3)每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

4.2 代码实现:

    public static int[] shellSort(int[] arr){
        int len = arr.length;
        if (len == 0) return arr;
        int gap = len / 2;  //增量初始值
        while (gap > 0){
            for (int i = gap; i < len; i++){
                //对每个分组进行插入排序
                int curr = arr[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && arr[preIndex] > curr){
                    arr[preIndex + gap] = arr[preIndex];
                    preIndex -= gap;
                }
                arr[preIndex + gap] = curr;
            }
            gap = gap / 2;  //缩小增量,重新分组进行插入排序
        }
        //gap==1时,将所有序列分为一组进行插入排序
        return arr;
    }
5、归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

5.1 算法描述:
(1)把长度为n的输入序列分成两个长度为n/2的子序列;
(2)对这两个子序列分别采用归并排序;
(3)将两个排序好的子序列合并成一个最终的排序序列。

5.2 代码实现:

    public static int[] mergeSort(int[] arr){
        if (arr.length < 2) return arr;
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0 , mid);
        int[] right = Arrays.copyOfRange(arr, mid , arr.length);
        return merge(mergeSort(left), mergeSort(right));
    }

    /**
     * 将两个有序序列 组合成一个新的有序序列
     */
    private static int[] merge(int[] left, int[] right){
        int[] result = new int[left.length + right.length];
        for (int index = 0, i = 0, j = 0; index < result.length; index++){

            if (i < left.length && j < right.length){
                if (left[i] <= right[j]) {
                    result[index] = left[i++];
                } else if (left[i] > right[j]) {
                    result[index] = right[j++];
                }
            } else {
                if (i >= left.length) result[index] = right[j++];
                else if (j >= right.length) result[index] = left[i++];
            }

        }
        return result;
    }

未完待续。。。

相关文章

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

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

  • 数据结构&算法(一)

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

  • 十大经典排序算法(java实现)

    前言 本文我们将以java代码实现十大经典排序算法,包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序...

  • Python一行代码实现快速排序

    上期文章排序算法——(2)Python实现十大常用排序算法为大家介绍了十大常用排序算法的前五种(冒泡、选择、插入、...

  • 排序算法

    十大经典排序算法最强总结(含JAVA代码实现) - 郭耀华 - 博客园 1、冒泡排序 前后比较 一轮排序 最后一个...

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

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

  • 排序

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

  • 快速排序

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

  • 数据结构与算法(二):排序算法

    十大基础排序算法。 Basic-Sorting-Algorithm 关于十大基本排序算法的整理。 十大排序算法分别...

  • 排序算法

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

网友评论

      本文标题:十大排序算法 (java实现)

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