一. 數(shù)組排序

1. 簡介

Java中的數(shù)組是一種數(shù)據(jù)集合，里面可以存儲若干數(shù)據(jù)元素。有時(shí)我們需要對這些數(shù)據(jù)元素進(jìn)行排序，找出數(shù)組中的最大值、最小值，或者是按降序或升序?qū)?shù)組進(jìn)行排列，這些需求都需要我們能夠?qū)?shù)組進(jìn)行排序。但我們要注意，對數(shù)組排序會修改數(shù)組本身，即數(shù)組里元素的內(nèi)存指向會發(fā)生改變。

對數(shù)組進(jìn)行排序是程序中很常見的需求。如果我們想要實(shí)現(xiàn)數(shù)組排序，可以利用數(shù)據(jù)結(jié)構(gòu)中的某些排序算法來進(jìn)行實(shí)現(xiàn)，比如著名的冒泡排序、選擇排序等，當(dāng)然也可以利用Java自帶的Arrays.sort()方法來實(shí)現(xiàn)。接下來就針對這幾種實(shí)現(xiàn)方案，給大家設(shè)計(jì)幾個實(shí)現(xiàn)案例。

2. 冒泡排序(重點(diǎn))

2.1 簡介

冒泡排序的核心實(shí)現(xiàn)思路，就是把數(shù)據(jù)元素按照從下到上，兩兩進(jìn)行比較。所以冒泡排序的特點(diǎn)是，每一輪循環(huán)后，最大的一個數(shù)被交換到末尾。因此，下一輪循環(huán)可以“刨除”最后的數(shù)，每一輪循環(huán)都比上一輪循環(huán)的結(jié)束位置靠前一位。冒泡排序整體可以分為兩種情況，即升序排列和降序排列。

升序排列的實(shí)現(xiàn)思想：

將數(shù)組中相鄰的兩個數(shù)據(jù)元素進(jìn)行比較，如果前面一個元素比后面的大，就把兩者交換位置(一輪比較)；

然后將上面的操作進(jìn)行循環(huán)(比較n-1輪)。

排列過程如下圖所示：

降序排列的實(shí)現(xiàn)思想：

將數(shù)組中相鄰的兩個數(shù)據(jù)元素進(jìn)行比較，如果前面一個元素比后面的小，就把兩者交換位置(一輪比較)；

然后將上面的操作進(jìn)行循環(huán)(比較n-1輪)。

2.2 基本實(shí)現(xiàn)

大家要注意，面試時(shí)經(jīng)常會讓我們手寫冒泡排序和選擇排序等算法，你必須牢牢地記住相關(guān)的代碼實(shí)現(xiàn)哦。

/**
 * @author
 */
public class Demo09 {
    public static void main(String[] args) {
	// 冒泡排序--基本實(shí)現(xiàn)
	//待排序的數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	//控制需要比較幾輪
	for (int i = 0; i < arr.length; i++) {
            //控制每一輪的比較次數(shù)
            for (int j = 0; j < arr.length - 1; j++) {
            //如果前面的比后面的數(shù)字大，則兩者就進(jìn)行交換
		if (arr[j] > arr[j + 1]) {
                    //兩數(shù)交換，需要一個“第三方”，好比兩杯水互換，需要第三個杯子。
                    //交換兩個變量的值，必須借助一個臨時(shí)變量。
                    //定義一個新的臨時(shí)變量，將數(shù)組中的前面的元素先賦值給臨時(shí)變量
                    int temp = arr[j];
                    //后面的值賦值到前面的位置上
                    arr[j] = arr[j + 1];
                    //再將臨時(shí)變量的值賦值到后面的位置上
                    arr[j + 1] = temp;
		}
            }
	}
	//遍歷排序后的數(shù)組
	for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
	}
    }
}

這種實(shí)現(xiàn)方式比較容易理解，但并不是最優(yōu)的實(shí)現(xiàn)方案，因?yàn)檫@種方案需要比較的次數(shù)較多。我們可以進(jìn)一步對該方案進(jìn)行優(yōu)化，將比較的次數(shù)降下來，請繼續(xù)往下看。

2.3 優(yōu)化次數(shù)

在本案例中，會對比較次數(shù)進(jìn)行優(yōu)化。

/**
 * @author 
 */
public class Demo10 {
    public static void main(String[] args) {
	// 冒泡排序--優(yōu)化比較次數(shù)
	// 待排序數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	for(int j = 0; j < arr.length; j++) {//控制輪數(shù)
	    for(int i = 0; i < arr.length - 1 - j; i++) {//控制每一輪的次數(shù)
	        if(arr[i] > arr[i+1]) {
	            int temp = arr[i];
	            arr[i] = arr[i+1];
	            arr[i+1] = temp;
	        }
	    }
	}
        //遍歷排序后的數(shù)組
	for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
	}
    }
}

