1. 快排
- 思路：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- 变量：左值left，右值right，临时标志值key，目标数组number
- 步骤：一趟快速排序的算法是：
- 设置两个变量i、j，排序开始的时候：i=left，j=right；
- 以第一个数组元素作为关键数据，赋值给key，即key=A[left]；
- 在满足i<j的情况下，从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，接着从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，此时将A[i]和A[j]互换；
- 重复第3步，直到i=j；
第3步中，若没有发生交换直接进行到了i==j，则数组本身就已有序，结束循环即可。
- 代码：
static void quickSort(int left, int right) {
if (left > right)
return;
int i = left, j = right, key = number[left];
while (i != j) {
while (number[j] >= key && i < j)
j--;
while (number[i] <= key && i < j)
i++;
if (i < j) {
number[j] = number[j] ^ number[i];
number[i] = number[j] ^ number[i];
number[j] = number[j] ^ number[i];
}
}
number[left] = number[i];
number[i] = key;
quickSort(left, i - 1);
quickSort(i + 1, right);
}
2. 二分查找
- 思路：是将n个元素分成大致相等的两部分，去将a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x>a[n/2],则只要在数组a的右半部搜索x，否则，在数组a的左半部搜索。
- 变量： 目标findValue，中值middle ，目标数组sortedData
- 代码：
static int binaryChop(int[] sortedData, int findValue) {
int start = 0;
int end = sortedData.length - 1;
while (start <= end) {
// 中间位置
int middle = (start + end) >> 1; // 相当于(start+end)/2
// 中值
int middleValue = sortedData[middle];
if (findValue == middleValue) {
// 等于中值直接返回
return middle;
} else if (findValue < middleValue) {
// 小于中值时在中值前面找
end = middle - 1;
} else {
// 大于中值在中值后面找
start = middle + 1;
}
}
// 找不到
return -1;
}
to be continued...
