通过简单排序理解大O表示法

朴灿烈づ我的快乐病毒、 2022-09-25 12:28 223阅读 0赞

https://segmentfault.com/a/1190000004577742

## 大O表示法初体验 ##

> 身在斯洛文尼亚的阿拉里克得到斯提里科被杀的消息后，仰天大笑：“终于没有人能阻止我去罗马了。”  
> 当他手下的将军问：“不知大王打算走哪条路去罗马？”  
> 西哥特王哈哈大笑，说出了那句千古名言：All roads lead to Rome

![bVtmuT][]  
条条大路通罗马，这句著名的英语谚语告诉人们，达到同一目的可以有多种不同的方法和途径。  
在编程中同样如此，同样一个编程问题，十个程序员可能会写出十种程序，算法各不相同，确实是条条大路通罗马。  
但程序员对算法的效率可不会像西哥特王那般豪放和豁达，程序员对于算法的效率十分在乎，尽管算法无论效率高低，均能解决问题，但效率高的算法，除了能解决问题，还可以在问题规模变大变复杂时，高效地解决问题。

于是，我们面临一个问题，那就是如何评价，以及从什么角度去评价一个算法。

通常，我们可能说，这个算法比那个算法更快一点，但这个比较是没有意义的。当算法要处理的数据项数量不同时，谁快谁慢都要重新评价。

评价算法时，应该结合数据量来评价，即当数据量增大时，算法所消耗的时间变化趋势。

在计算机世界中，这种粗略的评价方式被称为大O表示法

## 简单排序 ##

### 冒泡排序 ###

冒泡排序先从数组最左边开始，比较第1个和第2个元素的值，值比较高的往数组的高位排，然后依次比较第2和第3个元素，值比较大的往高位排，一直比较到倒数第2个和倒数第1个元素，这称为第一趟排序，这一趟就能确定数组中值最大的那个元素，并把这个最大的元素排到数组的最高位。  
依次类推，第二趟排序会确定数组中第二大的元素，并把它排在最大的元素前边。  
假设数组有n个元素，那么经过n-1趟排序，数组的元素就是有序的。  
因为每一趟中，最大的元素就像水泡一样，冒到了数组的高位，冒泡排序因此得名。