本案例同樣也不是最優(yōu)的實(shí)現(xiàn)方案，我們也可以對該實(shí)現(xiàn)方案進(jìn)行優(yōu)化。

2.4 優(yōu)化輪數(shù)

在本案例中，會對比較的輪數(shù)進(jìn)行優(yōu)化。

/**
 * @author
 */
public class Demo11 {
    public static void main(String[] args) {
	// 冒泡排序--優(yōu)化比較輪數(shù)
	// 待排序數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	for (int j = 0; j < arr.length - 1; j++) { //輪數(shù)
	    //假設(shè)這一輪已經(jīng)拍好序，設(shè)置一個標(biāo)簽進(jìn)行記錄
	    boolean flag = true;
	    for (int i = 0; i < arr.length - 1 - j; i++) {//每一輪比較的次數(shù)
	        if(arr[i] > arr[i+1]) {
	            //更改是否比較過的標(biāo)簽
	            flag = false;
	            int temp = arr[i];
	            arr[i] = arr[i+1];
	            arr[i+1] = temp;
	        }
	    }
	    //如果本輪已排序好，則直接跳過，避免沒必要的比較。
	    if(flag) {
	        break;
	    }
	}
	//遍歷排序后的數(shù)組
	for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
	}
    }
}

這種實(shí)現(xiàn)方案，可以說是三種方案中最優(yōu)的一種，但對初學(xué)者來說，理解起來確實(shí)不容易。當(dāng)然，在我們的線下課程中，我們的講師會對實(shí)現(xiàn)的每一個步驟詳細(xì)講解，不用怕自己理解不了。

3. 選擇排序(重點(diǎn))

3.1 簡介

選擇排序的核心實(shí)現(xiàn)思路，是隨機(jī)確定一個標(biāo)志位(一般為第一個數(shù)字)作為最小數(shù)，然后向后 遍歷 ，找到比標(biāo)志位更小的數(shù)字后，便與標(biāo)志位互換位置，并更新最小數(shù)。選擇排序同樣可以進(jìn)行升序或降序排列。

選擇排序升序思路：

將當(dāng)前位置上的數(shù)，與它后面的每個數(shù)進(jìn)行比較，選擇出最小的那個數(shù)，交換到當(dāng)前位置；

循環(huán)選擇當(dāng)前位置上的數(shù)。

選擇排序降序思路：

將當(dāng)前位置上的數(shù)，與它后面的每個數(shù)進(jìn)行比較，選擇出最大的那個數(shù)，交換到當(dāng)前位置；

循環(huán)選擇當(dāng)前位置上的數(shù)。

3.2 實(shí)現(xiàn)案例

以下是以升序的方式實(shí)現(xiàn)的選擇排序代碼，供大家參考。

/**
 * @author
 */
public class Demo12 {
    public static void main(String[] args) {
	// 選擇排序
	// 待排序的數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	for (int j = 0; j < arr.length-1; j++) {
	    //選擇下標(biāo)為0的位置
	    int min = j;
	    //將當(dāng)前這個數(shù)與后面的每個數(shù)進(jìn)行比較
	    for (int i = j+1; i < arr.length; i++) {
	        //如果當(dāng)前數(shù)字小于標(biāo)記的最小值，則將當(dāng)前數(shù)字標(biāo)記為最小值
	        if(arr[min] > arr[i]) {
	            min = i;
	        }
	    }
	    //如果當(dāng)前數(shù)字不是最小的，則進(jìn)行交換
	    if(min != j) {
	        int temp = arr[j];
	        arr[j] = arr[min];
	        arr[min] = temp;
	    }
	}
        //遍歷排序后的數(shù)組
        for(int i=0;i<arr.length;i++) {
            System.out.print(arr[i]+"\t");
        }
    }
}

4. Arrays.sort方法

以上兩種排序算法，實(shí)現(xiàn)起來是比較復(fù)雜的，但在面試時(shí)，基本上都要求我們能夠手寫出冒泡排序和選擇排序，大家一定要把代碼看懂哦。但如果我們想快速實(shí)現(xiàn)排序，其實(shí)可以使用Java自帶的API方法進(jìn)行實(shí)現(xiàn)，這個會更簡單。

4.1 簡介

Arrays工具類主要用于對數(shù)組進(jìn)行排序、查找、填充、比較等的操作，該類存在于java.util包下，所以我們使用的第一步就是要先進(jìn)行導(dǎo)包: import java.util.Arrays;

其中Arrays.sort()是Arrays類中的一個靜態(tài)方法，用于對數(shù)組進(jìn)行排序，我們可以直接調(diào)用。該方法有如下幾種重載形式：

