冒泡排序、选择排序、插入排序

系统管理员 2022-08-21 05:35 218阅读 0赞

最近在看数据结构与算法分析，想写个笔记记录一下，先从基本的冒泡、选择、插入开始吧。

注：都是以增序为例说明

一、冒泡排序

1、原理：从数组的第一个位置开始两两比较array\[index\]和array\[index+1\]，如果array\[index\]大于array\[index+1\]则交换array\[index\]和array\[index+1\]的位置，止到数组结束；

从数组的第一个位置开始，重复上面的动作，止到数组长度减一个位置结束；

从数组的第一个位置开始，重复上面的动作，止到数组长度减二个位置结束；

。。。。

2、 时间复杂度：O(N²)，进行了(n-1)\*(n-2)....=n\*(n-1)/2次比较和约比较次数一半的交换次数（均况下），那么根据大O表示法时间复杂度为O(N^2)

3、代码

/**
    * 冒泡增序算法
    * @param array
    */
    public static void  bubblingSort(int[] array){
    for(int i=0;i<array.length;i++){
    for(int j=0;j<array.length-i-1;j++){
    if(array[j]>array[j+1]){
    swap(array,j,j+1);
    }
    }
    }
    }
    
    private static void swap(int[] array,int x,int y){
    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;
    }

二、选择排序

1、原理：选择一个值array\[0\]作为标杆，然后循环找到除这个值外最小的值（查找小于标杆的最小值），交换这两个值，这时最小值就被放到了array\[0\]上，然后再将array\[1\]作为标杆，从剩下未排序的值中找到最小值，并交换这两个值。

如图：（数据结构与算法中的图）

![Center][]

2、时间复杂度：O(N^2)，与冒泡排序相比减少了数组交换的次数

3、代码

/**
    * 选择排序增序
    * @param array
    */
    public static void selectSort(int [] array){
    for(int i=0;i<array.length;i++){
    int index = i;
    for(int j=i+1;j<array.length;j++){
    if(array[j] < array[index]){
    index = j;
    }
    }
    if(i != index) swap(i,index,array);
    display(array);
    System.out.println();
    }
    }
    
    
    public static void swap(int a,int b,int array[]){
    int temp  = array[a];
    array[a] = array[b];
    array[b] = temp;
    }

三、插入排序

1、原理：插入排序的思想是数组是部门有序的，然后将无序的部分循环插入到已有序的序列中

如图：（从数据结构与算法中摘得）

![Center 1][]

2、时间复杂度：插入排序对随即顺序的序列的时间复杂度也为O(N^2)，但是对于基本有序的序列进行排序时间复杂度为O(N)

3、代码

/**
    * 插入排序升序
    * @param array
    */
    public static void insertSort(int [] array){
    for(int out=1;out<array.length;out++){
    int temp = array[out];//被标记的值或者说是当前需要插入的值
    int in = out;
    //如果轮循值大于被标记值则往后移
    while( in > 0 && temp < array[in - 1]){
    array[in] = array[in - 1]; 
    in -- ;
    }
    //将被标记值插入最终移出的空位置
    array[in] = temp;
    }
    }

[Center]: /images/20220731/d6a7946451914f21997efe8c01f26c7e.png
[Center 1]: /images/20220731/9e0e2552680a49a49fa37905f9c4266f.png