基础算法总结Java版
感觉自己的算法真的是菜，之前写过的也不能很麻溜的写出来，在此记录一下
排序算法
快排：主要就是分治思想，选取一个基准 x 然后一趟排序下来把所有小于 x 的放在其左边，大于 x 的放在其右边。只是要多加注意 = 的使用
我今天才发现一个方法就能完成，之前都是写一个主要的方法返回经过一次排序后的中间位置，再写另外一个方法去调用，本质都一样，只不过前一种更为简洁些，后一个比较容易理解。
/** 快排1 **/
public static int quick_sort(int []a, int low, int high){
int swap = a[low];
if(low < high){
while (low < high){
//注意这里和下一个循环条件一定至少有一个要是 >= 或者 <=
while (low < high && a[high] >= swap)
high--;
a[low] = a[high];
while (low < high && a[low] < swap)
low++;
a[high] = a[low];
}
a[low] = swap;
}
return low;
}
public static void quickSort(int []a, int low, int high){
if(low < high){
int mid = quick_sort(a, low, high);
quickSort(a,low,mid-1);
quickSort(a,mid+1,high);
}
}
/** 快排2 **/
public static void quickSort2(int a[], int low, int high){
int l = low;
int h = high;
if(l < h){
int swap = a[l];
while (l < h){
//注意这里和下一个循环条件一定至少有一个要是 >= 或者 <=
while (l < h && a[h] > swap){
h --;
}
a[l] = a[h];
while (l < h && a[l] <= swap){
l ++;
}
a[h] = a[l];
}
a[l] = swap;
quickSort2(a,low,l-1);
quickSort2(a,l+1,high);
}
}
选取第一个位置的数作为基准（swap），之后想象这个位置空出来了，需要从后往前找第一个小于 swap 的数，找到后（high位置处）放在 low 位置。然后此时想象 high 位置空了出来，需要从前往后找第一个大于 swap 的数，找到后（low位置处）放在 high 位置。持续这个过程，直到第一次排序结束，即 low = high。现在 low/high 位置左侧的数都是比 swap 小的，右侧都是大于或等于 swap 的数，所以最后再把 swap 放在这个位置，a[low] = swap;
有个需要注意的地方在 从后往前/从前往后 找寻 第一个小于/大于 swap 的数时的while 条件： while (low < high && a[high] >= swap) ，要求 low < high是防止越界，而后面一个 a[high] >= swap 我之前总忘记写等号，会发生死循环。这是个很严重的问题，不加（两个循环判断条件都不加） = ，如果后面有一个数和基准相等，会一直在这里循环。举个例子，排序数组 50,2,……,50第一个次排序 low 位置处是 50，high 位置处也是 50，这个循环会一直进行下去，总是在 50 与 50 互换。
给你一个例子随意感受一下：1,4,4,4,12,78,8,45,67,39,20,90,65,34,34,6,7,88,9,1,-3,-88,-2
查询算法
二分查找：二分查找很简单，不容易想出来的是它的一些变体
/** 二分查找 **/
public static int halfSearch(int a[] ,int targert){
int low = 0;
int high = a.length-1;
int mid = (low+high)/2;
while (low <= high){
if(a[mid] == targert){
return mid;
}
else if (a[mid] > targert){
high = mid - 1;
}
else {
low = mid + 1;
}
mid = (low+high)/2;
}
return -1;
}
/** 查找第一个等于 x 的位置 **/
public static int searchFirstEquelIndex(int []a, int target){
int low = 0;
int high = a.length - 1;
int mid = (low + high) >> 1;
while (low <= high){
if(a[mid] < target){
low = mid + 1;
}
else if(a[mid] >= target){
high = mid - 1;
}
mid = (low + high) >> 1;
}
if(low >= 0 && a[low]==target){
return low;
}
return -1;
}