数组——排序

目录

冒泡排序

选择排序

 插入排序

补充——方法如何定义



冒泡排序

算法思想:

1、比较相邻的元素。如果前一个元素比后一个元素大,就交换这两个元素的位置。
2、每一对相邻元素做相同的工作,从开始第一对元素到最后一对元素,直至最后位置的元素就是最大值。

数组——排序


时间复杂度O(n^2)。适用于排序数量较少的情况下使用。

代码实现:

先写一个Bubble类

//先准备3个方法。
public class Bubble {
//对数组排序的方法
     public static void sort(Comparable[] a){
         for(int i = a.length-1;i > 0;i--){//初始化时所有元素都参与循环
             for(int j = 0;j < i;j++){ //每次循环后少一个数字,由i的次数来控制j循环次数
                 //比较索引j和索引j+1处的值
                 if(greater(a[j],a[j+1])){
                    exch(a,j,j+1);
                 }
             }
         }
     }
     //比较方法。比较v元素是否大于w元素
     private static boolean greater(Comparable v,Comparable w){
         return v.compareTo(w)>0;
     }
     //交换位置方法。数组元素i和j交换位置
     private static void exch(Comparable[] a,int i,int j){
         Comparable temp;
         temp = a[i];
         a[i] = a[j];
         a[j] = temp;
     }
}

接下来是一个mian方法进行测试

BubbleTest.java

import part02.sort.demo.Bubble;
import java.util.Arrays;

public class BubbleTest {
    public static void main(String[] args) {
        //实现了比较接口,提供了比较规则
        Integer[] arr = {12,3,7,8};//Integer是一个包装类它实现了Cpmparable接口
        Bubble.sort(arr);
        System.out.println(Arrays.toString(arr));//转化为字符串输出打印
    }
}

选择排序

算法思想:

每次遍历都假定第一个索引处的元素是最小值,和其他索引处的值依次进行比较,如果当前索引处的值大于其他某处索引的值,则与较小索引处的值进行交换,保证每次遍历数据其最小索引值在第一位。
时间复杂度:O(n^2),适用于少量排序。

数组——排序

 由于代码大部分与冒泡排序类似我这里这给出排序方法,比较位置、交换方法和测试类的方法和一样。

排序方法代码:

//对数据a中的元素进行排序
    public static void sort(Comparable[] a){
        for(int i = 0;i <=a.length - 2;i++){
            int minIndex = i;
            for(int j = i+1;j < a.length;j++){
                //需要比较最小索引minIndex处的值和索引处的值
                if(greater(a[minIndex],a[j])){
                    minIndex = j;
                }
            }
            //交换最小元素所在索引minIndex处的值和索引i处的值
            exch(a,i,minIndex);
        }
    }

 插入排序

 算法思想:

把所有的元素分为两组,已经排序和未排序;找到未排序的组中的第一个元素,向已排序的组中进行插入;倒叙遍历已经排序的元素,依次和待插入的元素进行比较,直至找到一个元素小于待插入元素,那么就把带插入元素放到这个位置,其他的元素向后移一位。

数组——排序

时间复杂度:O(n^2),适用于少量排序。

排序方法代码:

 //对数组的元素进行排序
    public static void sort(Comparable[] a){
        for(int i = 1;i < a.length;i++){
            //比较索引j的值和j-1处的值,如果j-1处的值比索引j大,则交换数据,
            // 反之就说明找到合适位置,退出循环即可。
            for(int j = i; j > 0;j--){
                if(greater(a[j-1],a[j])){
                    exch(a,j-1,j);
                }else {
                    break;
                }
            }
        }
    }

补充——方法如何定义

 API的设计就是数据解耦,其目的是为了更好的维护程序。

方法定义:

定义:public static void 方法名 ( ) {
          //方法体
    }

例如: private static boolean greater(Comparable v,Comparable w){
                         return v.compareTo(w)>0;    //方法体
     }

在写方法的时候一定要注意两个明确。
两个明确:返回值类型;参数

上一篇:集合


下一篇:插入排序及其改进