• sort(T[] a) ：對指定T型數(shù)組按數(shù)字升序排序；
• sort(T[] a, int formIndex, int toIndex) ：對指定T型數(shù)組中 [formIndex,toIndex) 數(shù)據(jù)按數(shù)字升序排序；
• sort(T[] a, Comparator<? supre T> c) : 依據(jù)比較器對T型數(shù)組進(jìn)行排序；
• sort(T[] a, int formIndex, int toIndex, Comparator<? supre T> c) : 依據(jù)比較器產(chǎn)生的順序?qū)型數(shù)組中的 [formIndex,toIndex) 進(jìn)行排序。

4.2 實(shí)現(xiàn)案例

接下來再給大家設(shè)計(jì)一個利用Arrays.sort方法實(shí)現(xiàn)的排序案例。

/**
 * @author 
 */
public class Demo13 {
    public static void main(String[] args) {
	// 選擇排序
	//遍歷排序后的數(shù)組
	String[] names = { "cxk", "rose", "lihua", "lilei", "zhaosi" };
	//直接利用Arrays類提供的數(shù)組排序的方法，內(nèi)部是基于“快速排序”實(shí)現(xiàn)的。
	Arrays.sort(names);
	for (int i = 0; i < names.length; i++) {
            System.out.print(names[i] + "\t");
	}
    }
}

二. 二分查找法

1. 簡介

我們對數(shù)組除了可以進(jìn)行排序之外，還能對數(shù)組中的元素進(jìn)行查找，其中一個比較經(jīng)典的方案是利用二分查找法，也叫做折半查找法進(jìn)行實(shí)現(xiàn)，可以縮小查找范圍，提高查找效率。

二分查找是一種效率較高的查找方法，要求數(shù)據(jù)表須采用順序存儲結(jié)構(gòu)，且數(shù)組是有序(升序或者降序)的。核心思路就是將待查找的元素與中間下標(biāo)對應(yīng)的元素進(jìn)行比較，如果大于中間下標(biāo)對應(yīng)的元素，則去右半部分查找，否則就去左半部分進(jìn)行查找?；緦?shí)現(xiàn)流程如下：

• 首先，我們假設(shè)數(shù)組中的元素是按升序排列的；
• 然后將數(shù)組中間位置記錄的 關(guān)鍵字 與查找關(guān)鍵字進(jìn)行比較，如果兩者相等，則查找成功；
• 否則就利用中間的位置 記錄， 將數(shù)組分成前、后兩個子部分。如果中間位置記錄的關(guān)鍵字大于查找關(guān)鍵字，則進(jìn)一步查找前一子部分，否則進(jìn)一步查找后一子部分；
• 重復(fù)以上過程，直到找到滿足條件的 記錄為止 ?；蛑钡阶硬糠植淮嬖跒橹?，此時(shí)查找不成功。

2. 實(shí)現(xiàn)案例

然后就按照上述思路，給大家設(shè)計(jì)了如下案例，大家可以對照練習(xí)，好好琢磨該案例。

/**
 * @author 
 */
public class Demo14 {
    public static void main(String[] args) {
	// 二分查找法--折半查找法
	// 遍歷排序后的數(shù)組
	int[] arr = { 1, 3, 46, 22, 11 };
	int index = search(arr,46);
	System.out.println("46所在的索引位置="+index);
    }
    //定義一個方法，實(shí)現(xiàn)二分查找
    public static int search(int[] arr,int num) {
	//1. 獲取最小、大值的下標(biāo)
	int min = 0;
	int max = arr.length -1;
	while(min <= max) {
	    //2. 獲取中間值的下標(biāo)
	    int middle = (min + max) / 2;
	    //3. 將要查找的數(shù)字與中間值做比較
	    if(num > arr[middle]) {
	        min = middle +1;
	    }else if(num < arr[middle]) {
	        max = middle -1;
	    }else {
	        return middle;
	    }
        }
	return -1;
    }
}

三. 結(jié)語

至此，就把一維數(shù)組的內(nèi)容給大家介紹完畢了，現(xiàn)在你知道數(shù)組有什么作用了嗎？今日重點(diǎn)：

• 常用的排序算法有冒泡排序、插入排序和快速排序等；
• 冒泡排序使用兩層for循環(huán)實(shí)現(xiàn)排序；
• 交換兩個變量的值需要借助一個臨時(shí)變量。
• 可以直接使用Java標(biāo)準(zhǔn)庫提供的Arrays.sort()進(jìn)行排序；
• 對數(shù)組排序會直接修改數(shù)組本身。

對于數(shù)組，我們要掌握其基本用法，明白數(shù)組的擴(kuò)容原理，并掌握數(shù)組的排序算法。

以上就是詳解Java數(shù)組的排序算法與二分查找法的詳細(xì)內(nèi)容，更多關(guān)于Java數(shù)組排序算法與二分查找法的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論