冒泡排序
新手最先接觸到的排序演算法，對一個陣列進行遍歷，遍歷程序中進行比較，如果該位置的元素大于后一位置的元素，則將兩元素交換，
public static int[] bubbleSort(int[] a) {
for(int i = 0;i < a.length;i++) {
for(int j = 0; j < a.length-1-i;j++) {
if(a[j] > a[j+1]) {
int tmp = 0;
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
return a;
}
此演算法時間復雜度為O（n^2）；
注意點：外層回圈是保證每一個元素都要參與到冒泡中，內層回圈是保證每一個元素都要進行冒泡比較，當外層回圈每走一次，表示找到了一個最大的值，并且放在陣列的 a.length-i-1的位置上.
快速排序
首先介紹快速排序需要用到的工具：左指標、右指標、中間值，
用到的思想：遞回
取陣列中第一個元素作為中間值，然后左右指標分別跟中間值進行比較，小于中間值的放在左邊，大于中間值的放在右邊，當左右指標重合時，重合位置處的左邊數值全部比中間值小，右邊全部比中間值大，
這樣陣列就分成了兩個部分，再對這兩部分如法炮制，分別又生成了兩個陣列，依次遞回下去，遞回結束的條件是左指標大于或者等于右指標，
public static void quickSort(int[] a,int left,int right) {
if(left < right) {
int index = getIndex(a,left,right);
quickSort(a,left,index-1);
quickSort(a,index+1,right);
}
}
public static int getIndex(int[] a,int left,int right) {
int tmp = a[left];
while(left < right) {
//用while回圈，來判斷右指標對應的數是否大于tmp，是的話不用交換，直接移動右指標即可
while(left < right && a[right] >= tmp) {
right--;
}
//順序執行到這里，肯定是不滿足上面的while回圈條件，也就是右邊的數要小于中間值，此時需要把右邊的數換到左邊
a[left] = a[right];
while(left < right && a[left] <= tmp) {
left++;
}
a[right] = a[left];
}
//當回圈結束后，左右兩邊都分好大小，而指標重合位置處卻沒有值，需要把中間值放進來，
a[left] = tmp;
//回傳兩者相交處，
return left;
}
二分查找
當我們需要在已排好序的陣列中尋找到特定值時，可以使用二分查找，效率高，
所需要用到的工具：左指標、右指標、mid指標
思想：左指標右指標分別對應該元素所在陣列中的范圍邊界，初始化值為0和a.length；取中間值=（左指標+右指標+1）/2，這樣就得到兩個個區間（左指標，mid）（mid，右指標），判斷mid處的值與待確定位置值（S）的大小關系，若mid>S，說明S的位置應該在左區間，反之則在右區間，然后取對應的區間，再次如法炮制，遞回求解后得到正確結果，
public class BinarySearch {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a = new int[] {1,2,4,6,7,9,11,15};
System.out.println(BinarySearch.binarySearch(a, 0, a.length, 10));
}
static boolean isFind = false;
public static int binarySearch(int[] a,int left,int right,int search) {
while(!isFind)
{
if(left>=right) break;
int mid = (left+right+1)/2;
if(a[mid] > search) {
right = mid-1;
}else if(a[mid] < search) {
left = mid+1;
}else if(a[mid] == search) {
isFind = true;
left = mid;
}
}
if(!isFind) left = -1;
return left;
}
}
本文首發于java黑洞網，博客園同步更新
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/273114.html
標籤：Java