01_數組排序

01.1_定義

把數組無序的元素通過交換移動等方式使數組或元素變成有序序列。

01.2_冒泡排序

數組中的元素兩兩比較大的元素往後放，經過一輪比較後，最大的元素會出現在最後面。

2020.7.30數組排序（1）01_數組排序

案例示範

package ArraryDemo1;

import com.sun.xml.internal.ws.api.model.wsdl.WSDLOutput;

import java.util.Arrays;

//冒泡排序
public class ArrayTest01 {
    public static void main(String[] args) {
        //定義一個數組
        int[] arr = {5, 10, 7, 4, 3};
        //抽取方法
        // chang(arr);
        for (int j = 0; j < arr.length - 1; j++) {
            for (int i = 0; i < arr.length - 1-j; i++) {
                if (arr[i] > arr[i + 1]) {
                    //互換位置
                    int x = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = x;
                }
            }
        }
        System.out.println(Arrays.toString(arr));//[3, 4, 5, 7, 10]
        System.out.println("--------------------------------------------");
    }
    //将分輪比較提取為方法
    private static void chang(int[] arr) {
        //進行第一輪排序
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                //互換位置
                int x = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = x;
            }
        }
        //輸出數組元素
        System.out.println(Arrays.toString(arr));//[5, 7, 4, 3, 10]
        System.out.println("---------------");
        //進行第二輪排序
        for (int i = 0; i < arr.length - 1 - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                //互換位置
                int x = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = x;
            }
        }
        //輸出數組元素
        System.out.println(Arrays.toString(arr));//[5, 4, 3, 7, 10]
        System.out.println("---------------");
        //進行第三輪排序
        for (int i = 0; i < arr.length - 1 - 1 - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                //互換位置
                int x = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = x;
            }
        }
        //輸出數組元素
        System.out.println(Arrays.toString(arr));//[4, 3, 5, 7, 10]
        System.out.println("-------------");
        //進行第三輪排序
        for (int i = 0; i < arr.length - 1 - 1 - 1 - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                //互換位置
                int x = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = x;
            }
        }
        //輸出數組元素
        System.out.println(Arrays.toString(arr));//[3, 4, 5, 7, 10]
    }
}

01.3_選擇排序

每次拿一個元素，跟後面剩餘的元素比較，挨個比較，小的往前方，最小的元素就會出現在最前面

2020.7.30數組排序（1）01_數組排序

案例示範

package ArraryDemo1;

import java.util.Arrays;

//選擇排序
public class ArrayTest02 {
    public static void main(String[] args) {
        //定義一個數組
        int[] arr={5,10,7,4,3};
        //chang(arr);
        //選擇排序
        for (int j = 0; j < arr.length; j++) {
            for (int i = 1+j; i < arr.length; i++) {
                if(arr[j]>arr[i]){
                    int y=arr[j];
                    arr[j]=arr[i];
                    arr[i]=y;
                }
            }
        }
        System.out.println(Arrays.toString(arr));//[3, 4, 5, 7, 10]
        System.out.println("============================================================");
    }

    private static void chang(int[] arr) {
        int x=0;
        for (int i = 1; i < arr.length; i++) {
            if(arr[x]>arr[i]){
                int y=arr[x];
                arr[x]=arr[i];
                arr[i]=y;
            }
        }
        System.out.println(Arrays.toString(arr));//[3, 10, 7, 5, 4]
        System.out.println("--------------------------------");
        //選擇排序第二輪,開始比較元素索引為1，比上一輪少比較一次
        x=1;
        for (int i = 2; i < arr.length; i++) {
            if(arr[x]>arr[i]){
                int y=arr[x];
                arr[x]=arr[i];
                arr[i]=y;
            }
        }
        System.out.println(Arrays.toString(arr));//[3, 4, 10, 7, 5]
        System.out.println("--------------------------------");
        //選擇排序第三輪,開始比較元素索引為2，比上一輪少比較一次
        x=2;
        for (int i = 3; i < arr.length; i++) {
            if(arr[x]>arr[i]){
                int y=arr[x];
                arr[x]=arr[i];
                arr[i]=y;
            }
        }
        System.out.println(Arrays.toString(arr));//[3, 4, 5, 10, 7]
        System.out.println("--------------------------------");
        //選擇排序第四輪,開始比較元素索引為3，比上一輪少比較一次
        x=3;
        for (int i = 4; i < arr.length; i++) {
            if(arr[x]>arr[i]){
                int y=arr[x];
                arr[x]=arr[i];
                arr[i]=y;
            }
        }
        System.out.println(Arrays.toString(arr));//[3, 4, 5, 7, 10]
        System.out.println("--------------------------------");
    }
}

