數(shù)據(jù)結(jié)構(gòu)和算法

數(shù)據(jù)結(jié)構(gòu)是計算機存儲，組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運行或存儲效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)；算法是指令的集合，是為解決特定問題而規(guī)定的一系列操作，可以簡潔而快速的得到預(yù)期的結(jié)果集。程序=數(shù)據(jù)結(jié)構(gòu)+算法

冒泡排序

冒泡大家都知道，在河水中的泡泡，水底剛冒出來的時候是比較小的，隨著慢慢向水面浮起會逐漸增大。

圖文描述

• 首先創(chuàng)建一個數(shù)組 int[] arr ={60,40,80,20,30}

• 然后進行冒泡排序如下圖：

  
  
  邏輯圖
  
  
  邏輯圖
• 計算的順序
  1.第一次循環(huán)：arr[0]和arr[1]，arr[1]和arr[2]，arr[2]和arr[3]，arr[3]和arr[4] 得到全部5位數(shù)中最大值
  2.第二次循環(huán)：arr[0]和arr[1]，arr[1]和arr[2]，arr[2]和arr[3] 得到剩下的4位數(shù)中最大的值
  3.第三次循環(huán)：arr[0]和arr[1]，arr[1]和arr[2] 得到剩下的3位數(shù)中最大的值
  4.第四次循環(huán)：arr[0]和arr[1] 得到剩下的2位數(shù)中最大的值

冒泡算法的運作規(guī)律如下：

• 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個的值。
• 最外層可以用個for循環(huán) ,循環(huán)4次 也就是（arr.lenght-1）次。
• 第1次循環(huán)i=0時判斷4次，第2次循環(huán)i=1時判斷3次，第3次循環(huán)i=2時判斷2次，第4循環(huán)i=3時判斷1次。arr.lenght-1=4，4-0=4,4-1=3,4-2=2,4-3=1，內(nèi)部循環(huán)判斷每次都是從下標(biāo)為0開始的，得到的規(guī)律內(nèi)部j初始化時為0，j<（arr.lenght-1-i）內(nèi)部判斷的次數(shù)。

實現(xiàn)代碼如下

import java.util.Arrays;
import java.util.Random;
public class MrpSort{

 public static void main(String[] args) {


    /**
     * 第一步首先創(chuàng)建一個數(shù)組 內(nèi)容是100以內(nèi)的隨機數(shù)字
     */
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }

    System.out.println("排序前數(shù)組="+ Arrays.toString(arr));

    for (int i = 0; i < arr.length-1; i++) {

        for(int j = 0; j < arr.length-1-i; j++){

            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }

        }

    }

    System.out.println("排序后數(shù)組="+Arrays.toString(arr));

  }
 }

結(jié)果

冒泡排序

選擇排序

選擇排序是每一次從待排序的數(shù)據(jù)元素中選出最小的一個元素，存放在序列的起始位置，直到全部待排序的數(shù)據(jù)元素排完。

圖文描述

• 首先創(chuàng)建一個數(shù)組 int[] arr ={60,40,80,20,30}

• 然后進行選擇排序如下圖：

  
  
  選擇排序
  
  
  選擇排序
• 計算順序
  1. 第一次循環(huán)：arr[0]和arr[1]，arr[0]和arr[2]，arr[0]和arr[3]，arr[0]和arr[4] 得到全部5位數(shù)中最小的值。
  2. 第二次循環(huán)：arr[1]和arr[2]，arr[1]和arr[3]，arr[1]和arr[4] 得到剩下四位數(shù)中最小的值。
  3. 第三次循環(huán)：arr[2]和arr[3]，arr[2]和arr[4] 得到剩下三位數(shù)中最小的值。
  4. 第四次循環(huán)：arr[3]和arr[4] 得到剩下兩位數(shù)中最小的值。

選擇排序計算規(guī)律如下：

• 從待排序序列中，用第一個數(shù)字和以下數(shù)字比較，如果arr[i]>arr[n] 則換值。
• 最外層用個for循環(huán)，循環(huán)4次 也就是（arr.lenght-1）次。
• 第1次循環(huán)i=0時判斷4次，第2次循環(huán)i=1時判斷3次，第3次循環(huán)i=2時判斷2次，第4循環(huán)i=3時判斷1次。arr.lenght-1=4，4-0=4,4-1=3,4-2=2,4-3=1，內(nèi)部循環(huán)判斷每次都是從下標(biāo)為i開始的，得到的規(guī)律內(nèi)部j初始化時為i+1，j<arr.lenght 內(nèi)部判斷的次數(shù)。

實現(xiàn)代碼如下

  import java.util.Arrays;
  import java.util.Random;

  public class selectSort {

    public static void main(String[] args){

    /**
     * 第一步首先創(chuàng)建一個數(shù)組 內(nèi)容是100以內(nèi)的隨機數(shù)字
     */
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }

    System.out.println("排序前數(shù)組="+ Arrays.toString(arr));

    for (int i = 0; i < arr.length-1; i++) {

        for (int j = i+1; j < arr.length; j++){

            if (arr[i] > arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }

    }

    System.out.println("排序后數(shù)組="+Arrays.toString(arr));
  }
}

