Java中七种排序算法总结分析

目录
  • 前言:对文章出现的一些名词进行解释
  • 一、插入排序
    • 1.基本思想
    • 2.直接插入排序
    • 3.希尔排序(缩小增量排序)
  • 二、选择排序
    • 1.基本思想
    • 2.直接选择排序
    • 3.堆排序
  • 三、交换排序
    • 1.基本思想
    • 2.冒泡排序
    • 3.快速排序(递归与非递归)
      • 1.Hoare版
      • 2.挖坑法
      • 3.前后标记法(难理解)
      • 4.快速排序优化
      • 5.快速排序非递归
      • 6.相关特性总结
  • 四、归并排序(递归与非递归)

前言:对文章出现的一些名词进行解释

排序: 使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来的操作。

稳定性: 假定在排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,a=b,且a在b之前,而在排序后的序列中,a仍然在b之前则这种排序算法是稳定的,否则就是不稳定的。

内部排序: 数据元素全部放在内存中的排序。

外部排序: 数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。
文中所有排序都是升序。

一、插入排序

直接插入排序是一种简单的插入排序法。

1.基本思想

把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有记录全部插完为止,得到一个新的有序序列。这种思想在我们玩扑克牌的时候用到过,在我们码牌时,抽出一个牌,会从后往前依次比较牌面值,然后插入到一个比前面大且比后面小的位置中。

2.直接插入排序

步骤:

1.第一次排序先将第一个元素看成是已排序区间,将其内容保存起来
2.待排序区间是其后面的所有元素,从其后面第一个开始,依次和已排序区间里的元素比较(这里的比较是从后向前比较,也就是从其前一个元素比较到0号位置的元素)
3.如果小于已排序区间中的元素,则将该位置向后挪一位
4.直到找到第一个比其小的元素,此时其后面的所有元素都是比它大的,且都向后挪了一位,这时其后面的位置是空的,将该元素放进来即可。
5.之后取第二个,第三个…第i个依次这样比较即可,即循环起来。其中每次[0,i)是已排序区间,[i,size)是待排序区间。

动图演示:

