一些排序算法(java描述)

Atom 发布于2019-08-16 18:26 / 3281人阅读

摘要：桶排序的基本思路是遍历一个待排的数组把每个数出现的次数记录到一个新的数组里面那这个新的数组里的下标就是待排序的数组的值设待排数组是记录待排数组的桶是让我们来理一下思路新建一个数组数组的大小是循环遍历这个数组在循环体里面将数出现的次数记

bucket sort

桶排序的基本思路是遍历一个待排的数组,把每个数出现的次数记录到一个新的数组里面,那这个新的数组里的下标就是待排序的数组的值.

设待排数组是arr,记录待排数组的桶是bucket让我们来理一下思路:

新建一个数组,数组的大小是arr.length-1;

循环遍历arr这个数组,在循环体里面将arr数出现的次数记录到bucket这个数组里面;

遍历bucket这个数组,判断值是多少就输出多少次bucket的下标;

以下是Java代码:

public static void bucketSort(int [] arr){
        int[] bucket=new int[max(arr)+1];
        for (int i = 0; i < arr.length; i++) {
            bucket[arr[i]]++;
        }
        int count=0;
        for (int i=0;i
以上只是一个简单的桶排序,不能排序负数和小数,但它的时间复杂度也仅仅是T(N)=O(N+M);
buble sort
冒泡排序的的思路就是遍历数组,交换(swap)相邻两个元素,使余下未排序数组部分最大(或最小)的元素浮到最前或最后;
这样排序一个长度为N的数组所需要的时间复杂度T(N)=O(N²)
以下是java代码:
    public static void bubbleSort(int [] arr){
        for (int i = arr.length; i > 0; i--) {
            for (int j = 0; j < i-1; j++) {
                if (arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }
冒泡排序的缺点很明显,在全部无序的情况下,时间复杂度太高了(因为它只能交换相邻两个元素);
而且上述的示例有一个需要改进的地方就是:设想一个数组前半部分是有序的,但是如果有序的话检查一次就够了(前面在排序后半部分的元素中已经检查过了),所以我们可以设一个布尔型的flag值,有序就直接跳过,这样能大大缩短代码运行时间;
selection sort
选择排序和冒泡排序有点类似,它的基本思路就是把数组看成两部分:一部分有序,一部分无序;
把后面无序的部分的最小值放到前半部分的最后面(冒泡排序是交换相邻的元素)
以下是java代码:
    public static void selectionSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j]
选择排序的时间复杂度也是O(N²)
insertion sort
插入排序的基本思路是选择后面没排序的部分的第一个元素,插入到前半部分有序的合适位置(和选择排序正好相反);
让我们来理一下思路吧:

arr[0]是有序的;
遍历余下的将arr[1]放到前面有序部分的合适位置(arr[0]前面或后面);
每次把余下部分的第一个放到前面有序的合适位置(重复1,2步骤);
直到余下的部分没有元素.

以下是java代码:
 /**
     * thought the arr as two part, the front part is ordered and the end part is unordered;
     * in the loop each time put the fist element of the end part to the appropriate position in the front part;
     * until the outer loop is over;
     * @param arr the array wait to sort;
     */
    public static void insertionSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] j; k--) {
                        arr[k]=arr[k-1];
                    }
                    arr[j]=tmp;
                    break;
                }
            }
        }
    }
由于有两层循环,所以它的时间复杂度也是O(N²),不过和选择排序不同的是它是稳定的排序;
quick sort
快速排序采用分治法(divide-and-conquer method),利用递归(recursion)对数组作拆分处理;
分治法的基本思路就是:大事化小,小事化无;
让我们来理一下思路吧:

随便找一个元素看作基准点(为了方便起见我们不妨把arr[0]看作基准点);
基准点左边的数比基准点小,右边的数比它大;
循环调用,直到每部分只有两数,左边小,右边大;

java代码如下:
    /**
     * Quicksort is a divide-and-conquer method for sorting.
     * divide the arr to two parts, set the leftest element as the standard position;
     * find the smaller element than standard position from the right;
     * find the larger element than standard position from the left;
     * @param arr the arr wait to sort
     * @param left left guard
     * @param right right guard
     */
    public static void quickSort(int[] arr,int left,int right){
        if (left>right) return;
        int i=left,j=right,pos=arr[left];
        while(i!=j){
            while(i=pos){
                j--;
            }
            while(i
由于快排是跳跃交换元素位置的(和冒泡排序不同),所以它的平均时间复杂度是O(NlogN);
没接触到递归的同学可能觉得快排有点抽象,可以参照<啊哈,算法>或<算法第四版>(实际上我也在用这两本教材),你也可以看看发明者关于快排的论文;
summary
以下是每种算法的平均时间复杂度:


name
T(N)



bucket sort
O(N+M)


buble sort
O(N²)


selection sort
O(N²)


insertion sort
O(N²)


quick sort
O(NlogN)



还有其他的希尔排序,堆排序,计数排序,基数排序啊有待读者们去一一探索,这里就不再一一赘述了.
原文链接:<算法第四版>最佳实践

name	T(N)
bucket sort	O(N+M)
buble sort	O(N²)
selection sort	O(N²)
insertion sort	O(N²)
quick sort	O(NlogN)

idc机房托管云服务器 java插入排序算法 java实验排序算法 java自然排序算法 java三种排序算法

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

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

十大经典排序算法总结(Javascript描述)

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

Binguner 2019-08-20 11:05 评论0 收藏0
基本排序 - Algorithms, Part I, week 2 ELEMENTARY SORTS

摘要：我们讨论比较排序算法的理论基础，并结合本章应用排序和优先级队列算法。基本排序引入了选择排序，插入排序和。描述了，一种保证在线性时间内运行的排序算法。当我们后续实现排序算法时，我们实际上将这个机制隐藏在我们的实现下面。前言上一篇：栈和队列下一篇：归并排序排序是重新排列一系列对象以便按照某种逻辑顺序排列的过程。排序在商业数据处理和现代科学计算中起着重要作用。在交易处理，组合优化，天体...

BLUE 2019-08-16 15:58 评论0 收藏0
八大排序算法Java实现

摘要：向后移动位简单选择排序基本思想常用于取序列中最大最小的几个数时。代码实现循环次数选出最小的值和位置交换位置堆排序基本思想对简单选择排序的优化。概述常见的八大排序算法，它们之间的关系如下： showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序希尔排序简单选择排序堆排序...

Coly 2019-08-15 11:57 评论0 收藏0
算法-java排序实现总结

摘要：一常见的排序算法及时间复杂度二各排序算法的理解及实现冒泡排序算法描述比较相邻元素，如果第一个比第二个大，交换位置，这样每经过一趟就冒出一个最大的动图演示代码实现快速排序算法描述从数列中挑出一个元素，称为基准从左向右找比这个第一个比这个基一.常见的排序算法及时间复杂度 showImg(https://segmentfault.com/img/bV8J6j?w=1722&h=1132);...

explorer_ddf 2019-08-15 15:31 评论0 收藏0
Java数据结构与算法——排序(基础概念)

摘要：排序算法索引待更数据结构与算法桶排序数据结构与算法快速排序时间复杂度算法的时间复杂度是一个函数，其定量的描述了一个算法运行时间和输入规模之间的关系。总结在介绍排序算法之前，本篇先对后面排序算法的基本概念说叨说叨，打下一个基础铺垫。声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。前言：Java数据结构与算法专题会不定时更新，欢迎各位读者监督。在介绍各类排序算法之前，本篇先聊聊算...

jzzlee 2019-08-16 11:10 评论0 收藏0