优化常见的java排序算法

目录
  • 冒泡排序
    • 原始的写法
    • 优化一
    • 优化二
  • 选择排序
    • 方法一
    • 方法二
  • 堆排序
    • 建大堆来实现堆排
    • 建小堆来实现堆排
  • 插入排序
    • 实现
    • 优化一
    • 优化二
  • 归并排序
    • 递归实现归并排序
    • 优化
  • 来看O(n)的排序
  • 当然除了基于比较的排序、还有基于非比较的排序。
  • 总结

冒泡排序

冒泡排序的思想:

每次让当前的元素和它的下一个元素比较大小、如果前一个的元素大于后一个元素的话,交换两个元素。

这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素。

那么下次扫描的长度比上次少一个、因为数组的最后一个元素已经是最大的了、即最后一个元素已经有序了。

优化一: 优化的思路就是每一次扫描遍历一次数组、如果某次的扫描之后没有发生数组元素的交换的话、那么说明数组的元素已经是有序的了,就可以直接跳出循环、没有继续扫描的必要了。

优化二:如果数组的尾部已经局部有序的话、那么在经历一次扫描之后的话、就不需要在对尾部局部有序的部分进行扫描了。具体的做法就是记录上一次交换的位置,然后让下一次的扫描到上一次的记录的位置就好了、因为记录的位置后的元素已经有序了。

原始的写法

    //常规的写法
    public static void bubbleSort1(int[] array) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                }
            }
        }
    }

优化一

    //优化一
    public static void bubbleSort2(int[] array) {
        boolean flag = true;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    flag = false;
                }
            }
            if (flag)
                break;
        }
    }

优化二

    //优化二
    public static void bubbleSort3(int[] array) {
        int end = array.length-1;
        for (int i = end; i > 0 ; i--) {
            int lastIndex = 1;
            for (int j = 0; j < end; j++) {
                if (array[j] > array[j + 1]) {
                    int tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    lastIndex = j + 1;
                }
            }
            end = lastIndex;
        }
    }

选择排序

选择排序的思想也是类似与冒泡排序的思想。再一次扫描之后找打数组当中最大的元素、将最大的元素放在数组的末尾。第二次的扫描数组的时候比上次扫描的长度减一

当然也可以换种思路来实现选择排序—每次扫描数组、然后找出最小的元素、将最小的元素放在数组的首位、下次扫描的时候不在扫描数组的首位、将第二小的元素放在数组第二个位置即可。

方法一

    public static void selectSort1(int[] array) {
        for (int end = array.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int start = 0; start <= end; start++) {
                if (array[maxIndex] < array[start]) {
                    maxIndex = start;
                }
            }
            int tmp = array[end];
            array[end] = array[maxIndex];
            array[maxIndex] = tmp;
        }
    }

方法二

    public static void selectSort2(int[] array) {
        for (int start = 0; start < array.length; start++) {
            int minIndex = start;
            for (int end = start; end < array.length; end++) {
                if (array[end] < array[minIndex]) {
                    minIndex = end;
                }
            }
            int tmp = array[minIndex];
            array[minIndex] = array[start];
            array[start] = tmp;
        }
    }

堆排序

堆排可以看作是对选择排序的一种优化、将数组原地建成大堆、将最大的元素放在数组的最后一个位置、adjust使数组继续保持大根堆、下一次的交换是和数组的倒数第二个元素进行交换。思路和前面两种排序的算法的思路一致、也是找最值、和数组的首或尾交换、下次交换的时候忽略已经交换的元素。

当然也可以建立一个小堆。堆顶已经是最小的了,那么只需要比较堆顶的左孩子和右孩子的大小即可,左孩子大于右孩子的话、交换、让右孩子adjust保持小堆(因为交换后的右孩子可能不满足小堆)即可。

建大堆来实现堆排

    public static void heapSort1(int[] array) {
        //建大堆
        for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
            adjustDown(array, p, array.length);
        }
        //交换
        int end = array.length - 1;
        while (end > 0) {
            int tmp = array[0];
            array[0] = array[end];
            array[end] = tmp;
            adjustDown(array, 0, end);
            end--;
        }
    }
    public static void adjustDown(int[] array, int p, int len) {
        int child = p * 2 + 1;
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[p]) {
                int tmp = array[child];
                array[child] = array[p];
                array[p] = tmp;
                p = child;
                child = p * 2 + 1;
            } else {
                break;
            }
        }
    }