代码实现:

    public static void insertSort(int[] array){
        int j=0;
        //i位置与之前所有下标从后往前进行比较,该位置大于i则继续往前,小于则插入到后边
        //[0,bound)已排序区间
        //[bound,size)待排序区间
        for(int bound=1;bound<array.length;bound++) {
            int temp = array[bound];
            //先取已排序区间的最后一个,依次往前进行比较
            for (j = bound - 1; j >= 0; j--) {
                //如果temp小于,则将元素往后移一位
                if (array[j]>temp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            //找到合适位置,填充
            array[j + 1] = temp;
        }
    }

相关特性总结:

时间复杂度:O(N2)
空间复杂度:O(1)
稳定性:稳定(是从后往前依次比较的)
应用场景:元素越接近有序越好(因为越接近有序比较次数就会越少,算法的时间效率就会越高)

3.希尔排序(缩小增量排序)

基本思想:
把待排序区间中所有记录分成几个组,设置一个gap值,所有距离为gap的记录分在同一组内,并分别对每个组内的记录进行排序,然后让gap以一定的规律减小,然后重复上述分组和排序的工作,当gap达到1时,所有记录已经排好序。

步骤:

1.设置gap值(每个组内元素之间间隔)
2.在每个组内进行直接插入排序
3.缩小gap值(这里我按照2倍缩小)
4.gap为1时排序完毕

图象解释:

代码实现:

    public static void shellSort(int[] array){
        int gap= array.length/2;
        while(gap>0){
            int j=0;
            //i位置与之前所有下标从后往前进行比较,该位置大于i则继续往前,小于则插入到后边
            for(int bound=gap;bound<array.length;bound+=gap) {
                int temp = array[bound];
                for (j = bound - gap; j >= 0; j-=gap) {
                    if (array[j]>temp) {
                        array[j + gap] = array[j];
                    } else {
                        break;
                    }
                }
                array[j + gap] = temp;
            }
            gap=gap/2;
        }
    }

相关特性总结:

希尔排序是对直接插入排序的优化
当gap>1时都是预排序,目的是让数组更接近有序,当gap==1时,数组已经接近有序,这样就很会快,整体而言,可以达到优化的效果
时间复杂度不确定,因为gap取值方法有很多
空间复杂度:O(1)
稳定性:不稳定(元素之间是跳着交换的)

二、选择排序

1.基本思想

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

2.直接选择排序

步骤:

1.先记录下标为0元素为最小值
2.从下标为1开始往后遍历,遇到比最小值还小的就标记起来,遍历完成即找到最小值
3.将找到的最小值与下标为0的元素进行交换
4.此时[0,1)为已排序区间,即不再动,[1,size)是待排序区间
5.从下标为1继续上面的操作,即循环起来
6.循环到最后只剩一个元素结束,排序完成

动图演示:

代码实现:

    public static void selectSort(int[] nums) {
        //每次都和第一个元素相比,如果小于则和一个元素则交换
        for(int bound=0;bound<nums.length-1;bound++){
            //先记录最小值为第一个元素
            int min=bound;
            //从其后一个开始遍历,找出后面所有元素中的最小值
            for(int i=bound+1;i<nums.length;i++){
                if(nums[min]>nums[i]){
                    min=i;
                }
            }
            //将最小值与待排序区间第一个进行交换
            swap(nums,bound,min);
        }
    }

相关特性总结:

时间复杂度:O(N2)
空间复杂度:O(1)
稳定性:不稳定
效率不是很好,实际中很少使用

3.堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。
注意:排升序要建大堆,排降序要建小堆

步骤:

1.创建一个大堆(升序)

从倒数第一个非叶子结点开始向下调整,直到根结点,创建一个大堆

2.将根结点与最后一个结点进行交换,此时最后一个元素一定是所有元素中最大的
3.将size–
4.将堆继续调整好形成一个大堆,继续上面的操作,即循环起来
5.最终排序完成

图像解释:

代码实现:

    //写一个交换函数
    private static void swap(int[] array,int parent,int child){
        int temp=array[child];
        array[child]=array[parent];
        array[parent]=temp;
    }
    //排升序建大堆
    //向下调整,上篇博客提到了
    private static void shiftDown(int[] array,int parent,int size){
        int child=parent*2+1;
        while(child<size){
            if(child+1<size&&array[child+1]>array[child]){
                child+=1;
            }
            if(array[parent]<array[child]){
                swap(array,parent,child);
                parent=child;
                child=parent*2+1;
            }else{
                return;
            }
        }
    }
    //堆排序
    public static void heapSort(int[] array){
        //创建一个堆
        int size=array.length;
        for(int root=(size-2)/2;root>=0;root--){
            shiftDown(array,root,size);
        }
        while(size>1){
            //将第一个和最后一个元素进行交换
            swap(array,0,size-1);
            //交换完成向下调整
            size--;
            shiftDown(array,0,size);
        }
    }

相关特性总结:

时间复杂度:O(NlogN)
空间复杂度:O(1)
稳定性:不稳定
使用堆来选数,效率高了很多

三、交换排序

1.基本思想

交换,就是根据序列中两个记录键值的比较结果来兑换这两个记录在序列中的位置,交换序列的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的头部移动

2.冒泡排序

步骤:

1.从0号位置开始,将元素和他后面的元素比较,如果大于则交换
2.当遍历完成,最大的元素肯定在数组的最后
3.之后再比较时,最后一个元素就是已排序区间,不再参与比较
4.重复上述步骤,即循环起来

动图演示:

代码实现:

    public static void bubbleSort(int[] nums) {
        //外层循环控制循环次数
        for(int num=1;num<nums.length;num++){
            //内层循环控制交换哪两个元素
            for(int i=0;i<nums.length-num;i++){
                if(nums[i+1]<nums[i]){
                    swap(nums,i+1,i);
                }
            }
        }
    }

相关特性总结:

时间复杂度:O(N2)
空间复杂度:O(1)
稳定性:稳定
冒泡排序在最开始就已经学到,很容易理解

3.快速排序(递归与非递归)

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该基准值将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列重复该过程,直到所有元素都排列在相应的位置上为止。

主框架实现:

    public static void quickSort(int[] array,int left,int right){
        if((right-left)<=1){
            return;
        }
        //按照基准值对array数组的[left,right)区间中的元素进行划分
        int div=partition3(array,left,right);

        //划分成功后以div为边界形成了左右两部分[left,div)和[div+1,right)
        //递归排[left,div)
        quickSort(array,left,div);

        //递归排[div+1,right)
        quickSort(array,div+1,right);
    }

从上述程序可以看出,程序结构与二叉树前序遍历规则非常像。
接下来按照基准值划分就是快排的核心,常见方法有三种:

1.Hoare版

步骤:

1.这里我们取最右侧为基准值
2.设置begin和end用来标记,让begin从左往右走,end从右往左走
3.当begin小于end时,因为我们取得基准值为最右侧,所以应先让begin从左往右走,找到比基准值大的元素就停下来
4.这时让end从右往左走,找到比基准值小的元素就停下来,两者交换位置
5.循环起来
6.当循环结束时,两个最终走到了同一个位置,将其和基准值进行交换

动图演示:

代码实现:

    private static int partition1(int[] array,int left,int right){
        int temp=array[right-1];
        //begin从左往右找
        int begin=left;
        //end从右往左找
        int end=right-1;
        while(begin<end){
            //让begin从前往后找比temp大的元素,找到之后停下来
            while(array[begin]<=temp&&begin<end){
                begin++;
            }
            //让end从后往前找比temp小的元素,找到之后停下来
            while(array[end]>=temp&&begin<end){
                end--;
            }
            //当两个在同一个位置时,不需要交换,减少交换次数
            if(begin!=end){
                swap(array,begin,end);
            }
        }
        if(begin!=right-1){
            swap(array,begin,right-1);
        }
        return begin;
    }

2.挖坑法

步骤:

1.先将基准值(这里是最右侧元素)放在临时变量temp中,这里就形成第一个坑位
2.设置begin和end用来标记,让begin从左往右走,end从右往左走
3.当begin小于end时,让begin从左往右走,找到比temp大的值,去填end的坑,同时begin这里形成一个坑位
4.然后让end从右往左走,找到比temp小的值,去填begin的坑,同时end这里形成了一个新的坑位
5.就这样一直循环,互相填坑,直到不满足循环条件
6.这时begin和end在同一个坑位,且是最后一个坑位,使用基准值填充

图象解释:

代码实现:

    private static int partition2(int[] array,int left,int right){
        int temp=array[right-1];
        int begin=left;
        int end=right-1;
        while(begin<end){
            //让begin从前往后找比基准值大的元素
            while(array[begin]<=temp&&begin<end){
                begin++;
            }
            if(begin!=end){
                //begin位置找到了一个比temp大的元素,填end的坑
                array[end]=array[begin];
                //begin位置形成了一个新的坑位
            }
            //让end从后往前找比基准值小的元素
            while(array[end]>=temp&&begin<end){
                end--;
            }
            if(begin!=end){
                //end位置找到了一个比temp小的元素,填begin的坑
                array[begin]=array[end];
                //end位置形成了一个新的坑位
            }
        }
        //begin和end位置是最后的一个坑位
        //这个坑位使用基准值填充
        array[begin]=temp;
        return begin;
    }

3.前后标记法(难理解)

小编其实也是根据大佬的代码分析出来的,要问为什么这么做咱确实也是不太理解,另外如理解错误欢迎指正
这里真诚发问,大佬们的脑子是不是和我的脑子不太一样?

步骤:

1.采用cur和prev来标记,两者都是从左往右走,不一样的是,最开始cur在0号位置,prev在cur前一个位置上
2.当遇到比temp大的元素时,prev不动,cur向前走一步,当两者一前一后的状态时,cur也会往前走一步,而prev不动
3.这样两者逐渐拉开差距,此时遇到比基准值小的元素,cur中的元素就会与prev中的元素交换
4.走到最后prev的下一个元素与基准值位置交换

图象解释:

代码实现:

    private static int partition3(int[] array,int left,int right){
        int temp=array[right-1];
        int cur=left;
        int prev=cur-1;
        //让cur从前往后找比基准值小的元素
        while(cur<right){
            if(array[cur]<temp&&++prev!=cur){
                swap(array,cur,prev);
            }
            cur++;
        }
        //将基准值的位置放置好
        if(++prev!=right-1){
            swap(array,prev,right-1);
        }
        return prev;
    }

但是会发现:

当我们选取的基准值越靠近整个数组的中间时,效率越好,这时可以看作是将数组逐渐分成了一个满二叉树,因此效率为O(NlogN)
最差时是取到其最大或者最小的元素,还是要划分n次,效率为O(N2)
一般时间复杂度都是看起最差情况,那为什么快速排序的时间复杂度是O(NlogN)呢?

其实是可以对取基准值进行优化的,详情请看下面:

4.快速排序优化

1.三数取中法选temp

之前我们只取一个基准值
优化后,我们在左边取一个,中间取一个,右边取一个
比较三个数的大小,谁在中间就取谁为基准值

    private static int getIndexOfMid(int[] array,int left,int right){
        int mid=left+((right-left)>>1);
        if(array[left]<array[right-1]){
            if(array[mid]<array[left]){
                return left;
            }else if(array[mid]>array[right-1]){
                return right-1;
            }else{
                return mid;
            }
        }

在更改上面的划分方法中,只需要看看上面取出的基准值在不在最右侧,如果不在就与最右侧的值交换,这样代码改动就比较小。

        int index=getIndexOfMid(array,left,right);
        if(index!=right-1){
            swap(array,index,right-1);
        }

2.递归到小的子区间时,可以考虑使用插入排序
在Idea的内层方法中,用的是小于47使用直接插入排序

5.快速排序非递归

如果直接转为循环不好转,之前提到可以使用栈来实现,利用栈后进先出的特性

    public static void quickSortNor(int[] array){
        Stack<Integer> s=new Stack<>();
        s.push(array.length);
        s.push(0);
        while(!s.empty()){
            int left=s.pop();
            int right=s.pop();
            if((right-left)<47){
                insertSortQuick(array,left,right);
            }else{
                int div=partition1(array,left,right);
                //先压入基准值的右半侧
                s.push(right);
                s.push(div+1);
                //再压入基准值的左半侧
                s.push(div);
                s.push(left);
            }
        }
    }

6.相关特性总结

时间复杂度:O(NlogN)
空间复杂度:O(logN)(递归单次没有借助辅助空间,高度即是深度)
稳定性:不稳定
快速排序整体综合性能和使用场景都是比较好的,所以才叫快速排序

四、归并排序(递归与非递归)

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有的子序列合并,得到完全有序的序列,即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

动图演示:

归并排序核心步骤:将两个有序数组合并成一个有序数组

    private static void mergeData(int[] array,int left,int mid,int right,int[] temp){
        int begin1=left,end1=mid;
        int begin2=mid,end2=right;
        int index=left;
        while(begin1<end1&&begin2<end2){
            //依次比较每一位上的元素,小的放入temp同时下标后移一位
            if(array[begin1]>array[begin2]){
                temp[index++]=array[begin2++];
            }else {
                temp[index++]=array[begin1++];
            }
        }
        //看两个数组哪个还没有遍历完成,直接顺次放入temp数组的后面
        while(begin1<end1){
            temp[index++] = array[begin1++];
        }
        while(begin2<end2){
            temp[index++]=array[begin2++];
        }
    }

主程序(递归):
步骤:

1.先对待排序区间进行均分为两个
2.使用递归,直到均分为每个区间只剩下一个元素时,每两个使用二路归并
3.将两个有序数组合并为一个有序数组,将结果保存在temp中
4.最终temp保存的就是排序完成的数组,再拷贝回原数组中

    private static void mergeSort(int[] array,int left,int right,int[] temp){
        if((right-left>1)){
            //先对[left,right)区间中的元素进行均分
            int mid=left+((right-left)>>1);
            //[left,mid)
            mergeSort(array,left,mid,temp);
            //[mid,right)
            mergeSort(array,mid,right,temp);
            //二路归并
            mergeData(array,left,mid,right,temp);
            //将temp中的元素拷贝回原数组中
            System.arraycopy(temp,left,array,left,right-left);
        }
    }

主程序(非递归):
直接采用gap对数组进行分割,每次分割完成对gap*2,一开始为2个采用二路归并,之后4个,8个,直到大于等于size结束。
非递归比递归思路更加简单。

    public static void mergeSortNor(int[] array){
        int size=array.length;
        int gap=1;
        while(gap<size){
            for(int i=0;i<size;i+=2*gap){
                //划分好要归并的区域,第一次每个区间只有一个元素
                //[left,mid)
                int left=i;
                int mid=left+gap;
                //[mid,right)
                int right=mid+gap;
                if(mid>size){
                    mid=size;
                }
                if(right>size){
                    right=size;
                }
                int[] temp=new int[size];
                //二路归并
                mergeData(array,left,mid,right,temp);
                //将temp中的元素拷贝回原数组中
                System.arraycopy(temp,left,array,left,right-left);
            }
            //gap值翻二倍,继续归并
            gap<<=1;
        }
    }

相关特性总结:

时间复杂度:O(NlogN)
空间复杂度:O(N)
稳定性:稳定
缺点在于需要O(N)的空间复杂度,归并排序解决更多的是磁盘中的外排序问题

到此这篇关于Java中七种排序算法总结分析的文章就介绍到这了,更多相关Java 排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java深入了解数据结构中常见的排序算法

    目录 一,概念 1,排序 2,稳定性 二,排序详解 1,插入排序 ①直接插入排序 2,选择排序 ①直接选择排序 ②堆排序 3,交换排序 ①冒泡排序 ②快速排序 4,归并排序 一,概念 1,排序 排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 平时的上下文中,如果提到排序,通常指的是排升序(非降序). 通常意义上的排序,都是指的原地排序(in place sort). 2,稳定性 两个相等的数据,如果经过排序后,排序算法能保证其相对位置不发生变化,则我们称该算

  • Java常用的八种排序算法及代码实现+图解

    目录 1.冒泡排序 冒泡排序法的思路 2.冒泡排序法的代码实现 3.冒泡排序法优化 4.选择排序 5.插入排序 插入排序的思路 经典的排序算法有八种,分别为: 冒泡排序 选择排序 插入排序 归并排序 希尔排序 快速排序 堆排序 基数排序 其中冒泡排序.选择排序.插入排序称为三大基本排序. 虽然这三大基本排序算法时间复杂度都是O(n2),但是其实细细讨论之下,还是有各自的特点的. 1.冒泡排序 冒泡排序法的思路 基本思路: 假设我们需要进行升序排列 进行N轮的比较,每一轮将相邻的两个元素依次比较,

  • Java 十大排序算法之冒泡排序刨析

    目录 冒泡排序原理 冒泡排序API设计 冒泡排序的代码实现 冒泡排序的时间复杂度分析 冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值 冒泡排序API设计 类名 Bubble 构造方法 Bubble:创建Bubble对象 成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C

  • Java 十大排序算法之插入排序刨析

    目录 插入排序原理 插入排序API设计 插入排序代码实现 插入排序的时间复杂度分析 插入排序原理 ①把所有元素分成已排序和未排序两组 ②找到未排序组的第一个元素,向已经排序的组中进行插入 ③倒序遍历已经排好的元素,依次和待插入的元素进行比较,直到找到一个元素小于等于待插入元素,那么就把待插入元素放到这个位置,其他元素向后移动一位 插入排序API设计 类名 Insertion 构造方法 Insertion():创建Insertion对象 成员方法 1.public static void sort

  • Java 十大排序算法之选择排序刨析

    目录 选择排序原理 选择排序API设计 选择排序代码实现 选择排序的时间复杂度 选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值 选择排序API设计 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a):对

  • Java 十大排序算法之希尔排序刨析

    目录 希尔排序原理 希尔排序的API设计 希尔排序的代码实现 希尔排序是插入排序的一种,又称"缩小增量排序",是插入排序算法的一种更高效的改进版本. 希尔排序原理 1.选定一个增长量h,按照增长量h作为数据分组的依据,对数据进行分组. 2.对分好组的每一组数据完成插入排序. 3.减小增长量,最小减为1,重复第二步操作. 希尔排序的API设计 类名 Shell 构造方法 Shell():创建Shell对象 成员方法 1.public static void sort(Comparable

  • java中几种常见的排序算法总结

    目录 本节目标: [插入排序] [优化版] [希尔排序] [选择排序] [堆排序]  [冒泡排序] 介绍一个冒泡排序的优化方法:  [快速排序] [归并排序] [正文] [代码简介:]  [排序总结] 本节目标: :分析常见的比较排序算法基本原理及实现 :分析排序算法的性能分析 :分析Java中常用排序方法 1 排序 排序,就是使一串记录,按照其中某个或某些关键字的大小,递增或递减排列的操作. 平时的上下文中,提到排序 通常指排升序. 2 稳定性 两个相同的数据,如果经过排序后,排序算法能保证其

  • Java 十大排序算法之计数排序刨析

    计数排序是非比较的排序算法,用辅助数组对数组中出现的数字计数,元素转下标,下标转元素 计数排序优缺点 优点:快 缺点:数据范围很大,比较稀疏,会导致辅助空间很大,造成空间的浪费 使用范围:数据较为密集或范围较小时适用. 思路 1.找出最大元素max 2.初始化一个max+1的数组 3.将每个元素的计数存储在数组中各自的索引处 4.存储计数数组元素的累积和 5.数组中找到原始数组的每个元素的索引 计数排序代码实现 public class CountingSort { private static

  • Java 十大排序算法之归并排序刨析

    目录 归并排序原理 归并排序API设计 归并排序代码实现 归并排序的时间复杂度分析 归并排序原理 1.尽可能的一组数据拆分成两个元素相等的子组,并对每一个子组继续拆分,直到拆分后的每个子组的元素个数是1为止. ⒉将相邻的两个子组进行合并成一个有序的大组. 3.不断的重复步骤2,直到最终只有一个组为止. 归并排序API设计 类名 Merge 构造方法 Merge():创建Merge对象 成员方法 1.public static void sort(Comparable[] a):对数组内的元素进行

  • Java中七种排序算法总结分析

    目录 前言:对文章出现的一些名词进行解释 一.插入排序 1.基本思想 2.直接插入排序 3.希尔排序(缩小增量排序) 二.选择排序 1.基本思想 2.直接选择排序 3.堆排序 三.交换排序 1.基本思想 2.冒泡排序 3.快速排序(递归与非递归) 1.Hoare版 2.挖坑法 3.前后标记法(难理解) 4.快速排序优化 5.快速排序非递归 6.相关特性总结 四.归并排序(递归与非递归) 前言:对文章出现的一些名词进行解释 排序: 使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来

  • JavaScript实现的七种排序算法总结(推荐!)

    目录 前言 冒泡排序 基础算法 第二种写法是在基础算法的基础上改良而来的: 选择排序 基础算法 二元选择排序-优化 插入排序 交换法插入排序 移动法 希尔排序 堆排序 快速排序 归并排序 总结 前言 所谓排序算法,即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序.这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率.对于排序,我们首先要求其具有一定的稳定性,即当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前

  • Java实现8种排序算法的示例代码

    冒泡排序 O(n2) 两个数比较大小,较大的数下沉,较小的数冒起来. public static void bubbleSort(int[] a) { //临时变量 int temp; //i是循环次数,也是冒泡的结果位置下标,5个数组循环5次 for (int i = 0; i < a.length; i++) { //从最后向前面两两对比,j是比较中下标大的值 for (int j = a.length - 1; j > i; j--) { //让小的数字排在前面 if (a[j] <

  • JavaScript中几种排序算法的简单实现

    排序算法的实现 我的JS水平就是渣渣,所以我就用类似于JAVA和C的方式来写JavaScript的排序算法了. 而且这里我不讲算法原理,仅仅只是代码实现,可能会有Bug,欢迎大家博客评论指导. 插入排序 插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已

  • Java的Arrays.sort()方法排序算法实例分析

    暂时网上看过很多JDK8中Arrays.sort的底层原理,有些说是插入排序,有些说是归并排序,也有说大于域值用计数排序法,否则就使用插入排序...其实不全对.让我们分析个究竟: // Use Quicksort on small arrays if (right - left < QUICKSORT_THRESHOLD) { //QUICKSORT_THRESHOLD = 286 sort(a, left, right, true); return; } 数组一进来,会碰到第一个阀值QUICK

  • PHP四种排序算法实现及效率分析【冒泡排序,插入排序,选择排序和快速排序】

    本文实例讲述了PHP四种排序算法实现及效率分析.分享给大家供大家参考,具体如下: PHP的四种基本排序算法为:冒泡排序.插入排序.选择排序和快速排序. 下面是我整理出来的算法代码: 1. 冒泡排序: 思路:对数组进行多轮冒泡,每一轮对数组中的元素两两比较,调整位置,冒出一个最大的数来. //简单版: function bubbleSort($arr) { $n = count($arr); for($i=1;$i<$n;$i++) { //冒泡的轮数(最多$n-1轮) for($j=0;$j<

  • Java常用的八种排序算法与代码实现

    目录 1.直接插入排序 2.希尔排序 3.简单选择排序 4.堆排序 5.冒泡排序 6.快速排序 7.归并排序 8.基数排序 1.直接插入排序 经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中. 将第一个数和第二个数排序,然后构成一个有序序列 将第三个数插入进去,构成一个新的有序序列. 对第四个数.第五个数--直到最后一个数,重复第二步. 如何写写成代码: 首先设定插入次数,即循环次数,for(int i=1;i<length;i++),1个数的那次不用插入. 设定插入数和得到已经排好

  • C++中十种内部排序算法的比较分析

    C++中十种内部排序算法的比较分析 #include<iostream> #include<ctime> #include<fstream> using namespace std; #define MAXSIZE 1000 //可排序表的最大长度 #define SORTNUM 10 //测试10中排序方法 #define max 100 //基数排序时数据的最大位数不超过百位: typedef struct node { int data3; int next; }

随机推荐