美文网首页排序/算法Android开发经验谈Android开发
详解排序算法--插入排序和冒泡排序

详解排序算法--插入排序和冒泡排序

作者: 六尺帐篷 | 来源:发表于2017-08-08 13:20 被阅读242次
    • 冒泡排序
    • 插入排序
    • 插入排序和冒泡排序分析

    冒泡排序

    Paste_Image.png

    冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。尽管这个算法是最简单了解和实现的排序算法之一,但它对于包含大量的元素的数列排序是很没有效率的。

    冒泡排序算法的运作如下:

    • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
    • 针对所有的元素重复以上的步骤,除了最后一个。
    • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    冒泡排序如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,也可以把最坏情况下的复杂度降低到{O(n)}
    在这个情况,已经排序好的数列就无交换的需要。

    • 最坏时间复杂度
    201111301912294589.gif

    Java代码实现:

    package cc;
    
    public class BubbleSort {
        
        public static void bubblesort(int[] a) {
            bubblesort(a, 0, a.length-1);
        }
        
        private static void bubblesort(int[] a, int left, int right) {
            
            for(int p=right;p>=left;p--) {
                int flag = 0;
                for(int i=0;i<p;i++) {
                    if(a[i] > a[i+1]) {
                        swap(a, i, i+1);
                        flag = 1;
                    }
                }
                if(flag == 0)
                    break;
            }
        }
    
        private static void swap(int[] a, int i, int j) {
            
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            
        }
    }
    

    插入排序

    类似于摸牌的过程

    Paste_Image.png

    插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    算法描述:

    • 从第一个元素开始,该元素可以认为已经被排序
    • 取出下一个元素,在已经排序的元素序列中从后向前扫描
    • 如果该元素(已排序)大于新元素,将该元素移到下一位置
    • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
    • 将新元素插入到该位置后
    • 重复步骤2~5

    如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找插入排序

    • 最坏时间复杂度
    Insertion-sort-example-300px.gif Insertion_sort_animation.gif

    Java代码

    package cc;
    
    public class InsertSort {
    
        public static void insertsort(int[] a) {
            insertsort(a, 0, a.length-1);
        }
        
        private static void insertsort(int[] a, int left , int right) {
            int j;
            
            for(int p = left+1;p<=right;p++) {
                int temp = a[p];
                for(j=p;j>left && a[j-1] > temp;j--)
                    a[j] = a[j-1];
                a[j] = temp;
            }
        }
    }
    
    

    插入排序和冒泡排序分析

    首先我们引入逆序对的概念

    对于下标i<j,如果A[i]>A[j],则称(i,j)是一对逆序对(inversion)

    交换2个相邻元素正好消去1个逆序对!

    给定初始序列{34, 8, 64, 51,32, 21},冒泡排序和插入排序分别需要多少次元素交换才能完成?
    交换次数就是逆序对的次数,都是9次

    插入排序: T(N, I) = O( N+I ),如果序列基本有序,则插入排序简单且高效

    定理:任意N个不同元素组成的序列平均具有N ( N - 1 ) / 4 个逆序对。

    定理:任何仅以交换相邻两元素来排序的算法,其平均时间复杂度为 ( N2 ) 。 这意味着:要提高算法效率,我们

    • 每次消去不止1个逆序对!
    • 每次交换相隔较远的2个元素!

    这就是希尔排序的由来。

    相关文章

      网友评论

        本文标题:详解排序算法--插入排序和冒泡排序

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