美文网首页
算法-排序-上(Sorting)

算法-排序-上(Sorting)

作者: 鼬殿 | 来源:发表于2020-07-10 16:46 被阅读0次

    10大排序算法

    ◼ 以上表格是基于数组进行排序的一般性结论
    ◼ 冒泡、选择、插入、归并、快速、希尔、堆排序,属于比较排序(Comparison Sorting)

    1.冒泡排序(Bubble Sort)

    ◼ 冒泡排序也叫做起泡排序
    ◼ 执行流程(升序)
    ① 从头开始比较每一对相邻元素,如果第1个比第2个大,就交换它们的位置
    ✓ 执行完一轮后,最末尾那个元素就是最大的元素
    ② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①,直到全部元素有序

        static void bubbleSort1(Integer[] arr) {
            //外循环为排序趟数,如果数组中有n个元素,则执行n-1趟
            for (int end = arr.length-1; end > 0; end--) {
                //begin [1..length-1]
                for (int begin = 1; begin <= end; begin++) {
                    if (arr[begin] < arr[begin - 1]) {
                        int tmp = arr[begin];
                        arr[begin] = arr[begin - 1];
                        arr[begin-1] = tmp;
                    }
                }
            }
        }
    

    冒泡排序 – 优化①

    ◼ 如果序列已经完全有序,可以提前终止冒泡排序


        static void bubbleSort(Integer[] arr) {
            for (int end = arr.length-1; end > 0; end--) {
                boolean sorted = true;
                for (int begin = 1; begin <= end; begin++) {
                    if (arr[begin] < arr[begin - 1]) {
                        int tmp = arr[begin];
                        arr[begin] = arr[begin - 1];
                        arr[begin-1] = tmp;
                        //如果没有来到内循环,证明是序列有序的
                        sorted =false;
                    }
                }
                if (sorted) break;
            }
        }
    

    冒泡排序 – 优化②

    ◼ 如果序列尾部已经局部有序,可以记录最后1次交换的位置,减少比较次数


        static void bubbleSort(Integer[] arr) {
            for (int end = arr.length-1; end > 0; end--) {
                // sortedIndex的初始值在数组完全有序的时候有用
                int sortedIndex = 1;
                for (int begin = 1; begin <= end; begin++) {
                    if (arr[begin] < arr[begin - 1]) {
                        int tmp = arr[begin];
                        arr[begin] = arr[begin - 1];
                        arr[begin-1] = tmp;
                        //记录最后1次交换的位置,序列尾部已经局部有序
                        sortedIndex = begin;
                    }
                }
                end = sortedIndex;
            }
        }
    

    ◼ 最坏、平均时间复杂度:O(n^2)
    ◼ 最好时间复杂度:O(n)
    ◼ 空间复杂度:O(1)

    排序算法的稳定性(Stability)

    ◼ 如果相等的2个元素,在排序前后的相对位置保持不变,那么这是稳定的排序算法


    ◼ 对自定义对象进行排序时,稳定性会影响最终的排序效果
    ◼ 冒泡排序属于稳定的排序算法(内循环用的是比较用的是 <)

    原地算法(In-place Algorithm)

    ◼ 何为原地算法?
    不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入
    空间复杂度为 O(1) 的都可以认为是原地算法
    ◼ 非原地算法,称为 Not-in-place 或者 Out-of-place
    ◼ 冒泡排序属于 In-place

    2.选择排序(Selection Sort)

    ◼ 执行流程
    ① 从序列中找出最大的那个元素,然后与最末尾的元素交换位置
    ✓ 执行完一轮后,最末尾的那个元素就是最大的元素
    ② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①

        static void selectSort(Integer[] arr) {
            for (int end = arr.length-1; end > 0; end--) {
                int maxIndex = 0;
                for (int begin = 1; begin <= end; begin++) {
                    if (arr[maxIndex] < arr[begin]) {
                        //记录较大元素的索引
                        maxIndex = begin;
                    }
                }
                //每轮内循环结束,获取最大的元素的索引,与end位置元素交换位置
                int tmp = arr[maxIndex];
                arr[maxIndex] = arr[end];
                arr[end] = tmp; 
            }
        }
    

    ◼ 选择排序的交换次数要远远少于冒泡排序,平均性能优于冒泡排序
    ◼ 最好、最坏、平均时间复杂度:O(n^2),空间复杂度:O(1),属于不稳定排序
    例如:
    初始序列: 7 5 10a 10b 2a 4 2b
    第一躺选择排序: 7 5 2b10b 2a 4 10a

    3.堆排序(Heap Sort)

        private int heapSize;
        @Override
        protected void sort() {
            //原地建堆
            heapSize = arr.length;
            for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
                siftDown(i);
            }
            while (heapSize > 1) {
                // 交换堆顶元素和尾部元素
                swap(0, --heapSize);
                // 对0位置进行siftDown(恢复堆的性质)
                siftDown(0);
            }
        }
        
        /**
         * 让index位置的元素下滤
         * @param index
         */
        private void siftDown(int index) {
            Integer element = arr[index];
            //完全二叉树的性质:非叶子结点个数 n1 + n2 = floor( n / 2 ) = ceiling( (n – 1) / 2 )
            int half = heapSize >> 1;
            // 第一个叶子节点的索引 == 非叶子节点的数量
            // index < 第一个叶子节点的索引
            // 必须保证index位置是非叶子节点
            while (index < half) {
                // index的节点有2种情况
                // 1.只有左子节点
                // 2.同时有左右子节点
                            
                // 默认为左子节点跟它进行比较
                int childIndex = (index << 1) + 1;
                Integer child = arr[childIndex];
                // 右子节点
                int rightIndex = childIndex + 1;
                // 选出左右子节点最大的那个
                if (rightIndex < heapSize && comparable(arr[rightIndex], child) > 0) {
                    child = arr[childIndex = rightIndex];
                }
                if (comparable(element, child) >= 0) break;
                // 将子节点存放到index位置
                arr[index] = child;
                // 重新设置index
                index = childIndex;
            }
            arr[index] = element;
        }
    

    ◼ 最好、最坏、平均时间复杂度:O(nlogn),空间复杂度:O(1),属于不稳定排序

    4.插入排序(Insertion Sort)

    ◼ 插入排序非常类似于扑克牌的排序



    ◼ 执行流程
    ① 在执行过程中,插入排序会将序列分为2部分
    ✓ 头部是已经排好序的,尾部是待排序的
    ② 从头开始扫描每一个元素
    ✓ 每当扫描到一个元素,就将它插入到头部合适的位置,使得头部数据依然保持有序
    //外循环执行多少趟

    for (int begin = 1; begin < arr.length; begin++) {
        //记录索引
        int cur = begin;
        while (cur > 0 && cmp(cur, cur -1) < 0) {
            //交换
            swap(cur, cur - 1);
            cur --;
        }
    }
    

    插入排序 – 逆序对(Inversion)

    ◼ 什么是逆序对?
    数组 <2,3,8,6,1> 的逆序对为:<2,1> <3,1> <8,1> <8,6> <6,1>,共5个逆序对


    ◼ 插入排序的时间复杂度与逆序对的数量成正比关系
    逆序对的数量越多,插入排序的时间复杂度越高

    ◼ 最坏、平均时间复杂度:O(n^2)
    ◼ 最好时间复杂度:O(n)
    ◼ 空间复杂度:O (1)

    ◼ 属于稳定排序

    ◼ 当逆序对的数量极少时,插入排序的效率特别高
    甚至速度比 O nlogn 级别的 速排序还要快

    ◼ 数据量不是特别大的时候,插入排序的效率也是非常好的

    插入排序 – 优化

    ◼ 思路是将【交换】转为【挪动】



    ① 先将待插入的元素备份
    ② 头部有序数据中比待插入元素大的,都朝尾部方向挪动1个位置
    ③ 将待插入元素放到最终的合适位置
    //外循环执行多少趟

    for (int begin = 1; begin < arr.length; begin++) {
        //记录索引
        int cur = begin;
        //记录要插入的数据
        E v = arr[cur];
        while (cur > 0 && cmp(v, arr[cur -1]) < 0) {
            //挪动
            arr[cur] = arr[cur - 1];
            cur --;
        }
        arr[cur] = v;
    }
    

    二分搜索(Binar y Search)

    ◼ 如何确定一个元素在数组中的位置?(假设数组里面全都是整数)
    如果是无序数组,从第 0 个位置开始遍历搜索,平均时间复杂度:O(n)


    如果是有序数组,可以使用二分搜索,最坏时间复杂度:O(logn)

    思路
    ◼ 假设在 [begin, end) 范围内搜索某个元素 v,mid == (begin + end) / 2
    ◼ 如果 v < m,去 [begin, mid) 范围内二分搜索
    ◼ 如果 v > m,去 [mid + 1, end) 范围内二分搜索
    ◼ 如果 v == m,直接返回 mid

    示例
    public static int indexOf(int[] arr, int v) {
            if (arr == null || arr.length == 0) return -1;
            int begin = 0;
            int end = arr.length;
            while (begin < end) {
                int mid = (begin + end) >> 1;
                if (v < arr[mid]) {
                    end = mid;
                }else if (v > arr[mid]) {
                    begin = mid + 1;
                }else {
                    return mid;
                }
            }
            return -1;
        }
    

    如果存在多个重复的值,返回的是哪一个?
    ✓ 不确定

    插入排序 – 二分搜索优化

    ◼ 在元素v的插入过程中,可以先二分搜索出合适的插入位置,然后再将元素 v 插入


    ◼ 要求二分搜索返回的插入位置:第1个大于 v 的元素位置
    如果 v 是 5,返回 2
    如果 v 是 1,返回 0
    如果 v 是 15,返回 7
    如果 v 是 8,返回 5

    优化 – 思路
    ◼ 假设在 [begin, end) 范围内搜索某个元素 v,mid == (begin + end) / 2
    ◼ 如果 v < m,去 [begin, mid) 范围内二分搜索
    ◼ 如果 v ≥ m,去 [mid + 1, end) 范围内二分搜索


    优化 – 实例

    @Override
        protected void sort() {
            //外循环执行多少趟
            for (int begin = 1; begin < arr.length; begin++) {
                insert(begin, search(begin));
            }
        }
        
        /**
         * 将source位置的元素插入到dest位置
         * @param source
         * @param dest
         */
        private void insert(int source, int dest) {
            E v = arr[source];
            for (int i = source; i > dest; i--) {
                arr[i] = arr[i - 1];
            }
            arr[dest] = v;
        }
        
        /**
         * 利用二分搜索找到 index 位置元素的待插入位置
         * 已经排好序数组的区间范围是 [0, index)
         * @param index
         * @return
         */
        private int search(int index) {
            int begin = 0;
            int end = index;
            while (begin < end) {
                int mid = (begin + end) >> 1;
                if (cmp(arr[index], arr[mid]) < 0) {
                    end = mid;
                } else {
                    begin = mid + 1;
                }
            }
            return begin;
        }
    

    5.归并排序(Merge Sort)

    ◼ 1945年由约翰·冯·诺伊曼(John von Neumann)首次提出



    ◼ 执行流程
    ① 不断地将当前序列平均分割成2个子序列
    ✓ 直到不能再分割(序列中只剩 个元素)
    ② 不断地将2个子序列合并成一个有序序列
    ✓ 直到最终只剩下1个有序序列

    归并排序 – divide实现

        private E[] leftArr;
    
        @Override
        protected void sort() {
            leftArr = (E[]) new Comparable[arr.length >> 1];
            sort(0, arr.length);
        }
    
        // T(n) = T(n/2) + T(n/2) + O(n)
        /**
         * 对 [begin, end) 范围的数据进行归并排序
         */
        private void sort(int begin,int end) {
            //数组中只有一个元素
            if (end - begin < 2) return;
            int mid = (begin + end) >> 1;
            sort(begin, mid);
            sort(mid, end);
            merge(begin,mid,end);
        }
    
    

    归并排序 – merge

    归并排序 – merge细节

    归并排序 – merge – 左边先结束

    归并排序 – merge – 右边先结束

        /**
         * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
         */
        private void merge(int begin,int mid,int end) {
            int li = 0, le = mid - begin;
            int ri = mid, re = end;
            int ai = begin;
            for (int i = li; i < le; i++) {
                leftArr[i] = arr[begin + I];
            }
            // 如果左边还没有结束
            while (li < le) {
                if (ri < re && cmp(arr[ri], leftArr[li]) < 0) {
                    arr[ai++] = arr[ri++];//拷贝右边数组到array
                }else {
                    arr[ai++] = leftArr[li++];//拷贝左边数组到array
                }
            }
        }
    

    归并排序 – 复杂度分析

    ◼ 归并排序花费的时间



    ◼ 由于归并排序总是平均分割子序列,所以最好、最坏、平均时间复杂度都是 O(nlogn) ,属于稳定排序
    ◼ 从代码中不难看出:归并排序的空间复杂度是 O(n/2 + logn) = O(n)

    n/2 用于临时存放左侧数组,logn 是因为递归调用

    常见的递推式与复杂度

    6.快速排序(Quick Sort)

    ◼ 1960年由查尔斯·安东尼·理查德·霍尔(Charles Antony Richard Hoare,缩写为C. A. R. Hoare)提出
    昵称为东尼·霍尔(Tony Hoare)

    快速排序 – 执行流程

    ① 从序列中选择一个轴点元素(pivot)
    ✓ 假设每次选择 0 位置的元素为轴点元素

    ② 利用 pivot 将序列分割成 2 个子序列
    ✓ 将小于 pivot 的元素放在pivot前面(左侧)
    ✓ 将大于 pivot 的元素放在pivot后面(右侧)
    ✓ 等于pivot的元素放哪边都可以

    ③ 对子序列进行 ① ② 操作
    ✓ 直到不能再分割(子序列中只剩下1个元素)


    ◼ 快速排序的本质
    逐渐将每一个元素都转换成轴点元素

    快速排序 – 轴点构造

    快速排序 – 时间复杂度

    ◼ 在轴点左右元素数量比较均匀的情况下,同时也是最好的情况
    T( n) = 2 ∗ T (n/2) + O( n) = O(nlogn)
    ◼ 如果轴点左右元素数量极度不均匀,最坏情况
    T (n) = T(n − 1) + O(n) = O(n^2)

    ◼ 为了降低最坏情况的出现概率,一般采取的做法是
    随机选择轴点元素

    ◼ 最好、平均时间复杂度:O(nlogn)
    ◼ 最坏时间复杂度:O(n2)
    ◼ 由于递归调用的缘故,空间复杂度:O(logn)
    ◼ 属于不稳定排序


    左右节点数量极度不均匀
        @Override
        protected void sort() {
            sort(0,arr.length);
        }
        /**
         * 对 [begin, end) 范围的元素进行快速排序
         * @param begin
         * @param end
         */
        private void sort(int begin,int end) {
            if ((end - begin) < 2) return;
            // 确定轴点位置 O(n)
            int mid = pivotIndex(begin, end);
            // 对子序列进行快速排序
            sort(begin,mid);
            sort(mid + 1,end);
        }
        /**
         * 构造出 [begin, end) 范围的轴点元素
         * @return 轴点元素的最终位置
         */
        private int pivotIndex(int begin,int end) {
            //随机交换begin位置的元素
            swap(begin, begin + (int)Math.random() * (end - begin));
            E pivot = arr[begin];
            // end指向最后一个元素
            end --;
            while (begin < end) {
                while (begin < end) {
                    if (cmp(pivot, arr[end]) < 0) {// 右边元素 > 轴点元素
                        end --;
                    }else {
                        arr[begin++] = arr[end];
                        break;
                    }
                }
                while (begin < end) {
                    if (cmp(pivot, arr[begin]) > 0) {// 左边元素 < 轴点元素
                        begin ++;
                    }else {
                        arr[end--] = arr[begin];
                        break;
                    }
                }
            }
            // 将轴点元素放入最终的位置
            arr[begin] = pivot;
            // 返回轴点元素的位置
            return begin;
        }
    

    快速排序 – 与轴点相等的元素


    ◼ 如果序列中的所有元素都与轴点元素相等,利用目前的算法实现,轴点元素可以将序列分割成 2 个均匀的子序列

    ◼ 思考:cmp 位置的判断分别改为 ≤、≥ 会起到什么效果?



    ◼ 轴点元素分割出来的子序列极度不均匀
    导致出现最坏时间复杂度 O(n^2)

    相关文章

      网友评论

          本文标题:算法-排序-上(Sorting)

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