java 查找排序_查找与排序算法（Java实现）
1、二分查找算法
package other;
public class BinarySearch {
/*
* 循環實現二分查找算法arr 已排好序的數組x 需要查找的數-1 無法查到數據
*/
public static int binarySearch(int[] arr, int x) {
int low = 0;
int high = arr.length-1;
while(low <= high) {
int middle = (low + high)/2;
if(x == arr[middle]) {
return middle;
}else if(x
high = middle - 1;
}else {
low = middle + 1;
}
}
return -1;
}
//遞歸實現二分查找
public static int binarySearch(int[] dataset,int data,int beginIndex,int endIndex){
int midIndex = (beginIndex+endIndex)/2;
if(data dataset[endIndex]||beginIndex>endIndex){
return -1;
}
if(data
return binarySearch(dataset,data,beginIndex,midIndex-1);
}else if(data>dataset[midIndex]){
return binarySearch(dataset,data,midIndex+1,endIndex);
}else {
return midIndex;
}
}
public static void main(String[] args) {
int[] arr = { 6, 12, 33, 87, 90, 97, 108, 561 };
System.out.println("循環查找：" + (binarySearch(arr, 87) + 1));
System.out.println("遞歸查找"+binarySearch(arr,3,87,arr.length-1));
}
}
時間復雜度
比如：總共有n個元素，每次查找的區間大小就是n，n/2，n/4，…，n/2^k(接下來操作元素的剩余個數)，其中k就是循環的次數。
由于n/2^k取整后>=1，即令n/2^k=1，
可得k=log2n,(是以2為底，n的對數)，所以時間復雜度可以表示O()=O(logn)
2、歸并排序
歸并排序(Merge)是將兩個(或兩個以上)有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。 將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為2-路歸并。
歸并排序算法穩定，數組需要O(n)的額外空間，鏈表需要O(log(n))的額外空間，時間復雜度為O(nlog(n))，算法不是自適應的，不需要對數據的隨機讀取。
工作原理：
1、申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
2、設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3、比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
4、重復步驟3直到某一指針達到序列尾
5、將另一序列剩下的所有元素直接復制到合并序列尾
public class MergeSortTest {
public static void main(String[] args) {
int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };
print(data);
mergeSort(data);
System.out.println("排序后的數組：");
print(data);
}
public static void mergeSort(int[] data) {
sort(data, 0, data.length - 1);
}
public static void sort(int[] data, int left, int right) {
if (left >= right)
return;
// 找出中間索引
int center = (left + right) / 2;
// 對左邊數組進行遞歸
sort(data, left, center);
// 對右邊數組進行遞歸
sort(data, center + 1, right);
// 合并
merge(data, left, center, right);
print(data);
}
/**
* 將兩個數組進行歸并，歸并前面2個數組已有序，歸并后依然有序
*
* @param data
* 數組對象
* @param left
* 左數組的第一個元素的索引
* @param center
* 左數組的最后一個元素的索引，center+1是右數組第一個元素的索引
* @param right
* 右數組最后一個元素的索引
*/
public static void merge(int[] data, int left, int center, int right) {
// 臨時數組
int[] tmpArr = new int[data.length];
// 右數組第一個元素索引
int mid = center + 1;
// third 記錄臨時數組的索引
int third = left;
// 緩存左數組第一個元素的索引
int tmp = left;
while (left <= center && mid <= right) {
// 從兩個數組中取出最小的放入臨時數組
if (data[left] <= data[mid]) {
tmpArr[third++] = data[left++];
} else {
tmpArr[third++] = data[mid++];
}
}
// 剩余部分依次放入臨時數組(實際上兩個while只會執行其中一個)
while (mid <= right) {
tmpArr[third++] = data[mid++];
}
while (left <= center) {
tmpArr[third++] = data[left++];
}
// 將臨時數組中的內容拷貝回原數組中
// (原left-right范圍的內容被復制回原數組)
while (tmp <= right) {
data[tmp] = tmpArr[tmp++];
}
}
public static void print(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + "\t");
}
System.out.println();
}
}
static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, result, start1, end1);
merge_sort_recursive(arr, result, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
result[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
result[k++] = arr[start1++];
while (start2 <= end2)
result[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = result[k];
}
public static void merge_sort(int[] arr) {
int len = arr.length;
int[] result = new int[len];
merge_sort_recursive(arr, result, 0, len - 1);
}
3、快速排序
算法概述/思路
快速排序一般基于遞歸實現。其思路是這樣的：
1.選定一個合適的值(理想情況中值最好，但實現中一般使用數組第一個值),稱為“樞軸”(pivot)。
2.基于這個值，將數組分為兩部分，較小的分在左邊，較大的分在右邊。
3.可以肯定，如此一輪下來，這個樞軸的位置一定在最終位置上。
4.對兩個子數組分別重復上述過程，直到每個數組只有一個元素。
5.排序完成。
public static void quickSort(int[] arr){
qsort(arr, 0, arr.length-1);
}
private static void qsort(int[] arr, int low, int high){
if (low < high){
int pivot=partition(arr, low, high); //將數組分為兩部分
qsort(arr, low, pivot-1); //遞歸排序左子數組
qsort(arr, pivot+1, high); //遞歸排序右子數組
}
}
private static int partition(int[] arr, int low, int high){
int pivot = arr[low]; //樞軸記錄
while (low
while (low=pivot) --high;
arr[low]=arr[high]; //交換比樞軸小的記錄到左端
while (low
arr[high] = arr[low]; //交換比樞軸小的記錄到右端
}
//掃描完成，樞軸到位
arr[low] = pivot;
//返回的是樞軸的位置
return low;
}
算法性能/復雜度
可以看出，每一次調用partition()方法都需要掃描一遍數組長度(注意，在遞歸的時候這個長度并不是原數組的長度n，而是被分隔出來的小數組，即n*(2^(-i)))，其中i為調用深度。而在這一層同樣長度的數組有2^i個。那么，每層排序大約需要O(n)復雜度。而一個長度為n的數組，調用深度最多為log(n)層。二者相乘，得到快速排序的平均復雜度為O(n ㏒n)。
通常，快速排序被認為是在所有同數量級的排序方法中，平均性能最好。
從代碼中可以很容易地看出，快速排序單個棧的空間復雜度不高，每次調用partition方法時，其額外開銷只有O(1)。所以，最好情形下快速排序空間復雜度大約為O(㏒n)。
算法優化
上面這個快速排序算法可以說是最基本的快速排序，因為它并沒有考慮任何輸入數據。但是，我們很容易發現這個算法的缺陷：這就是在我們輸入數據基本有序甚至完全有序的時候，這算法退化為冒泡排序，不再是O(n㏒n)，而是O(n^2)了。
究其根源，在于我們的代碼實現中，每次只從數組第一個開始取。如果我們采用“三者取中”，即arr[low],arr[high],arr[(low+high)/2]三者的中值作為樞軸記錄，則可以大大提高快速排序在最壞情況下的性能。但是，我們仍然無法將它在數組有序情形下的性能提高到O(n)。還有一些方法可以不同程度地提高快速排序在最壞情況下的時間性能。
此外，快速排序需要一個遞歸棧，通常情況下這個棧不會很深，為log(n)級別。但是，如果每次劃分的兩個數組長度嚴重失衡，則為最壞情況，棧的深度將增加到O(n)。此時，由棧空間帶來的空間復雜度不可忽略。如果加上額外變量的開銷，這里甚至可能達到恐怖的O(n^2)空間復雜度。所以，快速排序的最差空間復雜度不是一個定值，甚至可能不在一個級別。
為了解決這個問題，我們可以在每次劃分后比較兩端的長度，并先對短的序列進行排序(目的是先結束這些棧以釋放空間)，可以將最大深度降回到O(㏒n)級別。
算法穩定性
快速排序并不是穩定的。這是因為我們無法保證相等的數據按順序被掃描到和按順序存放。
算法適用場景
快速排序在大多數情況下都是適用的，尤其在數據量大的時候性能優越性更加明顯。但是在必要的時候，需要考慮下優化以提高其在最壞情況下的性能。
快排的非遞歸實現
按照通常的理論，我們知道遞歸算法一般比較直觀自然，容易理解和書寫；而非遞歸算法一般更為晦澀，但是性能比遞歸算法更優良，因為其省去了大量的函數調用開銷。快速排序肯定有非遞歸實現的版本，例如這篇博客。有趣的是，這位作者認為快速排序的非遞歸實現比遞歸還要慢，并做出了分析。而下面的這位博主則寫了另一篇博文，證明“非遞歸算法總要比響應(應為"相應"--本博作者注)的遞歸算法速度快”，并認為前面的現象是由于Windows 下的STL效率比較低。
快速排序的Java非遞歸實現當然有，通常都是用自己實現的棧來模擬遞歸操作(實際上，前面兩位使用C++的同學也是如此做的)。但是我并不認為它們比遞歸的方式有極大的性能提升，反而丟失了可讀性，晦澀難懂。因此，我個人不提倡使用非遞歸方式。
4、動態規劃
動態規劃其實和分治策略是類似的，也是將一個原問題分解為若干個規模較小的子問題，遞歸的求解這些子問題，然后合并子問題的解得到原問題的解。區別在于這些子問題會有重疊，一個子問題在求解后，可能會再次求解，于是我們想到將這些子問題的解存儲起來，當下次再次求解這個子問題時，直接拿過來就是。其實就是說，動態規劃所解決的問題是分治策略所解決問題的一個子集，只是這個子集更適合用動態規劃來解決從而得到更小的運行時間。即用動態規劃能解決的問題分治策略肯定能解決，只是運行時間長了。因此，分治策略一般用來解決子問題相互對立的問題，稱為標準分治，而動態規劃用來解決子問題重疊的問題。
動態規劃一般由兩種方法來實現，一種為自頂向下的備忘錄方式，用遞歸實現，一種為自底向上的方式，用迭代實現。
5、堆排序
堆(二叉堆)可以視為一棵完全的二叉樹，完全二叉樹的一個“優秀”的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數組來表示(普通的一般的二叉樹通常用鏈表作為基本容器表示)，每一個結點對應數組中的一個元素。
如下圖，是一個堆和數組的相互關系
堆和數組的相互關系
對于給定的某個結點的下標 i，可以很容易的計算出這個結點的父結點、孩子結點的下標：
Parent(i) = floor(i/2)，i 的父節點下標
Left(i) = 2i，i 的左子節點下標
Right(i) = 2i + 1，i 的右子節點下標
package com.genesis.arithmetic;
import java.util.Arrays;
public class HeapSort {
private int[] arr;
public HeapSort(int[] arr){
this.arr = arr;
}
/**
* 堆排序的主要入口方法，共兩步。
*/
public void sort(){
/*
* 第一步：將數組堆化
* beginIndex = 第一個非葉子節點。
* 從第一個非葉子節點開始即可。無需從最后一個葉子節點開始。
* 葉子節點可以看作已符合堆要求的節點，根節點就是它自己且自己以下值為最大。
*/
int len = arr.length - 1;
int beginIndex = (len - 1) >> 1;
for(int i = beginIndex; i >= 0; i--){
maxHeapify(i, len);
}
/*
* 第二步：對堆化數據排序
* 每次都是移出最頂層的根節點A[0]，與最尾部節點位置調換，同時遍歷長度 - 1。
* 然后從新整理被換到根節點的末尾元素，使其符合堆的特性。
* 直至未排序的堆長度為 0。
*/
for(int i = len; i > 0; i--){
swap(0, i);
maxHeapify(0, i - 1);
}
}
private void swap(int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 調整索引為 index 處的數據，使其符合堆的特性。
*
* @param index 需要堆化處理的數據的索引
* @param len 未排序的堆(數組)的長度
*/
private void maxHeapify(int index,int len){
int li = (index << 1) + 1; // 左子節點索引
int ri = li + 1; // 右子節點索引
int cMax = li; // 子節點值最大索引，默認左子節點。
if(li > len) return; // 左子節點索引超出計算范圍，直接返回。
if(ri <= len && arr[ri] > arr[li]) // 先判斷左右子節點，哪個較大。
cMax = ri;
if(arr[cMax] > arr[index]){
swap(cMax, index); // 如果父節點被子節點調換，
maxHeapify(cMax, len); // 則需要繼續判斷換下后的父節點是否符合堆的特性。
}
}
/**
* 測試用例
*
* 輸出：
* [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
*/
public static void main(String[] args) {
// int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
int[] arr = new int[]{16, 7, 3, 20, 17, 8};
new HeapSort(arr).sort();
System.out.println(Arrays.toString(arr));
}
}
總結
以上是生活随笔為你收集整理的java 查找排序_查找与排序算法（Java实现）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： rust(43)-rust语言特点与版本
- 下一篇： python3精要(5)-python表