結(jié)果

選擇排序

插入排序

直接插入排序基本思想是每一步將一個待排序的記錄，插入到前面已經(jīng)排好序的有序序列中去，直到插完所有元素為止。從下標(biāo)為1的元素開始選擇合適的位置插入，因為下標(biāo)為0的只有一個元素，默認(rèn)是有序的。

圖文描述

• 首先創(chuàng)建一個數(shù)組 int[] arr ={60,40,80,20,30}

• 然后進行選擇排序如下圖（借用大神一張圖）：

  
  
  插入排序

• 計算順序

  1. 第一次循環(huán)：arr[1]和arr[0] 得到前兩位最小的值。
  2. 第二次循環(huán)：arr[2]和arr[1]，arr[2]和arr[0] 得到前三位最小的值。
  3. 第三次循環(huán)：arr[3]和arr[2]，arr[3]和arr[1]，arr[3]和arr[0] 得到前四位最小的值。
  4. 第四次循環(huán)： arr[4]和arr[3]， arr[4]和arr[2]， arr[4]和arr[1]， arr[4]和arr[0] 得到五位最小的值。

選擇排序計算規(guī)律如下：

• 最外層用個for循環(huán)，循環(huán)4次，因為從下標(biāo)為1開始，所以i<arr.lenght。
• 拿到右邊待排序的值和左邊已排序最右邊的值依次比較，如果待排序的值小于已排序的值繼續(xù)對比。

實現(xiàn)代碼如下

import java.util.Arrays;
import java.util.Random;

public class InsertSort {

  public static void main(String[] args){

    /**
     * 第一步首先創(chuàng)建一個數(shù)組 內(nèi)容是100以內(nèi)的隨機數(shù)字
     */
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }

    System.out.println("排序前數(shù)組="+ Arrays.toString(arr));

    int j;
    for(int i = 1 ; i < arr.length ; i++){
        int tmp = arr[i];//記錄要插入的數(shù)據(jù)
        j = i;
        while(j > 0 && tmp < arr[j-1]){//從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
            arr[j] = arr[j-1];//向后挪動
            j--;
        }
        arr[j] = tmp;//存在比其小的數(shù)，插入
    }

    System.out.println("排序后數(shù)組="+Arrays.toString(arr));
  }

}

結(jié)果

插入排序

冒泡、選擇、插入排序 效率對比

分別用冒泡、選擇、插入排序，來實現(xiàn)同一個需求，分別看完成花費的時間。

實現(xiàn)代碼

 import java.util.Random;

/**
 * 冒泡、選擇、插入 排序?qū)Ρ? */
   public class CompareSort {

    public static void main(String[] args){

    /**
     * 冒泡排序
     */
    int[] arrayBub = getArray();
    long startTimeBub = System.currentTimeMillis();
    for (int i = 0; i < arrayBub.length-1; i++) {
        for(int j = 0; j < arrayBub.length-1-i; j++){
            if (arrayBub[j] > arrayBub[j+1]){
                int temp = arrayBub[j];
                arrayBub[j] = arrayBub[j+1];
                arrayBub[j+1] = temp;
            }
        }
    }
    long endTimeBub = System.currentTimeMillis();
    System.out.println("冒泡排序時間戳= "+(endTimeBub-startTimeBub));

    /**
     * 選擇排序
     */
    int[] arraySelect = getArray();
    long startTimeSelet = System.currentTimeMillis();
    for (int i = 0; i < arraySelect.length-1; i++) {
        for (int j = i+1; j < arraySelect.length; j++){
            if (arraySelect[i] > arraySelect[j]){
                int temp = arraySelect[i];
                arraySelect[i] = arraySelect[j];
                arraySelect[j] = temp;
            }
        }
    }
    long endTimeSelet = System.currentTimeMillis();
    System.out.println("選擇排序時間戳= "+(endTimeSelet-startTimeSelet));

    /**
     * 插入排序
     */
    int[] arrayInsert = getArray();
    long startTimeInset = System.currentTimeMillis();
    int j;
    for(int i = 1 ; i < arrayInsert.length ; i++){
        int tmp = arrayInsert[i];//記錄要插入的數(shù)據(jù)
        j = i;
        while(j > 0 && tmp < arrayInsert[j-1]){//從已經(jīng)排序的序列最右邊的開始比較，找到比其小的數(shù)
            arrayInsert[j] = arrayInsert[j-1];//向后挪動
            j--;
        }
        arrayInsert[j] = tmp;//存在比其小的數(shù)，插入
    }
    long endTimeInset = System.currentTimeMillis();
    System.out.println("插入排序時間戳= "+(endTimeInset-startTimeInset));

}

/**
 * 創(chuàng)建一個數(shù)組 內(nèi)容是一萬個1000以內(nèi)的隨機數(shù)字
 */
public static int[] getArray(){
    int[] arr = new int[10000];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(1000);
    }
    return arr;
}

}

結(jié)果

三種排序時間戳

• 最終結(jié)論顯示，插入排序的效率要高于選擇排序高于冒泡排序。