美文网首页
排序算法-冒泡、选择、堆、插入、归并、快速、希尔

排序算法-冒泡、选择、堆、插入、归并、快速、希尔

作者: 一乐乐 | 来源:发表于2022-08-14 22:58 被阅读0次
    • 排序算法,默认是升序,左边的值是属于“小”值

    理解比较大小后的交换:当前元素cur 和 左边的元素cur-1, 左边的比较大,就交换或者挪动 array[cur] = array[cur-1];

    • <font color=red>编码的区间设置:建议是左闭 右开,方便 [begin, end) </font>
    • <font color=red>计算方面:使用右移 代替 除法 </font>

    ☺ 排序算法---重点放到比较的排序算法---冒泡、选择、堆排序 插入、归并、快速、希尔,

    对于计数排序、基数排序不是面试的重点


    排序算法-冒泡、选择、堆排序

    一、冒泡排序:

    为什么要叫冒泡排序? 因为形象生动上,每一轮都是最大的那个数冒到结尾

    定义:

    从头开始index=1 比较每一对相邻元素,如果第1个比第2个大,就交换它们的位置;执行完一轮后,最末尾那个元素就是最大的元素。

    ② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①,直到全部元素有序。

    一轮的比较范围是从1 到 end,然后根据理解得到end 从最后一个元素开始不断减少】

    • 第一轮的比较,下标从1开始,左边比右边大进行交换
    图片.png
            int array[] = {1, 3, 5, -1, -8};
            //比较 end 的结束范围,从最后一个元素-第二个元素
            for(int end = array.length - 1; end > 0; end--) {
                //冒泡排序-一轮的交换
                for(int begin = 1; begin <= end; begin++) {
                    if(array[begin] < array[begin-1]) {//当前元素的左边元素比较大时要交换
                        int temp = array[begin];
                        array[begin] = array[begin-1];
                        array[begin-1]=temp;
                    }
                }
            }
    


    优化1-冒泡排序

    ▪ 提前有序,终止比较(不一定有用:因为一般在随机数据中要提前有序的概率是很低的,)

    • 布尔变量:假设本轮已经有序
            //比较 end 的结束范围,从最后一个元素-第二个元素
            for(int end = array.length - 1; end > 0; end--) {
                boolean sorted = true;//假设提前有序
                //冒泡排序-一轮的交换
                for(int begin = 1; begin <= end; begin++) {
                    if(array[begin] < array[begin-1]) {//当前元素的左边元素比较大时要交换
                        int temp = array[begin];
                        array[begin] = array[begin-1];
                        array[begin-1]=temp;
                        sorted = false;//本轮有交换,证明假设提前有序 不成立
                    }
                }
                if(sorted) break;//果然提前有序,不用再比较了
            }
    


    优化2-冒泡排序

    • 如果序列尾部已经局部是有序的,可以记录最后一次交换的位置,从而减少比较的次数。
    图片.png
    int array[] = {1, 3, 5, -1, -8};
            //比较 end 的结束范围,从最后一个元素-第二个元素
            for(int end = array.length - 1; end > 0; end--) {
                int sortedIndex = 1;//记录最后一次交换的位置,初始值为1,是为了考虑一开始数组就是完全有序的
                //冒泡排序-一轮的交换
                for(int begin = 1; begin <= end; begin++) {
                    if(array[begin] < array[begin-1]) {//当前元素的左边元素比较大时要交换
                        int temp = array[begin];
                        array[begin] = array[begin-1];
                        array[begin-1]=temp;
                        sortedIndex = begin;//记录最后一次交换的位置
                    }
                }
                end = sortedIndex;//更新比较范围到最后一次交换的位置
            }
    



    二、选择排序

    为什么要叫选择排序? 因为每一轮都是把最大的那个数的位置给选择出来

    定义:

    从序列中找出最大的那个元素,然后与最末尾的元素交换位置;执行完一轮后,最末尾的那个元素就是最大的元素。

    ② 忽略 ① 中曾经找到的最大元素,重复执行步骤 ①

    ▪ 选择排序本质上看是冒泡的优化:

    因为冒泡是从头到尾:相邻两个元素比较完就交换

    选择排序是从头到尾:先找到最大元素位置,然后记录位置,最后才交换

            int array[] = {1, 3, 5, -1, -8};
            //比较 end 的结束范围,从最后一个元素-第二个元素
            for(int end = array.length - 1; end > 0; end--) {
                int maxIndex = 0;
                //选择排序-找出本轮的最大值
                for(int begin = 1; begin <= end; begin++) {
                    if(array[maxIndex] <= array[begin]) {//取等号是为了变成稳定的排序算法 10  10()  8 --一轮比较--> 10   8   10()  
                        maxIndex = begin;
                    }
                }
                //交换,把本轮找到的最大一个数放到结尾
                int temp = array[maxIndex];
                array[maxIndex] = array[end];
                array[end] = temp;
            }
    



    三、堆排序

    ▪ 堆排序本质上看是冒泡的优化:

    选择排序是从头到尾:每一轮都在 从头到尾找到最大元素位置(内循环在找最大值)

    ---- 找最值,可以交给堆负责(优化)

    ▪ 堆排序:先原地建堆,然后尾部元素放到堆顶,然后下滤

    int array[] = {1, 3, 5, -1, -8};
    // 原地建堆
    heapSize = arrayay.length;
    for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
    }
            
    while (heapSize > 1) {
        // 交换堆顶元素和尾部元素
        int temp = array[0];
        array[0] = array[heapSize];
        array[heapSize] = temp;
        heapSize--;
        // 对0位置进行siftDown(恢复堆的性质)
        siftDown(0);
    }
    
    
        /**
         * 下滤
        */
        private void siftDown(int index) {  
            int half = heapSize >> 1;
            Integer element = array[index];
            while(index < half) { //index 必须是非叶子节点!!!
                // 默认拿是左边跟父节点比大小
                int childIndex = (index << 1) + 1;
                Integer childElement = array[childIndex];
    
                int rightIndex = childIndex + 1;
                if(rightIndex < size
                        && compare(array[rightIndex], childElement) > 0) {
                    childElement = array[childIndex = rightIndex];
                }
                
                if(compare(element, childElement) >= 0) break;
                //子结点大的话
                array[index] = childElement;
                index = childIndex;
            }
            array[index] = element;
        }
    



    排序算法-插入排序

    一、插入排序

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

    定义:① 在执行过程中,插入排序会将序列分为2部分;头部是已经排好序的,尾部是待排序的

     ② 从头开始扫描每一个元素;每当扫描到一个元素,就将它插入到头部合适的位置,使得头部数据依然保持有序
    
    图片.png
        private void sort(Integer[] array) {
    ------------------------------------------- 核心代码开始 ------------------------------------------------------------     
            for(int begin = 1; begin < array.length; begin++) {//从无序区抓起的牌
                int cur = begin;
                while(cur > 0 && cmp(array[cur], array[cur - 1]) < 0) {//这张牌不断往左边走,和紧邻[cur-1]的头部有序区进行比较,小于左边就交换
                    swap(array[cur], array[cur - 1]);
                    cur--;//交换完,这个牌的位置
                }
            }
    ------------------------------------------- 核心代码结束 ------------------------------------------------------------     
        }
        
    
    
        protected int cmp(int v1, int v2) {
            return v1 - v2;
        }
        
        protected void swap(int v1, int v2) {
            int tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
    


    优化1-插入排序

    • 优化:挪动替换交换
    图片.png
        private void sort(Integer[] array) {
            for(int begin = 1; begin < array.length; begin++) {//从无序区抓起的牌
                int cur = begin;
                Integer v = array[cur];
                while(cur > 0 && cmp(v, array[cur - 1]) < 0) {//头部有序数据中比待插入元素大的,都朝尾部方向挪动1个位置
                    array[cur] = array[cur-1];//左边的值比较大就往右边挪动
                    cur--;
                }
                //找到合适的位置,插入
                array[cur] = v;
            }
        }
    


    优化2-插入排序

    • 找位置--使用二分搜索法(通过挪动左右指针,不断缩小一半的可能范围)

    • 使用二分搜索优化了比较次数

      细节:二分搜素的开始-结束区间[begin, end)

      • int begin = 0; int end = array.length;

      • 为什么结束要取 end,因为方便后续其他计算,比如算出该区间有多少元素

    • 优化二分搜素[原:查找位置]为[查找待插入的位置]

      ▪ 原:查找到位置

    查找目标位置的:查找过程分成三种判断条件:小于,去左边查找;大于,去右边查找;等于直接返回目标

    图片.png
    ▪ 现:查找到待插入位置
    

    查找待插入的目标位置的:查找过程分成两种种判断条件:小于,去左边查找;大等于,去右边查找;因为这个等于不是待插入的目标位置

    • 待插入的目标位置是第一个大于 待插入原始的值v 的元素位置
    图片.png
        /**
         * 查找待插入位置的索引
         */
        private int search(int index) {//index 是待插入索引
            int begin = 0;
            int end = index;
            while(begin < end) {
                int mid = (begin + end) >> 2;
                if(cmp(array[index], array[mid]) < 0) {
                    end = mid;
                }else {
                    begin = mid + 1;
                }
            }
            return begin;
        }
    
    
        private void sort(Integer[] array) {
            for(int begin = 1; begin < array.length; begin++) {//从无序区抓起的牌
                Integer v = array[begin];//备份插入元素
                int insertIndex = search(begin);//查找到合适的插入位置
                for(int i = begin; i > insertIndex; i--) {//挪动腾出空间
                    array[i] = array[i - 1];
                }
                array[insertIndex] = v;
            }
        }
    



    排序算法-归并排序

    一、归并排序

    定义:

    ① 不断地将当前序列平均分割成2个子序列;直到不能再分割(序列中只剩1个元素)

    ② 不断地将2个子序列合并成一个有序序列;直到最终只剩下1个有序序列

    图片.png
        int[] leftArray;
        int[] array;
    
        private void sort(int begin, int end) {
            if(end - begin < 2) return;//至少要有2个元素
            int mid = (begin + end) >> 1;
            sort(begin, mid);//左边归并
            sort(mid, end);//右边归并
            merge(begin, mid, end);//最后进行合并
        }
        
    
        /**
         * 将 [begin, mid) 和 [mid, end) 范围的序列数组合并成一个有序序列 
         */
        private void merge(int begin, int mid, int end) {
            int li = 0, le = mid - begin;//左边数组leftArray
            int ri = mid, re = end;//右边数组
            int ai = begin;//arrayay 的索引
            for(int i = li; i < le; i++) {//拷贝arrayay左边数组到leftArray
                leftArray[i] = array[begin + i];
            }
            
            while(li < le) {//左边还有元素
                if(ri < re && cmp(array[ri], leftArray[li]) < 0) {//右边有元素,且右边的值更加小
                    array[ai++] = array[ri++];
                }else {
                    array[ai++] = leftArray[li++];//左边有元素,且左边的值更加小
                }
            }
    



    排序算法-快速排序、希尔排序

    一、快速排序

    快速排序的本质:<font color=red>逐渐将每一个元素都转换成轴点元素</font>

    定义:

    ① 从序列中选择一个轴点元素(pivot)

    ▪ 假设每次选择 0 位置的元素为轴点元素

    ② 利用 pivot 将序列分割成 2 个子序列

    ▪ 将小于 pivot 的元素放在pivot前面(左侧)

    ▪ 将大于 pivot 的元素放在pivot后面(右侧)

    ▪ 等于pivot的元素放哪边都可以

    ③ 对子序列进行 ① ② 操作

    ▪ 直到不能再分割(子序列中只剩下1个元素)

    是一个递归排序:从轴点切分成两部分,不断地对左部分进行快速排序,不断地对右部分进行快速排序

    图片.png

    判断该元素是 "甩"到左边 还是 右边,不加等号,因为加上等号会使得轴点元素分割出来的子序列极度不均匀

    • 比如 6 6 6 6 6,轴点是6,那么取等号,全部给甩到一边了
        int[] array;
    
        private void sort(int begin, int end) {
            if(end - begin < 2) return;//至少要有两个元素
            int mid = pivotIndex(begin, end);//轴点,以轴点分割成了左右两部分
            sort(begin, mid);//对左部分进行快速排序
            sort(mid + 1, end);//对右部分进行快速排序
        }
        
    
        
        
        /**
         * 对 [begin, end) 范围内的元素进行快速排序
         */
        private int pivotIndex(int begin, int end) {
            swap(begin, begin + (int)(Math.random() * (end - begin)));//随机交换begin位置的元素
            
            Integer pivot = array[begin];//备份轴点元素
            end--;//让右边指针直到元素上
            
    ------------------------------------------- 核心代码开始 ------------------------------------------------------------         
            while(begin < end) {
                //内部使用了两个while 搭配 break,实现在右边找“小”、在左边找“大”后,对数组指针指向"调头"
                while(begin < end) {              //不加等号,因为加上等号会使得轴点元素分割出来的子序列极度不均匀
                    if(cmp(pivot, array[end]) < 0) {// 右边元素>轴点元素,不是目标,要在右边找“小”
                        end--;
                    }else {
                        array[begin++] = array[end];
                        break;
                    }
                }
                
                while(begin < end) {
                    if(cmp(pivot, array[begin]) > 0) {// 左边元素<轴点元素,不是目标,要在左边找“大”
                        begin++;
                    }else {
                        array[end--] = array[begin];
                        break;
                    }
                }
            }
    ------------------------------------------- 核心代码结束 ------------------------------------------------------------     
            array[begin] = pivot;//数组轴点元素进行赋值
            return begin;
        }
    
    
        protected int cmp(int v1, int v2) {
            return v1 - v2;
        }
        
        protected void swap(int v1, int v2) {
            int tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
    



    二、希尔排序

    切分成n 列然后进行排序--> 逆序对数量逐渐减少 --> 希尔排序,底层是使用插入排序,也可以把希尔看成是对插入排序的改进版

    图片.png
        int[] array;
    
        private void sort() {
            List<Integer> stepSequence = shellStepSequence();
            for(Integer step: stepSequence) {//按照每个步长进行切割,然后进行一一对应的比较 排序
                sort(step);
            }
        }
        
        /**
         * 按照给定的步长进行切割,然后对 step 列进行排序
         */
        private void sort(Integer step) {
     ------------------------------------------- 核心代码开始 ------------------------------------------------------------         
            // col: 第几列
            for(int col = 0; col < step; col++) {//对col列进行排序
                // 第col 列中的元素: col、col+2*step、col+3*step、col+4*step
                // 结合了步长的插入排序
                for(int begin = col + step; begin < array.length; begin++) {
                    int cur = begin;
                    while(cur > col && cmp(array[cur], array[cur - step]) < 0) {
                        swap(array[cur], array[cur - step]);
                        cur -= step;
                    }
                }
            }
    ------------------------------------------- 核心代码结束 ------------------------------------------------------------         
        }
    
        /**
         * 步长序列:获取 step 步长分割数组
         */
        private List<Integer> shellStepSequence(){
            List<Integer> stepSequence = new ArrayList<>();
            int step = array.length;
            while((step >>= 1) > 0) {
                stepSequence.add(step);
            }
            return stepSequence;
        }
        
        
    
        protected int cmp(int v1, int v2) {
            return v1 - v2;
        }
        
        protected void swap(int v1, int v2) {
            int tmp = v1;
            v1 = v2;
            v2 = tmp;
        }
    


    ▪ 冒泡、选择、插入、归并、快速、希尔、堆排序,都是基于比较的排序 [<font color=red>面试会考</font>]

    • 平均时间复杂度目前最低是 O(nlogn)

    ▪ 计数排序、桶排序、基数排序,都不是基于比较的排序 [<font color=red>面试不考,作为了解</font>]

    • 它们是典型的用空间换时间,在某些时候,平均时间复杂度可以比 O(nlogn) 更低


    排序算法-计数排序、基数排序、桶排序

    一、计数排序

    图片.png

    细节:在java 整型数组,new出数组之后,内部元素默认都是 0

    int counts = new int[10]; //new 完,默认所有元素都是0

        int[] array;
    
        private void sort() {
            //找出最大值
            int max = array[0];
            for(int i = 1; i < array.length; i++) {
                if(array[i] > max) {
                    max = array[i];
                }
            }
     ------------------------------------------- 核心代码开始 ------------------------------------------------------------         
            // 开辟内存空间,存储每一个整数出现的次数
            int[] counts = new int[1 + max];//整型数组,new出数组之后,内部元素默认都是 0 
            
            //统计每个整数出现的次数
            for(int i = 0; i < array.length; i++) {
                counts[array[i]]++;
            }
            
            //根据整数出现次数,对整数进行排序
            int index = 0;//整数数组上的指针
            for(int i = 0; i < counts.length; i++) {
                while(counts[i]-- > 0) {
                    array[index++] = i;
                }
            }
    ------------------------------------------- 核心代码结束 ------------------------------------------------------------          
        }   
    

    ■ 计数排序缺点:

    • 无法对负整数进行排序

    • 极其浪费内存空间

    • 是个不稳定的排序

    ■ 计数排序的优化

    图片.png
        int[] array;
    
        private void sort() {
            // 找出最大值、最小值
            int max = array[0];//最大值
            int min = array[0];//最小值
            for(int i = 1; i < array.length; i++) {
                if(array[i] > max) {
                    max = array[i];
                }
                if(array[i] < min) {
                    min = array[i];
                }
            }
     ------------------------------------------- 核心代码开始 ------------------------------------------------------------        
            //开辟内存空间,存储次数
            int[] counts = new int[max - min + 1];
            
            //统计每个整数出现的次数
            for(int i = 0; i < array.length; i++) {
                counts[array[i] - min]++;
            }
            //累加次数
            for(int i = 1; i < counts.length; i++) {
                counts[i] += counts[i - 1];
            }
            
            //从后往前遍历元素,将它放到有序数组中的合适位置
            int[] newArray = new int[array.length];
            for(int i = array.length - 1; i >= 0; i--) {
                newArray[--counts[array[i] - min]] = array[i];// 公式 count[k - min] -p 其中p是该元素k倒数着出现的次数
            }
    ------------------------------------------- 核心代码结束 ------------------------------------------------------------         
            //将有序数组赋值到array
            for(int i = 0; i < newArray.length; i++) {
                array[i] = newArray[i];
            }
        }
    



    二、基数排序

    定义:依次对个位数、十位数、百位数、千位数、万位数...进行排序(从低位到高位)

    图片.png
        int[] array;
    
        private void sort() {
            // 找出最大值
            int max = array[0];
            for (int i = 1; i < array.length; i++) {
                if (array[i] > max) {
                    max = array[i];
                }
            }
            // max = 593
            // 个位数 array[i] / 1 % 10 = 3
            // 十位数 array[i] / 10 % 10 = 9
            // 百位数 array[i] / 100 % 10 = 5
            for (int divider = 1; divider <= array.length; divider *= 10) {
                countingSort(divider);
            }
    
        }
    
        private void countingSort(int divider) {
            // 开辟内存空间,存储次数
            int[] counts = new int[10];//给个位数、十位数、百位数排序,它们的范围都是 0-9
    
            // 统计每个整数出现的次数
            for (int i = 0; i < array.length; i++) {
    //          counts[array[i]的基数]++;
                counts[array[i] / divider % 10]++;
            }
            // 累加次数
            for (int i = 1; i < counts.length; i++) {
                counts[i] += counts[i - 1];
            }
    
            // 从后往前遍历元素,将它放到有序数组中的合适位置
            int[] newArray = new int[array.length];
            for (int i = array.length - 1; i >= 0; i--) {
    //          newArray[--counts[array[i]的基数] = array[i];
                newArray[--counts[array[i] / divider % 10]] = array[i];
            }
    
            // 将有序数组赋值到array
            for (int i = 0; i < newArray.length; i++) {
                array[i] = newArray[i];
            }
        }
    

    ■ 基数排序的另外一种思路:元素先存到桶里,然后再回收

    图片.png



    三、桶排序



    如果本文对你有帮助的话记得给一乐点个赞哦,感谢!

    相关文章

      网友评论

          本文标题:排序算法-冒泡、选择、堆、插入、归并、快速、希尔

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