java二分排序

A. java二分查找

//*******二分查找，都注釋了，復制所有代碼，保存成QuickSortApp.java*************//
class ArrayIns
{
private long theArray[];
private int nElems;
//--------------------
public ArrayIns(int max){ //構造方法，初始化成員屬性。
theArray = new long[max];
nElems = 0;
}
//-----------------------
public void insert(long value){ //insert方法用於給數組賦值，並用nElems記錄數組元素的個數。
theArray[nElems] = value;
nElems++;
}
//----------------------------
public void display(){ //display方法用於顯示數組的所有元素到控制台。
System.out.println("A= ");
for(int j=0;j<nElems;j++)
System.out.print(theArray[j]+" ");
System.out.println("");
}
//------------------------------
public void quickSort(){ //ArrayIns對象調用quickSort方法可以為其成員屬性theArray數組中的元素排序（從小到大）
recQuickSort(0,nElems-1); //調用recQuickSort方法開始排序，初始范圍從第一個到最後一個開始。
}
//-------------------------------
private void recQuickSort(int left,int right){ //recQuickSort方法進行數組元素的排序。left,right表示排序的范圍.
if(right-left <= 0)
return; //如果right小於left,則第歸返回。此處是第歸的出口。
else {
long pivot = theArray[right]; //每次把排序范圍中的最後一個數作為排序時的參照數。
int partition = partitionIt(left,right,pivot); //調用prititionIt方法，參數列表中指明排序的范圍和參照數，並將方法的返回值賦給pritition變數(用來指明下一次排序時的范圍。)
//System.out.print(" "+1); //數字1代表第一次第歸的調用。
recQuickSort(left,partition-1); //第歸調用本方法，排序右范圍由partition-1來決定。
//System.out.print(" "+2); //數字2代表第二次第歸的調用。
recQuickSort(partition+1,right); //第歸調用本方法，排序左范圍由partition-1來決定。
}
}
//-----------------------------------
private int partitionIt(int left,int right,long pivot){ //partitionIt方法完成left和right范圍內元素間排序的具體過程。
int leftPtr = left-1; //leftPrt表示左標識位，從left-1開始。
int rightPtr = right; //rightPrt表示右表識位，到right。 while(true){//永真循環。
while(theArray[++leftPtr] < pivot); // 空循環，從leftPrt開始往rightPrt方向開始找一個比pivot大的數,用leftPtr記錄元素的位置。
while(rightPtr>0 && theArray[--rightPtr]>pivot);//空循環，從rightPrt往leftPrt方向開始找一個比pivot小的數，用rightPrt記錄元素的位置,並且rightPtr>0會保證不會數組越界。
if(leftPtr >= rightPtr) //永真循環的出口，表示本次排序結束。
break;//跳出循環。
else
swap(leftPtr,rightPtr);//將leftPtr和rightPtr所在位置的元素進行交換。
}
swap(leftPtr,right); //調用swap方法。
return leftPtr; //將leftPtr返回到本方法被調用的位置。用來指明下一次排序時的范圍.
}
//---------------------------------------------
private void swap(int dex1,int dex2){ //swap方法用來將數組中的兩個元素進行交換，dex1和dex2分別表示兩個數組元素的位置。
long temp = theArray[dex1]; //temp變數作為兩個數組元素交換時的臨時中轉變數。
theArray[dex1] = theArray[dex2];
theArray[dex2] = temp;
}
}//////////////////////////////////////////////////////////////////////////////////////class QuickSortApp
{
public static void main(String[] args)
{
int maxSize = 10; //定義變數maxSize，並賦初值10.
ArrayIns arr;
arr = new ArrayIns(maxSize);//創建ArrayIns類的對象arr for(int j=0;j<maxSize;j++){
long n = (int)(java.lang.Math.random()*99);//產生隨機數。
arr.insert(n); //用insert方法為arr中的成員數組變數賦值。
}
arr.display(); //用display方法顯示arr中成員變數數組中的所有元素。
arr.quickSort(); //用quickSort方法為arr成員變數數組中的元素按從小到大排序。
arr.display(); //顯示。
}
}

B. 用Java語言編寫對整型數組進行二分查找的程序。

public class BinarySearchDemo {

public static void main(String[] args) {
int[] a = new int[]{1,5,7,9,11,18,23,48,69};
int point = new BinarySearchDemo().binarySearch(a, 23);

if(point == -1)
System.out.println("在數組中未查找到數23");
else
System.out.println("數字23是數組中第 " + (point + 1) + " 位數");

}

/**
* 二分法查找一個整數在整型數組中的位置
*
* 演算法思路：首先得到數組a的最小值和最大值的下標，分別是：low和high，接著求出值位於數組中間那個數的下標middle
* 然後再將這個middle對應的數組中的數和待查找的數num進行比較，如果相等，則表示已查找到，如果num < a[middle]
* 則說明num位於a[low]和a[middle]之間，於是將a[middle - 1]設為較大值，繼續求出此時對應的a[middle]，
* 再進行比較，其他情況可依次類推。一直到low=high，如果此時還沒有在數組a中查找到，則說明該數組a中沒有值num，返回-1
*
* @param a 給定的整型數組
* @param num 待查找的數 num
*
* @return 返回整數num在數組a中的位置下標，如果未查找到則返回-1
* */
public int binarySearch(int[] a,int num){
int low = 0;
int high = a.length - 1;

while(low <= high){
int middle = (low + high) / 2;
if(num == a[middle])
return middle;
else if(num < a[middle])
high = middle - 1;
else
low = middle + 1;
}

return -1;
}

}

