欢迎您的访问
专注于分享最有价值的互联网技术干货

快速掌握Java 常用的排序算法

几个T的资料等你来白嫖
双倍快乐

简单的看一下关于常用的排序结构,如图

20210413141602986.png

本章代码重点实现: 插入排序 、选择排序、交换排序 这三类。

冒泡排序

原理:一次性用两个元素进行比较,如果小/大的就交换。走访数列的工作是重复地进行直到没有再需要交换位置。
20210413141603241.gif
代码:

/**
 * 冒泡排序
 * 
 * @author cjl
 *
 */
public class BubblingSort {

    public int[] BubblingSort(int[] res) {
        for (int i = 0; i < res.length; i++) {

  // 设置循环的次数
            for (int j = 0; j < res.length - i - 1; j++) {

  // 排序次数
                if (res[j] > res[j + 1]) {

  // 判断第一个值是否》大于第二个值
                    // 交换两个值就行
                    int temp = res[j]; // 先找一个值记录其中一个值
                    res[j] = res[j + 1];// 把大的值赋值过去
                    res[j + 1] = temp;// 替换位置
                }
            }
        }
        return res;
    }
}

快速排序

20210413141604131.gif
快速排序 流程方法:

  1. 设置一个基数,通常默认第一个排序。
  2. 【顺序逻辑】从后往前比较,基数小于等于后面的值,把该数放在基数对应的位置上(前一个位置坑里)从前往后比较,基数大于前面某个值,把该数放在基数对应的位置上(前一个位置坑里)。
  3. 【倒序逻辑】 从后往前比较 ,基数大于后面的值,把该数放到基数对应的位置上(前一个位置坑里),从前往后比较,基数小于等于某个值,把该数放在基数对应的位置上(前一个位置里面)
  4. 循环 2.3 步骤

通过图我详细解释一下:

20210413141604319.png

绿色位置 是设置的当前基础值【坑位1】。黄色表示的是坑位。顶上粉红色和蓝色表示 移动游标位置

1、 从后往前比较 比较小于基础值。 5 这个数先从后往前 比较 ,0小于5 因此0 下面挖一个坑2此时将 坑位2 对应 0这个数放到坑位1 对应的数上。
2、 从前往后比较 比较大于等于基础值。 9大于5 挖坑,坑位3,把坑位3对应数字9 填入之前坑位2的位置。
3、 当前最顶部两个游标贴在一起的时候,此时7 坑位 没有数字,把基数放到当前7坑位对应数值下 如图 蓝色5表示。

20210413141604436.png

4、 此时数组就分成3 部分 黄色 + 基数+绿色,再次递归黄色部分 或者绿色部分。每次递归的时候 主要找到 黄色和红色基础值的位置

/**
 * 快速排序
 * <li> 【顺序】  基数大于前者 ,小于等于后者 </li>
 * <li> 【倒序】  基数小于等于前者 ,大于后者 </li>
 * <li>设置一个基础key值</li>
 * <li>从后往前找到比他小/大于等于他的数,找到这个数字,填写到前一个坑里</li>
 * <li>在从前往后找到比它大或者等于/小于等于他的数字,找到后放到填写到前面那个坑里</li>
 * 
 * 
 * 
 * 
 * @author cjl
 *
 */
public class QuickSort {

    /**
     * 顺序逻辑
     * 
     * @param array
     *            数组
     * @param start
     *            数组索引0
     * @param end
     *            数组索引最后一位array.length-1
     * @return
     */
    public void QuickSort(int[] array, int start, int end) {
        // 当前游标索引值相等的时候 停止递归
        if (start < end) {
            int index = getIndex(array, start, end);
            // 根据索引值 递归 不递归索引值 从0 ~ index-1 | index+1~end
            QuickSort(array, 0, index - 1);
            QuickSort(array, index + 1, end);
        }
    }

    /**
     * 
     * @param array
     * @param start
     * @param end
     * @return
     */
    private int getIndex(int[] array, int start, int end) {
        int i = start;
        int j = end;
        // 定义初始值
        int x = array[i];
        while (i < j) {
            // 移动游标 从 后--》前移动 基数值小于等于后面的值 游标从右向左推进
            while (i < j && array[j] >= x) {
                j--;
            }
            // 如果出现满足的值
            if (i < j) {
                // 把后面的值赋值给第一个基础值
                array[i] = array[j];
                i++;
            }

            // 移动游标 从前---》往后 基数值大于前面的值 游标从左往右推进
            while (i < j && array[i] < x) {
                i++;
            }
            // 如果出现满足的值
            if (i < j) {
                // 把前的值赋值给上一个值
                array[j] = array[i];
                j--;
            }
        }
        array[i] = x;
        return i;
    }