建小堆来实现堆排

    public static void adjustDown1(int[] array, int p, int len) {
        int child = p * 2 + 1;
        while (child < len) {
            if (child + 1 < len && array[child] > array[child + 1]) {
                child++;
            }
            if (array[child] < array[p]) {
                int tmp = array[child];
                array[child] = array[p];
                array[p] = tmp;
                p = child;
                child = p * 2 + 1;
            } else {
                break;
            }
        }
    }
    public static void heapSort2(int[] array) {
        //建小堆
        for (int p = (array.length - 1 - 1) / 2; p >= 0; p--) {
            adjustDown1(array, p, array.length);
        }
        //交换
        int startIndex = 1;
        while (startIndex + 1 < array.length) {
            if (array[startIndex] > array[startIndex + 1]) {
                int tmp = array[startIndex];
                array[startIndex] = array[startIndex + 1];
                array[startIndex + 1] = tmp;
                adjustDown1(array,startIndex+1,array.length);
            }
            startIndex++;
        }
    }

插入排序

插入排序的思想就是类似于打牌的时候,左手拿的排就是有序的、右手拿牌然后将牌与前面的牌进行比较、然后插入到合适位置。

优化一:

优化一的思路就是将比较变为移动,每次拿到元素的时候就要和前面的元素进行比较、数组的逆序对比较多的话、那么每次都要比较和交换、所以我们可以先记录下当前的元素的值、将该元素前面大于该元素的数字都后移一位、然后插入、这样的话比较的和交换的次数就减少了。

优化二:

要在前面的有序的元素中找到当前元素要插入的位置、那么是不是可以使用二分查找来实现呢?所以我们可以使用二分查找来继续优化一下。

实现

    public static void insertSort1(int[] array) {
        for (int start = 1; start < array.length; start++) {
            int cur = start;
            while (cur > 0 && array[cur] < array[cur - 1]) {
                int tmp = array[cur];
                array[cur] = array[cur - 1];
                array[cur - 1] = tmp;
                cur--;
            }
        }
    }

优化一

    public static void insertSort2(int[] array){
        for (int start = 1; start < array.length; start++) {
            int cur = start;
            int tmp = array[start];
            while (cur>0 && tmp < array[cur-1]){
                array[cur] = array[cur-1];
                cur--;
            }
            array[cur] = tmp;
        }
    }

优化二

    public static void insertSort3(int[] array) {
        for (int start = 1; start < array.length; start++) {
            int cur = array[start];
            int insertIndex = searchIndex(array, start);
            for (int i = start; i > insertIndex; i--) {
                array[i] = array[i - 1];
            }
            array[insertIndex] = cur;
        }
    }
    public static int searchIndex(int[] array, int index) {
        int start = 0;
        int end = index;
        while (start < end) {
            int mid = (start + end) >> 1;
            if (array[index] < array[mid]) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

归并排序

归并排序的思想就是—不断的将当前的序列平均分为2个子序列、直到子序列中的元素的个数为1的时候、然后不断地将2个子序列合并成一个有序的序列。

优化:

可以看到每次归并的时候、申请的额外的数组的大小为左子序列的长度+右子序列的长度(end - start + 1)、归并之后将额外的数组的值赋值到原数组的对应的位置上。

那么我们可以做出优化、可以直接在原数组上进行操作、每次将左子序列的值拷贝出来、和右子序列的值比较、直接覆盖原来的值即可。这样每次申请的额外空间就比原来申请的空间减少一倍。

递归实现归并排序

    public static void mergerSortRec(int[] array) {
        mergerRec(array, 0, array.length - 1);
    }
    public static void mergerRec(int[] array, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) >> 1;
        mergerRec(array, start, mid);
        mergerRec(array, mid + 1, end);
        merger(array, start, mid, end);
    }
    private static void merger(int[] array, int start, int mid, int end) {
        int[] tmpArray = new int[end - start + 1];
        int tmpArrayIndex = 0;
        int leftStart = start;
        int leftEnd = mid;
        int rightStart = mid + 1;
        int rightEnd = end;
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            if (array[leftStart] < array[rightStart]) {
                tmpArray[tmpArrayIndex++] = array[leftStart++];
            } else {
                tmpArray[tmpArrayIndex++] = array[rightStart++];
            }
        }
        while (leftStart <= leftEnd) {
            tmpArray[tmpArrayIndex++] = array[leftStart++];
        }
        while (rightStart <= rightEnd) {
            tmpArray[tmpArrayIndex++] = array[rightStart++];
        }
        for (int i = 0; i < tmpArray.length; i++) {
            array[start + i] = tmpArray[i];
        }
    }