/**
     *
     *
     * @author beanlam
     * @date 2016年3月9日 下午11:26:20
     * @version 1.0
     *
     */
    public class SimpleSort {
    
        public static void bubbleSort(final int[] array) {
            if (array == null || array.length == 0) {
                throw new IllegalArgumentException("array");
            }
            
            int length = array.length;
            for (int outLoop = length - 1; outLoop > 0; outLoop-- ) {
                for (int innerLoop = 0; innerLoop < outLoop; innerLoop++) {
                    if (array[innerLoop] > array[innerLoop + 1]) {
                        swap(array, innerLoop, innerLoop + 1);
                    }
                }
            }
        }
        
        private static void swap(final int[] array, final int left, final int right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }

### 选择排序 ###

选择排序的过程是从左向右扫描数组，并从中找出最小值的元素，把它放在左边已知的最小位置上，比如第一趟扫描，找出最小的元素后，将该元素放到数组的下标0处。第二趟扫描从下标1开始扫描，找出最小元素后，放到下标1处。总共需要扫描n-1次，就能使该数组处于有序状态。

/**
     *
     *
     * @author beanlam
     * @date 2016年3月9日 下午11:26:20
     * @version 1.0
     *
     */
    public class SimpleSort {
    
        public static void selectionSort(final int[] array) {
            if (array == null || array.length == 0) {
                throw new IllegalArgumentException("array");
            }
            
            int length = array.length;
            int minIndex;
            for (int outLoop = 0; outLoop < length - 1; outLoop++) {
                minIndex = outLoop;
                for (int innerLoop = outLoop + 1;innerLoop < length; innerLoop++) {
                    if (array[innerLoop] < array[minIndex]) {
                        minIndex = innerLoop;
                    }
                }
                swap(array, outLoop, minIndex);
            }
        }
        
        private static void swap(final int[] array, final int left, final int right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }

### 插入排序 ###

插入排序的精髓在于先令局部有序，先令左边一部分数据有序，然后这部分有序的元素的下一位再与这些有序的元素比较，寻找合适自己站立的位置，插队排进去，插队也意味着右边的有序元素要挪动身子。  
一下提供基于for循环和while循环的两种插入排序实现方式：

/**
     *
     *
     * @author beanlam
     * @date 2016年3月9日 下午11:26:20
     * @version 1.0
     *
     */
    public class SimpleSort {
        public static void insertionSort(final int[] array) {
            if (array == null || array.length == 0) {
                throw new IllegalArgumentException("array");
            }
            
            int length = array.length;
            for (int outLoop = 1; outLoop < length; outLoop++) {
                int temp = array[outLoop];
                for (int innerLoop = outLoop - 1; innerLoop >= 0; innerLoop--) {
                    if (array[innerLoop] > temp) {
                        array[innerLoop + 1] = array[innerLoop];
                        if (innerLoop == 0) {
                            array[innerLoop] = temp;
                        }
                    } else {
                        array[innerLoop + 1] = temp;
                        break;
                    }
                }
            }
        }
        
        public static void insertionSort1(final int[] array) {
            if (array == null || array.length == 0) {
                throw new IllegalArgumentException("array");
            }
            
            int length = array.length;
            int temp;
            int innerLoop;
            for (int outLoop = 1; outLoop < length; outLoop++) {
                temp = array[outLoop];
                innerLoop = outLoop;
                while (innerLoop > 0 && array[innerLoop - 1] >= temp) {
                    array[innerLoop] = array[innerLoop-1];
                    --innerLoop;
                }
                array[innerLoop] = temp;
            }
        }
         
        private static void swap(final int[] array, final int left, final int right) {
            int temp = array[left];
            array[left] = array[right];
            array[right] = temp;
        }
    }

## 三种排序的效率比较 ##

假设需要比较的数组中有N个元素，  
冒泡排序中，需要扫描N-1趟，每扫描一趟就要多次对两个元素做比较，并且在必要时需要对两个元素做位置的交换，由于数据是随机的，所以平均下来，一趟中大概有一半被扫描的数据需要作位置的交换。  
第1趟需要N-1次比较，第2趟需要N-2次比较，以此类推，总共需要N(N-1)/2趟比较，而元素的交换次数平均下来需要做NN/4次。

选择排序和冒泡排序进行了相同次数的比较N\*(N-1)/2，但每一趟只有一次交换，甚至没有任何交换。因此，选择排序比冒泡排序更有效率，因为它减少了很多交换。

插入排序却又要比选择排序更有效率一点，因为第1趟排序中，它最多比较1次，第2趟排序中，最多比较2次， 依次类推，最后一趟，最多比较N-1次，  
平均只有全体数据的一半被比较，因此比较的次数为N\*(N-1)/4，与冒泡和选择排序不同的是，插入排序不需要交换数据，只是把一个值赋给数组的某一个下标，赋值的速度比交换数据的速度要快很多，因此插入排序比选择排序和冒泡排序更有效率。

## 回到大O表示法 ##

大O表示法只是一个粗略的估算值，它关注与随着数据量N的增大，算法速度的变化。

对于数组某个下标的赋值，算法消耗的时间是个常数K  
对于线性的查找，算法的消耗时间与N成正比。  
对于二分查找，算法消耗时间与log(N)成正比。

大O表示法通常会忽略常数，因为它关注的是算法的消耗时间随着N的变化而怎么变化。常数通常与处理器芯片或者编译器有关。

在上面的三种排序中，它们的效率为用大O表示法来表示都是O(N^2)，但实际上按比较的次数和交换的次数来考虑，插入排序效率高于选择排序，选择排序效率高于冒泡排序。

大O表示法常见的基于N的走势图如下图所示：  
![bVtmu6][]

*  [3月10日发布][3_10]

[bVtmuT]: /images/20220717/28d22baba70e4e718f4f441344bfdf69.png
[bVtmu6]: /images/20220717/1233fcb804034d3cac642e81d04a32ae.png
[3_10]: https://segmentfault.com/a/1190000004577742