    /**
     * 倒序逻辑
     * 
     * @param array
     *            数组
     * @param start
     *            数组索引0
     * @param end
     *            数组索引最后一位array.length-1
     * @return
     */
    public void QuickSortDesc(int[] array, int start, int end) {
        // 当前游标索引值相等的时候 停止递归
        if (start < end) {
            int index = getIndexDesc(array, start, end);
            // 根据索引值 递归 不递归索引值 从0 ~ index-1 | index+1~end
            QuickSortDesc(array, 0, index - 1);
            QuickSortDesc(array, index + 1, end);
        }
    }

    private int getIndexDesc(int[] ar, int m, int n) {
        int x = ar[m];
        while (m < n) {
            // X>后者
            while (m < n && ar[n]<x) {
                n--;
            }
            if (m < n) {
                ar[m]=ar[n];
                m++;
            }
            //x<=前者
            while (m < n && ar[m]>=x) {
                m++;
            }
            if (m < n) {
                ar[n]=ar[m];
                n--;
            }
        }
        ar[m]=x;

        return m;
    }

}

插入排序

20210413141604621.gif
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

public void insertSort(int[] array) {
        // 设置循环次数 定义游标 取第二个值
        for (int i = 1; i < array.length; i++) {
            // 游标指向 当前元素下一个值
            int temp = array[i];
            // 定义第二个游标指针 指向前一个值
            int j = i - 1;
            // 如果满足 前一个值 大于后一个值,则交换两个的位置,j-- 移动游标 直到与最后一个交换为止
            for (; j >= 0 && array[j] > temp; j--) {
                // 较小的值与相邻的值换位置
                array[j + 1] = array[j];
                // j-- 移动游标 向前移动游标 继续比较
            }
            array[j + 1] = temp;
        }
    }

希尔排序

希尔排序根据 分组插入排序,该方法又称缩小增量排序。
20210413141605275.gif
核心流程:

  • 先对数组进行分组 数组长度进行分组【length/2】
  • 每次减小分组长的增量
  • 移动index进行 插入排序
    20210413141605513.png
/**
 * 希尔排序根据 分组插入排序,该方法又称缩小增量排序
 * 
 * @author cjl
 *
 */
public class ShellSort {

    public void ShellSort(int ar[]) {
        int len = ar.length;
        // 先计算每次分组的个数,分组 长度 =0 时候跳出循环,每次计算完成 组长/2
        for (int space = len / 2; space > 0; space = space / 2) {
            // 循环每组的个分组个数 长度是8 的数组 分组数为8/2=4 循环4次
            for (int currentIndex = 0; currentIndex < space; currentIndex++) {
                // 进行循环比较,每次比较完成交换数据 ,游标移动m+space的位置
                for (int i = currentIndex + space; i < ar.length; i = i + space) {
                    // 插入排序
                    int temp = ar[i];
                    int x = i - 1;
                    for (; x > 0 && ar[x] > temp; x--) {
                        ar[x + 1] = ar[x];
                    }
                    ar[x + 1] = temp;
                }
            }
        }
    }
}

堆排序

20210413141605902.gif
先简单给大家简单分享一下
堆的概念:
堆是一棵完全二叉树,所谓完全二叉树即叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆和二叉树的区别:
堆是一个完全二叉树,并且每个结点的值都大于或等于其左右孩子结点的值(这里的讨论以大根堆为例),所以,堆是结点之间满足一定次序关系的完全二叉树。
树的度:结点拥有的子树数 。二叉树 小于等于2。

大顶堆、小顶堆

20210413141606227.png
20210413141606414.png

/**
 * 堆排序
 * 
 * @author cjl
 *
 */
public class HeapSort {

    public TreeMap HeapSort(int[] array) {
        TreeMap  tm=new TreeMap<>();
        //建立 小根堆
        for (int i = (array.length-1)/2; i>=0; i--) {
            HeapMap(array, array.length, i);;
        }
        //输入根堆
        int n=array.length;
        while (n>0) {
            tm.put(n, array[0]);
            array[0]=array[n-1];
            n--;
            HeapMap(array, n, 0);
        }
        return tm;
    }

