xml地图|网站地图|网站标签 [设为首页] [加入收藏]

排序算法java,7大排序算法总结篇

来源:http://www.ccidsi.com 作者:集成经验 人气:131 发布时间:2019-11-02
摘要:几大排序算法的Java完结,排序算法java 多多的面试题都问到了排序算法,中间的算法和沉思比较重大,那边笔者采用了5种常用排序算法并用Java实行了落实。本身写一个模板已防早先面

几大排序算法的Java完结,排序算法java

多多的面试题都问到了排序算法,中间的算法和沉思比较重大,那边笔者采用了5种常用排序算法并用Java实行了落实。本身写一个模板已防早先面试用到。大家能够看过算法之后,本人去落实一下。

1.冒泡排序:大数向下沉,小数向上浮。

package TestProject;
/**
 * 冒泡排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        bubbleSort(a);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }
    public static void bubbleSort(int[] a){
        int len = a.length;//数组长度
        for(int i=0;i<len;i  ){//每趟把最大数下沉到数组最后面
            for(int j=0;j<len-1;j  ){
                if(a[j 1]<a[j]){//如果数组后面的数比前面的小,则往后换下沉
                    int temp = a[j];
                    a[j] = a[j 1];
                    a[j 1] = temp;
                }
            }
        }
    }
}

1.1冒泡排序的优化大器晚成:用二个变量记录每次大数下沉的职位,标量值表明该变量前边数组已排序落成。

package TestProject;
/**
 * 冒泡排序优化
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        bubbleSort_1(a);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }
    public static void bubbleSort_1(int[] a){
        int len = a.length;//数组长度
        int i = len-1;
        while(i>0){
            int pos = 0;
            for(int j=0;j<i;j  ){//只需排序a[0,1,...,pos]
                if(a[j]>a[j 1]){
                    int temp = a[j];
                    a[j] = a[j 1];
                    a[j 1] = temp;
                    pos = j;
                }
            }
            i = pos;//下一摊,a[pos 1,...,len-1]已排序好
        }
    }
}

 

1.2冒泡排序的优化二:将时局向下沉同期小数向下浮。

package TestProject;
/**
 * 冒泡排序优化
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        bubbleSort_2(a);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }
    public static void bubbleSort_2(int[] a){
        int len = a.length;//数组长度
        int hight = len-1;
        int low = 0;
        while(low<hight){
            for(int i=low;i<hight;i  ){//大数下沉
                if(a[i]>a[i 1]){
                    int temp = a[i];
                    a[i] = a[i 1];
                    a[i 1] = temp;
                }
            }
            hight--;//每趟数组大数下沉到无序数组最后面,后面大数已排序好(这地方可以优化,可以每趟给一个变量记录其最后交换的位置,说明变量后面的数组已排序好)
            for(int i=hight;i>low;i--){//小数上浮
                if(a[i]<a[i-1]){
                    int temp = a[i];
                    a[i] = a[i-1];
                    a[i-1] = temp;
                }
            }
            low  ;//每趟数组小数上浮到无序数组最前面,前面的小数已排序好
        }
    }
}

 

2.插入排序:大概观念正是四个数组,一个平稳数组,一个冬辰数组,将冬季数组插入有序数列中。其元帅a[0]用作有序数组,a[1,...,len-1]用作冬辰数组。

package TestProject;
/**
 * 插入排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        insertSort(a);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }
    public static void insertSort(int[] a){
        int len = a.length;//数组长度
        for(int i=1;i<len;i  ){
            int temp = a[i];
            int j;
            for(j=i-1;j>=0;j--){//将a[i]插入a[0,..,i]序列中
                if(a[j]<=temp){
                    break;
                }else{
                    a[j 1]=a[j];//插入有序数组时(从小到大),如果插入的数比当前数小,则向前插入,此时的数向后挪一位
                }        
            }
            a[j 1] = temp;//此时插入数在有序数列的位置
        }
    }
}

3.选项排序:每回接纳出最小的数位居数组最前边。

package TestProject;
/**
 * 选择排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        selectSort(a);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }
    public static void selectSort(int[] a){
        int len = a.length;
        for(int i=0;i<len;i  ){
            int min = selectMin(a,i,len-1);
            int temp = a[min];//将无序数列的最小值换到前面
            a[min] = a[i];
            a[i] = temp;
        }
    }
    public static int selectMin(int[] a,int s,int t){
        int count = s;
        for(int i=s;i<=t;i  ){
            if(a[i]<a[count])count=i;
        }
        return count;
    }
}

3.1增选排序优化风流倜傥:二元选用排序,每趟将无序数列的最大值换成背后,将小小值换成前面。

package TestProject;
/**
 * 选择排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {8,1,0,2,8,6,1};
        selectSort(a);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }
    public static void selectSort(int[] a){
        int len = a.length;
        int l = 0;
        int h = len-1;
        while(l<h){
            int[] count = selectMinMax(a,l,h);
            int temp = a[count[0]];//将无序数列的最小值换到前面
            a[count[0]] = a[l];
            a[l] = temp;          
            if(count[1]==l){  //count[0]为无序数列的最小值位置,count[1]为无序数列的最大值位置,如果当count[0]挪到l位置时(a[1,..,l-1]为有序序列),可能会出现l位置就是最大值位置
                temp = a[count[0]];
                a[count[0]] = a[h];
                a[h] = temp;
            }else{
                temp = a[count[1]];
                a[count[1]] = a[h];
                a[h] = temp;
            }

            l  ;
            h--;
        }
    }
    public static int[] selectMinMax(int[] a,int s,int t){
        int[] count = {s,t};//count[0]-min,count[1]-max
        for(int i=s;i<=t;i  ){
            if(a[i]<a[count[0]]){
                count[0]=i;
            }
            if(a[i]>a[count[1]]){
                count[1]=i;
            }
        }
        return count;
    }
}

 4.堆排序:首先建构二个最大堆,堆顶成分为最大值,每一次将堆顶成分换来数组前面,那样三回巡回就足以获得从小到大的稳步数组。

package TestProject;
/**
 * 堆排序
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        int len = a.length;
        for(int i=(len/2-1);i>=0;i--){//建立一个最大堆
            maxHeapFixDown(a,i,len);//从有叶子的父节点建立最大堆,从下到上
        }
        for(int i=a.length-1;i>=0;i--){//堆顶元素为堆的最大值,每次把堆顶换到数组后面,一次次循环就使数组变成从小到大排序
            int temp = a[i];
            a[i] = a[0];
            a[0] = temp;
            maxHeapFixDown(a,0,i);
        }
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    }/**
     * 因为我们要从小到大排序,所以需要建立一个最大堆,从i开始到n-1,此时应满足a[i]>a[i 1,...,n-1]
     */
    public static void maxHeapFixDown(int[] a,int i,int n){
        int temp = a[i];
        int j = 2*i 1;
        while(j<n){
            if((j 1)<n&&a[j]<a[j 1])j  ;
            if(a[j]<temp)break;
            a[i] = a[j];
            i=j;
            j=2*j 1;
        }
        a[i] = temp;
    }
}

 5.快捷排序:选第二个因素作为规范成分,把小于这么些标准成分的值放到前边,把超越这几个条件成分的值放到背后。每便这一个规格成分的结尾地点也正是安如磐石数列最终之处,

