算法-java排序实现总结

explorer_ddf 发布于2019-08-15 15:31 / 1369人阅读

摘要：一常见的排序算法及时间复杂度二各排序算法的理解及实现冒泡排序算法描述比较相邻元素，如果第一个比第二个大，交换位置，这样每经过一趟就冒出一个最大的动图演示代码实现快速排序算法描述从数列中挑出一个元素，称为基准从左向右找比这个第一个比这个基

一.常见的排序算法及时间复杂度

二.各排序算法的理解及实现 1.冒泡排序（Bubble Sort）O（n²）

（1）算法描述

比较相邻元素，如果第一个比第二个大，交换位置，这样每经过一趟就冒出一个最大的

（2）动图演示

（3）代码实现

 public static int[] bubbleSort(int arr[]){
        int len = arr.length;
       for(int i = 0;iarr[j+1]){
                   int temp = arr[j];
                   arr[j] = arr[j+1];
                   arr[j+1] = temp;
               }
           }
       }
       return arr;
    }

2.快速排序 O（nlog2n）

（1）算法描述

从数列中挑出一个元素，称为"基准"（pivot）

从左向右找比这个第一个比这个基准大的数，从右往左找第一个比这个基准小的数，找到后互换位置

继续在此基础上执行第二步，直到两个寻找指针相遇

递归的（recursive）把小于基准值的序列和大于基准值的序列排序

（2）动图演示

 public static void quickSort(int[]arr, int left,int right) {
        if(left>right){return; }//递归的出口
        int i = left,j = right;
        int pivot = arr[left];//找到基准
        while (i < j) {
            //从右向左找第一个比基准值小的数
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            //从左向右找第一个比基准值大的数
            while (i < j && arr[i] <= pivot) {
                i++;
            }

            //两面都找到后互换位置
            if (i < j) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        //left=right时于基准值互换
        int tmp = arr[j];
        arr[j] = arr[left];
        arr[left] = tmp;
        //分别递归的调用基准值的左边和右边
        quickSort(arr,left,i-1);
        quickSort(arr,i+1,right);

    }

3.简单插入排序 O(n²)

（1）算法描述

从第二个元素开始（因为认为第一个元素已经有序）向前扫描

如果前一个数小于当前元素，继续跳到下一个元素开始向前扫描

如果前一个数大于当前元素，继续向前扫描，直到找到小于这个数的元素，插到它的后面

（2）动图演示

（3）代码实现

  public static void insertSort(int[] array){
        int len = array.length;
        for(int i = 1;i0 && array[j-1]>temp;j--){
                //如果比待插入数大 ，向右移
                array[j] = array[j-1];
            }
            //如果比带插入数小，插在该数后面
            array[j] = temp;
        }

4.希尔排序 O（nlogn）

（1）算法描述

其实就是对插入排序进行了优化，先对相同间隔的一组数进行插入排序，使序列基本有序，再进行间隔为1的插入排序时，减少工作量。（代码实现可对照插入排序，其实就是多了一组循环）

（2）动图演示

（3）代码实现

 public static void shellSort(int[] array){
        int len= array.length;
        int gap;//增量长度
        for(gap = len/2;gap>0;gap/=2){
            for(int i = gap;i gap && array[j - gap] > temp; j-=gap) {
                    //如果比待插入数大 ，向右移
                    array[j] = array[j - gap];
                }
                //如果比待插入数小，插在该数后面
                array[j] = temp;
            }
        }
    }

5.简单选择排序 O（n²）

（1）算法描述

将序列划分为有序区和无序区（初始状态有序区为空）

遍历无序区，选出最小的元素，放到有序区

（2）动图演示

（3）代码实现

   public static int[] selectSort(int array[]){
        for(int i=0;i
6.堆排序
（1）算法描述

专线服务服务器托管排序算法总结 java插入排序算法 java实验排序算法 java自然排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69107.html

【Java面试题】常见算法总结

摘要：常见算法种常见排序算法冒泡排序简单选择排序直接插入排序希尔排序归并排序快速排序堆排序种常见排序算法种常见排序算法的时间复杂度辅助空间以及稳定性对照表。常见算法 ...

K_B_Z 2021-10-13 09:40 评论0 收藏0
十大经典排序算法总结(Javascript描述)

摘要：算法描述冒泡排序是一种简单的排序算法。算法描述和实现一般来说，插入排序都采用在数组上实现。平均情况希尔排序年发明第一个突破的排序算法是简单插入排序的改进版它与插入排序的不同之处在于，它会优先比较距离较远的元素。前言读者自行尝试可以想看源码戳这，博主在github建了个库，读者可以Clone下来本地尝试。此博文配合源码体验更棒哦~~~ 个人博客：Damonare的个人博客原文地址：...

Binguner 2019-08-20 11:05 评论0 收藏0
SegmentFault 技术周刊 Vol.31 - 码农也要学算法

摘要：记作称为算法的渐进时间复杂度，简称时间复杂度。学习数据结构与算法之链表链表一种常见的数据结构，可以存储有序的元素集合。首先在大的分类上，它们都是散列算法。 showImg(https://segmentfault.com/img/bVSDvj?w=900&h=385); 当人工智能、AlphaGo、无人驾驶、智能投顾等词语不断在人们视野中出现的时候，意味着我们正步入一个算法的时代。计算...

cgspine 2019-06-26 15:45 评论0 收藏0
一个两年Java的面试总结

摘要：数据结构和算法树快速排序，堆排序，插入排序其实八大排序算法都应该了解一致性算法，一致性算法的应用的内存结构。如何存储一个的。八大排序算法一定要手敲一遍快排，堆排尤其重要。面试是一个双向选择的过程，不要抱着畏惧的心态去面试，不利于自己的发挥。前言 16年毕业到现在也近两年了，最近面试了阿里集团（菜鸟网络，蚂蚁金服），网易，滴滴，点我达，最终收到点我达，网易offer，蚂蚁金服二面挂掉，...

anRui 2019-08-15 14:34 评论0 收藏0
七大排序算法总结(java)

摘要：前面介绍了七大算法的思想与实现步骤，下面来做一个归总。直到无序区中的数为零，结束排序。步骤以从小到大为例，排序数组大小为。比较完以后则排序结束。堆排序思想堆排序是采用树的形式的数据结构来进行排序的，其中每一个堆都是完全二叉树。前面介绍了七大算法的思想与实现步骤，下面来做一个归总。排序方法平均复杂度最坏复杂度最好复杂度辅助空间稳定性直接选择排序 O(n^2...

cartoon 2019-08-14 14:09 评论0 收藏0