    private void HeapMap(int[] array, int len, int i) {
        int iLeft = i * 2 + 1;
        int iRight = i * 2 + 2;

        if (iLeft>len && iRight>len) {
            return ;
        }

        int tL=Integer.MAX_VALUE;
        int tR=Integer.MAX_VALUE;

        if (iLeft<len) {
            tL=array[iLeft];
        }
        if (iRight<len) {
            tR=array[iRight];
        }

        //当前根小于左右子节点 的话就满足最小根堆条件
        if (tL>array[i]&&tR>array[i]) {
            return;
        }
        //如果不满足的话比较最小的进行交换
        if (tL<tR) {
            swap(array, i, iLeft);
            HeapMap(array, len, iLeft);
        }else{
            swap(array, i, iRight);
            HeapMap(array, len, iRight);
        }
    }

    private void swap(int[] array, int i, int iLeft) {
        int t=array[i];
        array[i]=array[iLeft];
        array[iLeft]=t;
    }

}
//调用
public void  HeapSort() {
           int[]  array={

  8,7,6,6,10,-1,0,2,20,13,-2,-3,-5};  
           HeapSort sh=new HeapSort();
           TreeMap tm=new TreeMap<>();
           tm=sh.HeapSort(array);
           Iterator it=tm.descendingKeySet().iterator();
           while (it.hasNext()) {
            System.out.println(tm.get(it.next()));
        }

    }

简单选择排序

1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

3)重复第二步,直到所有元素均排序完毕

20210413141606582.gif

20210413141607100.png
原理

/**
 * 选择排序
 * 
 * @author cjl
 *
 */
public class SelectSort {

    public void SelectSort(int[] array) {
        // 循环次数
        for (int i = 0; i < array.length - 1; i++) {
            int k = i;
            for (int j = k+1; j < array.length; j++) {
                if (array[k] > array[j]) {
                    k = j; // 记录当前 最小值的位置
                }
            }
            if (i!=k) {
                int temp=array[i];
                array[i]=array[k];
                array[k]=temp;
            }
        }
    }

}

归并排序

20210413141607294.gif
归并排序(Merge sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

算法步骤:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针达到序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

说基数排序之前,我们简单介绍桶排序:

算法思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使 用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。

排序效率的比较

在网上搜了搜找到了这么一张图,看似蛮有道理的,如下:

20210413141607427.png

从排序效率上来说:
纯数字的话 :快速排序 、系统提供的Arrays.sort 相对较快Arrays.sort 实际上也是快速排序算法
带对象排序的:快速排序 比较快
稳定性来说的话:
归并排序,基数排序 比较好。

时间复杂度的问题

什么是时间复杂度?
时间复杂度:执行的语句次数,称为语句频度或者时间频度。

2.简单算法的时间复杂度举例

列举一些简单例子的时间复杂度。

O(1)的算法是一些运算次数为常数的算法。例如:

x=a;// 频度 1
    a=b;// 频度 1 
    b=x;// 频度 1

上面语句共三条操作,平均每条操作的频度为1,即使他有成千上万条操作,也只是个较大常数,这一类的时间复杂度为O(1)。

O(n)的算法是一些线性算法。例如:

int res =0;  //频度 1              
    for(i=0;i<n;i++)   //频度 n         
    res ++;  //频度 n

上面代码中第一行频度1,第二行频度为n,第三行频度为n,所以f(n)=n+n+1=2n+1。所以时间复杂度O(n)。这一类算法中操作次数和n正比线性增长。

O(logn) 一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取 O(logn)时间 例子:

int s=1; 
    while (s<=n) 
       s=s*2;

上面代码设第三行的频度是f(n), 则:2*f(n)<=n;f(n)<=log₂n,取最大值f(n)= log₂n,所以T(n)=O(log₂n ) 。

O(n²)(n的k次方的情况)最常见的就是平时的对数组进行排序的各种简单算法都是O(n²),例如直接插入排序的算法。

而像矩阵相乘算法运算则是O(n³)。

例子:

sum=0;                

 for(i=0;i<n;i++)  

    for(j=0;j<n;j++) 

       sum++;

第一行频度1,第二行n,第三行n²,第四行n²,T(n)=2n²+n+1 =O(n²)

常见的算法时间复杂度由小到大依次为
Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

以上是本人参考其他大神代码和博客学习的成果。如果又不足之处各位大神指教。

赞(0) 打赏
版权归原创作者所有,任何形式转载请联系我们:大白菜博客 » 快速掌握Java 常用的排序算法

评论 抢沙发

6 + 6 =
  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