01.4_直接插入排序

從第二個元素，每次那一個元素插入之前的序列中，使之仍保持有序

案例示範：

package ArraryDemo1;

import java.util.Arrays;

//直接插入排序：從第二個元素，每次拿一個後面元素插入之前的有序列中，使之仍保持有序
public class ArrayTest03 {
    public static void main(String[] args) {
        //[4,8,2,43,9,-8]
        //[]
        //
        int[] arr = {49, 38, 5, 97, 76, 13, 27, 20, 36, 58, 95};
        //外層循環定義輪次
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >0 ; j--) {
                if(arr[j]<arr[j-1]){
                    int x=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=x;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("=============================================");
        for (int k = 0; k < arr.length; k++) {
            int y=k;
            while(y>0&&arr[y]<arr[y-1]){
                int x=arr[y];
                arr[y]=arr[y-1];
                arr[y-1]=x;
            }
            y--;
        }
        System.out.println(Arrays.toString(arr));
    }
}

01.5_快速排序

分治法：比大小，再分區
從數組中取出一個數，作為基準數。
分區：将比這個數大或等于的數全放到他的右邊，小于他的數
全放到他的左邊。
再對左右區間重複第二步，直到各區間隻有一個數。

------------------------------思路
挖坑填數
将基準數挖出形成第一個坑。
由後向前找比他小的數，找到後挖出此數填到前一個坑中。
由前向後找比他大或等于的數，找到後也挖出此數填到前一個坑中。
再重複執行2，3兩步驟。

2020.7.30數組排序（1）01_數組排序

案例示範

對第一輪進行實作;

package ArraryDemo1;

import java.util.Arrays;

//快速排序
public class QuickScortTest {
    public static void main(String[] args) {
        //定義一個數組

        int[] arr = {5, 3, 9, 1, 6, 7, 2, 4, 0, 8};

        int i = 0;
        int j = arr.length - 1;
        //定義一個基準數
        int x = arr[0];
        //由後向前找比他小的數，找到後挖出此數填到前一個坑中。
        while(i<j){
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            //由前向後找比他大或等于的數，找到後也挖出此數填到前一個坑中。
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
            //把基準數鐵道最後一個坑中
            arr[i] = x;

            System.out.println(Arrays.toString(arr));
        }
        //一輪輸出
       /*   [0, 3, 5, 1, 6, 7, 2, 4, 9, 8]
            [0, 3, 4, 1, 5, 7, 2, 6, 9, 8]
            [0, 3, 4, 1, 2, 5, 7, 6, 9, 8]//第一輪最終結果*/

    }
}

整體實作，并封裝方法

package ArraryDemo1;

import java.util.Arrays;

public class QuicjkScortTest02 {
    public static void main(String[] args) {
        int[] arr={5,3,9,1,6,7,2,4,0,8};
        //調用方法
        QuicjkScortTest01.QuickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));//[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }
}
------------------------------------------------------------------------
package ArraryDemo1;

import java.util.Arrays;

//快速排序
public class QuicjkScortTest01 {

    public QuicjkScortTest01() {
    }

    //用遞歸進行實作,調用方法
    public static void QuickSort(int[] arr,int start,int end){
        if(start<end){
            //取出分區的索引
            int index=getIndex(arr,start,end);
            //對左分區進行遞歸
            QuickSort(arr,start,index-1);
            //對右分區進行遞歸
            QuickSort(arr,index+1,end);
        }

    }
    //封裝方法
    public static int getIndex(int[] arr,int start,int end){
        int i=start;
        int j=end;
        //定義一個基準數
        int x=arr[i];
        while(i<j){
            //由後向前找比他小的數，找到後挖出此數填到前一個坑中
            //隻要沒有找到比基準數小的就一直向前找，但是不能超出索引i
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];//将找到的數填在前一個坑中
                i++;
            }
            //由前向後找比他大或等于的數，找到後也挖出此數填到前一個坑中。
            while (i < j && arr[i] < x) {//隻要沒有找到比基準數大的就一直向後找，但是不能超出索引j
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];//将找到的數填在前一個坑中
                j--;
            }
           // System.out.println(Arrays.toString(arr));
        }
        //把基準數鐵道最後一個坑中
        arr[i] = x;
        return i;//傳回的是下一輪分區的索引
    }
}

2020.7.30數組排序（1）01_數組排序

01_數組排序

01.1_定義

01.2_冒泡排序

01.3_選擇排序

01.4_直接插入排序

01.5_快速排序

繼續閱讀

關于Gradle配置的小結

Java小案例——随機數猜測随機數猜測

nginx location中斜線的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method