优化

    public static void mergerSort(int[] array, int start, int end) {
        if (end - start < 2) return;
        int mid = (start + end) >> 1;
        mergerSort(array, start, mid);
        mergerSort(array, mid, end);
        merger(array, start, mid, end);
    }
    private static void merger(int[] array, int start, int mid, int end) {
        int[] tmpLeftArray = new int[(end - start + 1) >> 1];
        int ls = 0;
        int le = mid - start;
        int rs = mid;
        int re = end;
        int arrIndex = start;
        for (int i = ls; i < le; i++) {
            tmpLeftArray[i] = array[start + i];
        }
        while (ls < le) {
            if (rs < re && array[rs] < tmpLeftArray[ls]) {
                array[arrIndex++] = array[rs++];
            } else {
                array[arrIndex++] = tmpLeftArray[ls++];
            }
        }
    }

来看O(n)的排序

public class ThreadSortDemo {
    public static void main(String[] args) {
        int[] array = {2, 23, 45, 5, 100, 0, 9};
        for (int i = 0; i < array.length; i++) {
            new ThreadSort(array[i]).start();
        }
    }
}
class ThreadSort extends Thread {
    private int val;
    ThreadSort(int val) {
        this.val = val;
    }
    @Override
    public void run() {
        try {
            Thread.sleep(val);
            System.out.print(val + " ");
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
}

当然除了基于比较的排序、还有基于非比较的排序。

计数排序:核心思想就是统计每个整数在序列中出现的次数、进而推导出每个整数在有序序列中的索引。具体的做法就是先找出序列中最大的元素、开辟出最大元素+1的数组空间、统计每个元素出现的次数counts[array[i]]++、然后遍历coutns数组、找出不为0的元素、输出对应的下标即可、也可以将下标重新放回到array数组中,也就是相当于array数组已经排好序了。

基数排序: 将所有元素统一为同样的数位长度, 数位较短的数前面补零。然后, 从最低位开始, 依次进行一次排序,这样从最低位排序一直到最高位排序完成以后, 原数组就变成一个有序序列。

桶排序:创建一定数量的桶、可以使用数组或者链表作为桶、按照一定的规则、将序列中的元素均匀的分配到对应的桶中、然后对每个桶中的元素进行单独的排序、最后将所有非空的桶的元素合并成有序序列。

总结

本篇文章就到这里了,希望对你有帮助,也希望您能够多多关注我们的更多内容!

(0)

相关推荐

  • Java实现常见排序算法的优化

    冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个元素已经是最大的了.即最后一个元素已经有序了. 优化一: 优化的思路就是每一次扫描遍历一次数组.如果某次的扫描之后没有发生数组元素的交换的话.那么说明数组的元素已经是有序的了, 就可以直接跳出循环.没有继续扫描的必要了. 优化二:如果数组的尾部已经局部有

  • 深入探究TimSort对归并排序算法的优化及Java实现

    简介 MergeSort对已经反向排好序的输入时复杂度为O(n^2),而timsort就是针对这种情况,对MergeSort进行优化而产生的,平均复杂度为n*O(log n),最好的情况为O(n),最坏情况n*O(log n).并且TimSort是一种稳定性排序.思想是先对待排序列进行分区,然后再对分区进行合并,看起来和MergeSort步骤一样,但是其中有一些针对反向和大规模数据的优化处理. 归并排序的优化思想 归并排序有以下几点优化方法: 和快速排序一样,对于小数组可以使用插入排序或者选择排

  • Java实现冒泡排序算法及对其的简单优化示例

    原理 冒泡排序大概是所有程序员都会用的算法,也是最熟悉的算法之一. 它的思路并不复杂: 设现在要给数组arr[]排序,它有n个元素. 1.如果n=1:显然不用排了.(实际上这个讨论似乎没什么必要) 2.如果n>1: (1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面.所以,我们把这两个元素交换.然后进行下两个相邻的元素的比较.如此直到最后一对元素比较完毕,则第一轮排序完成.可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对

  • Java编程中快速排序算法的实现及相关算法优化

    时间复杂度 平均情况:O(nlgn) 最坏情况:O(n*n),发生在当数据已经是排序状态时 快排算法的基本原理 1.从数据中选取一个值a[i]作为参考 2.以a[i] 为参考,将数据分成2部分:P1.P2,P1中的数据全部≤a[i],P2中的数据全部>a[i],数据变为{{P1}{a[i]}{P2}} 3.将P1.P2重复上述步骤,直到各部分中只剩1个数据 4.数据完成升序排列 基本示例: 原始数据: {3,9,8,5,2,1,6} 第1步:选取第1个数据:3 第2步:将数据分成2部分,左边≤3

  • 优化常见的java排序算法

    目录 冒泡排序 原始的写法 优化一 优化二 选择排序 方法一 方法二 堆排序 建大堆来实现堆排 建小堆来实现堆排 插入排序 实现 优化一 优化二 归并排序 递归实现归并排序 优化 来看O(n)的排序 当然除了基于比较的排序.还有基于非比较的排序. 总结 冒泡排序 冒泡排序的思想: 每次让当前的元素和它的下一个元素比较大小.如果前一个的元素大于后一个元素的话,交换两个元素. 这样的话经历一次扫描之后能确保数组的最后一个元素一定是数组中最大的元素. 那么下次扫描的长度比上次少一个.因为数组的最后一个

  • 盘点几种常见的java排序算法

    目录 1.插入排序 2.分治排序法,快速排序法 3.冒泡排序 low版 4.冒泡排序 bigger版 5.选择排序 6. 归并排序 8. 堆排序 9. 其他排序 10. 比较 总结 1.插入排序 这个打麻将或者打扑克的很好理解, 比如有左手有一副牌1,2,4,7 ,来一张3的牌, 是不是就是手拿着这张牌从右往左插到2,4之间 一次插入排序的操作过程: 将待插元素,依次与已排序好的子数列元素从后到前进行比较,如果当前元素值比待插元素值大,则将移位到与其相邻的后一个位置,否则直接将待插元素插入当前元

  • java排序算法之冒泡排序

    本文实例为大家分享了java排序算法之冒泡排序的具体代码,供大家参考,具体内容如下 冒泡排序 冒泡排序无疑是最为出名的排序算法之一,从序列的一端开始往另一端冒泡(你可以从左往右冒泡,也可以从右往左冒泡,看心情),依次比较相邻的两个数的大小(到底是比大还是比小也看你心情) java代码实现bubblesort冒泡排序 package com.zy.test; import java.util.Arrays; public class BubbleSort { public static void

  • java 排序算法之归并排序

    目录 简单介绍 基本思想 思路分析 代码实现 对代码的一些改进 大数据量耗时测试 复杂度 简单介绍 归并排序(merge sort)是利用 归并 的思想实现的排序方法,该算法采用经典的 分治(divide-and-conquer)策略 : 分(divide):将问题分成一些小的问题,然后递归求解 治(conquer):将分的阶段得到的各答案「修补」在一起 即:分而治之 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使

  • java 排序算法之冒泡排序

    目录 基本介绍 图解冒泡排序算法的过程 代码实现 演变过程 优化 封装算法 大量数据耗时测试 基本介绍 冒泡排序(Bubble Sorting)(时间复杂度为 O(n²))的基本思想:通过对待排序序列 从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序则交换,使值较大的元素逐渐从前移向后部,就像水底下的旗袍一样逐渐向上冒. 优化点:因为排序过程中,个元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志判断元素是否进行过交换.从而减

  • java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

  • java 排序算法之选择排序

    目录 基本介绍 基本思想 思路分析 代码实现 演变过程 优化 算法函数封装 大量数据耗时测试 基本介绍 选择排序(select sorting)也属于内部排序法,是从欲排序的数据中,按指定的规则选出来某个元素,再依规定交换位置后达到排序的目的. 它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 基本思想 选择排序(select sorting)也是一种简单直

  • 一文带你了解Java排序算法

    目录 一.选择排序 二.冒泡排序 三.插入排序 一.选择排序 选择排序是一种简单直观的排序算法,无论什么数据进去都是 O(n²) 的时间复杂度.所以用到它的时候,数据规模越小越好.唯一的好处可能就是不占用额外的内存空间了吧 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾. 重复第二步,直到所有元素均排序完毕. public static void selectSort(int[] arr) { //选择排序

  • Java排序算法总结之冒泡排序

    本文实例讲述了Java排序算法总结之冒泡排序.分享给大家供大家参考.具体分析如下: 前言:冒泡排序(BubbleSort)就是依次比较相邻的两个数,将小数放在前面,大数放在后面. 下面让我们一起    来看冒泡排序在Java中的算法实现. 冒泡排序是计算机的一种排序方法,它的时间复杂度为O(n^2),虽然不及堆排序.快速排序的O(nlogn,底数为2),但是有两个优点: 1."编程复杂度"很低,很容易写出代码: 2.具有稳定性,这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后

  • Java排序算法之SleepSort排序示例

    本文实例讲述了Java排序算法之SleepSort排序.分享给大家供大家参考,具体如下: 分享一个很有创意的排序算法:sleepSort .巧妙利用了线程的sleep(),代码如下: public class SleepSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] ints = {1,4,7,3,8,9,2,6,5}; So

随机推荐