a[0,...,m-1] <a[m]<a[m 1,..,n]皇家88平台,,再早先边的a[0,...,m-1]举行上边的再一次操作就能够。

package TestProject;
/**
 * 快排
 * @author xuhui
 *
 */
public class SortAll {
    public static void main(String[] args){
        int[] a = {0,8,1,2,8,6,1};
        int len = a.length;
        quickSort(a,0,len-1);
        for(int i=0;i<a.length;i  ){
            System.out.print(a[i] " ");
        }
    } 
    public static void quickSort(int[] a,int s,int t){
        if(s<t){
            int x = a[s];
            int i = s;
            int j = t;
            while(i<j){
                while(i<j&&a[j]>=x)j--;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
                while(i<j&&a[i]<=x)i  ;
                temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
            quickSort(a,s,i-1);
            quickSort(a,i 1,t);
        }
    }
}

那边都以友好参照算法描述落成的Java代码,此中堆排序领会起来会相比较困难,里面大概有局地边缘条件从不杜撰到,若是有错请大家积极性修正。

非常多的面试题都问到了排序算法,中间的算法和讨论非常首要,这边小编选用了5种常用排序算法并用...

先是回看下各个排序的重大思路:
一.冒泡排序
冒泡排序首要思路是:
经过置换使相邻的五个数成为小数在前大数在后,那样每一趟遍历后,最大的数就“沉”到最终面了。重复N次即能够使数组有序。

冒泡排序改革1:在某次遍历中风姿洒脱经未有数据沟通,表达全数数组已经稳步。由此通过安装标识位来记录本次遍历有无数据交换就能够判明是不是要持续循环。

冒泡排序改革2:记录某次遍历时最终产生数据交流的地点,那么些岗位然后的数码分明已经平稳了。由此通过记录最终产生数据调换之处就能够规定下第二轮回的范围了。

二. 直接插入排序
直接插入排序主要思路是:
老是将一个待排序的多少,插入到眼下早就排好序的队列之中,直到整个数据插入完毕。

三. 直接采纳排序
直接接受排序首要思路是:
数组分成有序区和冬辰区,开始时整个数组都以冬天区,然后每趟从冬辰区选一个极小的要素直接放到有序区的结尾,直到一切数组变有序区。

地点那三种排序都以极其轻松的,上边那三种排序略有难度,希望读者能多多实行以深化掌握。

四. Hill排序
Hill排序主要思路是:
先将总体待排成分种类分割成几何个子类别(由相隔有个别“增量”的要素结合的)分别张开间接插入排序,然后挨门挨户减少增量再打开排序,待一切系列中的成分基本不改变(增量丰硕小)时,再对整个成分实行贰遍直接插入排序。由于希尔排序是对相隔多少相差的数码进行直接插入排序,因而能够形象的称Hill排序为“跳着插

五. 合并列排在一条线序
归并列排在一条线序首要思路是:
当四个数组左侧有序,侧边也长期以来,那合併那三个静止数组就到位了排序。如何让左右两边有序了?用递归!那样递归下去,归并上来便是合併列排在一条线序。

六. 登时排序
立即接收排序主要思路是:
“挖坑填数 分治法”,首先令i =L; j = R; 将a[i]挖出善变第贰个坑,称a[i]为基准数。然后j--由后迈入找比标准数小的数,找到后掘出此数填入前三个坑a[i]中,再i 由前向后找比基准数大的数,找到后也掘出此数填到前二个坑a[j]中。重复进行这种“挖坑填数”直到i==j。再将基准数填入a[i]中,那样i以前的数都比标准数小,i之后的数都比基准数大。因而将数组分成二部分再分别重复上述手续就完了了排序。

本文由68399皇家赌场发布于集成经验,转载请注明出处:排序算法java,7大排序算法总结篇

关键词: 68399皇家赌场 iOS开发 基础算法

最火资讯