排序-选择排序-Java

╰半橙微兮° 2022-06-15 10:36 254阅读 0赞

这个要看算法啊，看了算法第四版  
写了笔记，想了想还是放在博客上。是分享也是方便。

定义了一个排序算法的模板类  
包含排序算法sort，less比较，exch交换还有show输出和isShorted判断是否是有序的

传入的参数是Compareble，因为都实现了接口 。所以~  
比较利用的默认的compareTo方法  
这个方法的调用者小于传入者则返回-1 相等返回0 大于返回1  
然后让其返回值判断是否小于0，小于则返回true也就是前者小于后者。讲道理的话是要升序，但是现在是降序的，那么就会执行exch交换方法了

然后交换方法 exch。就是单纯的交换位置。传入数组，i，j交换a数组中的i，j的位置。就是定义一个变量然后交换即可  
判断是否有序：传入数组。for循环进行判断：i从1开始 每次比较 a\[i\]与a\[i-1\]。如果前者小于后者那么然后直接 return falses;  
与插入不同的是每次所有的都找一遍，找到最小的。

![这里写图片描述][SouthEast]

package object;
    
    public class Example { 
    
         //排序,继承后实现排序算法
         public static void sort(Comparable[] a){};
         //比较 v,w的大小 返回时默认的compareTo方法比较小于0就是v小返回ture，v大就返回false
         public static boolean less(Comparable v,Comparable w){
              return v.compareTo(w)<0;
         };
         //交换两个元素。
         public static void exch(Comparable[] a,int i,int j){
              Comparable t = a[i];
              a[i] = a[j];
              a[j] = t;
    
         };
         //打印出所有元素
         public static void show(Comparable[] a){
              for(int i=0;i<a.length;i++){
                  System.out.print(a[i]+" ");
    
              }
         };
         //验证是否是有序的，升序，a[i]与a[i-1]比较，v与w进行比较，然后小于0就是a[i]小于a[i-1]那么就是返回了true，if就执行返回false
         public static boolean isSorted(Comparable[] a){
    
              for(int i=1;i<a.length;i++){
                  if(less(a[i], a[i-1])) {System.out.println(a[i]+"-"+a[i-1]);return false;}
    
              }
              return true;
         }
    
    }
    
    
    
    然后写正经的选择排序算法：
    理论：
    就是讲道理是一个数组，找最小的将其放在第一位。然后从下一位开始找现在最小的将其放在第二位~
    运行时间与输入无关。数据移动最少。但是无论原来是否有序。进行选择排序都要花一样的时间。哪怕是都是一样的或者是已经有序的
    
    
    
    先写所有排序算法父类（因为含有相同的方法~）代码：
    
    
    
    package sorts;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.Collections;
    
    import object.Example;
    
    /** * * @author Administrator * */
    public class xuanzhe { 
    
         public static void main(String[] args) {
              Comparable[] a = new Comparable[]{
       1,3,2,4,6,8,9,3,4,5};
              Selection.sort(a);
              boolean b = Selection.isSorted(a);
              System.out.println(b);
         }
    
    
    }
    
    class Selection extends Example{
    
         public static void sort(Comparable[] a){
              int N = a.length;
              for (int i=0;i<N;i++){
                  int min =i;
                  for (int j=i+1;j<N;j++){
                       if(less(a[j], a[min])){
                            min =j;
                            //System.out.println(a[j]);
                            exch(a, i, min);
                            };
                  }
    
    
              }
              show(a);
    
    
         }
    
    }

然后写正经的选择排序算法：  
理论：  
就是讲道理是一个数组，找最小的将其放在第一位。然后从下一位开始找现在最小的将其放在第二位~  
运行时间与输入无关。数据移动最少。但是无论原来是否有序。进行选择排序都要花一样的时间。哪怕是都是一样的或者是已经有序的

代码：

package sorts;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.Collections;
    
    import object.Example;
    
    /** * * @author Administrator * */
    public class xuanzhe { 
    
         public static void main(String[] args) {
              Comparable[] a = new Comparable[]{
       1,3,2,4,6,8,9,3,4,5};
              Selection.sort(a);
              boolean b = Selection.isSorted(a);
              System.out.println(b);
         }
    
    
    }
    
    class Selection extends Example{
    
         public static void sort(Comparable[] a){
              int N = a.length;
              for (int i=0;i<N;i++){
                  int min =i;
                  for (int j=i+1;j<N;j++){
                       if(less(a[j], a[min])){
                            min =j;
                            //System.out.println(a[j]);
                            exch(a, i, min);
                            };
                  }
    
    
              }
              show(a);
    
    
         }
    
    }

创建一个数组，类型是Comparable类型的。元素什么都行  
然后sort  
一个for循环，因为每个元素都要与后面的其他的进行比较来找到当前最小的。  
再来一个循环，初始值是上一个循环的值j=i+1;用的是 j与min进行比较。这个循环的前面要初始化下假设最小值min是当前的i。  
然后比较，如果初始的min的下一个比他小就交换。不小就接着比较。一直比较完成。交换的话是让其交换。也就是最小值与i交换。  
i就是当前循环最开始的位置。

但是遇到问题。字符就有问题。。。。鸡鸡了

找到错误了。原来理解了原理。但是写代码的时候出现了问题。上面的代码是遇到小的就交换，哪对啊。找一圈找到最小的然后循环之后再交换

**正确代码：**

package sorts;
    
    import java.lang.reflect.Array;
    import java.util.Arrays;
    import java.util.Collection;
    import java.util.Collections;
    
    import object.Example;
    
    /** * * @author Administrator * */
    public class xuanzhe { 
    
        public static void main(String[] args) {
            Comparable[] a = new Comparable[]{
       "c","b","a","p","r","g","h","w"};
            Selection.sort(a);
            boolean b = Selection.isSorted(a);
            System.out.println(b);
        }
    
    }
    
    class Selection extends Example{
    
        public static void sort(Comparable[] a){
            int N = a.length;
            for (int i=0;i<N;i++){
                int min =i;
                for (int j=i+1;j<N;j++){
                    if(less(a[j], a[min])){
                        min =j;
                        }
    
                }
                exch(a, i, min);
    
            }
            show(a);
    
    
        }
    
    }

参考：[http://blog.csdn.net/jianyuerensheng/article/category/6203559][http_blog.csdn.net_jianyuerensheng_article_category_6203559]  
图片也是在这位博主看到的，觉得人家写的好好。

[SouthEast]: /images/20220615/e87c0701469947c6a4ebb05badf98ced.png
[http_blog.csdn.net_jianyuerensheng_article_category_6203559]: http://blog.csdn.net/jianyuerensheng/article/category/6203559