程序基本上就是這樣了，其中注釋中有詳細的解釋說明

C. java二分法查找的遞歸演算法怎麼實現

什麼是二分查找？

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。

過程

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));

System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：

總結：

遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

D. jave二分演算法

import java.util.ArrayList;
import java.util.Random;

public class Test {
public static void main(String[] args) {
ArrayList<Integer> list=new ArrayList<Integer>(50);//創建一個容量50的ArrayList
Random r=new Random(47);
for(int i=0;i<50;i++){
list.add(r.nextInt(200));//添加50個200以內的隨機數
}
BinSort(list);//二分插入排序
System.out.println(list);//謹祥唯輸出list的內容
}
public static void BinSort(ArrayList<Integer> list){//考慮到有大宴首量的隨機訪祥培問，用ArrayList較快
int left, right, mid, temp;
for (int i = 1; i < list.size(); i++)
{
left = 0;
right = i - 1;
temp = list.get(i);
while (left <= right)
{
mid = (left + right)/2;
if (temp < list.get(mid)) //升序
right = mid - 1;
else
left = mid + 1;
}
for (int j = i - 1; j >= left; j--)
list.set(j + 1, list.get(j));
list.set(left, temp);
}
}
}

E. 關於java的binarysearch()方法

Java中的binarySearch方法是一種用於在有序數組中查找特定元素的演算法。其方法主要基於二分查找法實現，能快速地在有序數組中定位指定元素的位置。下面是具體的方法和解釋：

Java中的binarySearch方法是基於二分查找法的實現，用於在有序數組中查找特定元素。此方法返回的是指定元素在數組中的索引值，若不存在則返回負值。同時，使用該方法需要注意數組必須是有序的。

具體解釋：

基本介紹與工作原理

Java的binarySearch方法是數組工具類java.util.Arrays中的一個方法。該方法基於二分查找演算法實現，適用於已排序的數組。二分查找演算法的核心思想是不斷縮小搜索范圍，每次將搜索范圍縮小一半，直到找到目標元素或搜索范圍為空。這種方法的時間復雜度為O，相對於線性查找的O，在處理大規模數據時效率更高。

方法參數與返回值

binarySearch方法接受三個參數：待搜索的數組、待搜索元素的起始位置和結束位置。它會返回目標元素在數組中的位置索引，如果數組中沒有該元素，則返回負值。插入點的定義是如果插入元素會導致數組保持有序的最小索引位置。所以如果沒有找到目標元素，該方法將指示我們如何將元素添加到數組中保持其有序性。

使用注意事項

使用binarySearch方法時，必須確保數組是有序的。如果數組未排序，結果將不可預測。此外，對於大型數組，該方法非常高效；但對於小型數組，可能不如簡單的線性搜索來得直觀和快速。在實際應用中，應根據具體情況選擇使用哪種搜索方法。同時，由於該方法涉及復雜的演算法邏輯，開發者在使用時需要有相應的編程基礎和演算法知識。

總結來說，Java中的binarySearch方法是一種高效的搜索演算法，適用於在已排序的數組中查找特定元素。它的核心思想是二分查找法，能夠在逐步縮小搜索范圍的同時快速定位目標元素的位置。

F. java中對一個list用shuffle後，再用collection.binarySearch法找其中的元素，為啥下標會出現負值啊

在Java中使用shuffle方法對一個列表進行洗牌後，列表中的元素將變得無序。此時，如果你嘗試使用Collections的binarySearch方法進行二分查找，由於列表已不再有序，二分查找演算法將無法正常工作。

二分查找演算法要求在查找前列表是有序的，它通過比較目標值與中間元素來決定搜索方向，從而將搜索范圍縮小一半。若列表是無序的，二分查找將無法根據中間元素進行有效判斷，導致結果不可靠。因此，即使返回了某個下標，也不能保證該下標對應的元素就是你所尋找的目標。

當binarySearch方法在無序列表中查找元素時，它會返回一個負值，這個負值實際上是負的插入點。具體來說，返回值是-(插入點+1)，而插入點是指在查找過程中，如果在列表中插入目標元素，它應該插入的位置。這表明目標元素並不在列表中，或者插入點的位置意味著目標元素應該位於列表中的某個位置。

例如，如果你在一個無序的列表中查找某個元素，binarySearch方法可能返回-4，這意味著如果要將該元素插入到列表中，它應該插入在列表的第4個位置之前。實際上，這個返回值表示的是目標元素不在列表中，或者列表中的元素不滿足二分查找的有序條件。

所以，當使用shuffle方法對列表進行洗牌後，再用binarySearch方法查找元素時，出現負值下標是正常的，這表明列表已不再有序，二分查找無法正確執行，結果自然不可信。為了獲得正確的查找結果，你需要先對列表進行排序。