1.顺序查找。
按数组的顺序从前往后一直比较，直到找到目标值返回。
优点：对数组的结构没有特定的要求，算法简单。
缺点：当数组个数n较大时，效率低下。
时间复杂度：最大时间复杂度是O(n)，最小时间复杂度是O(1),平均时间复杂度是O(n/2).
<span style="white-space:pre"> </span>/**
* 顺序查找算法
*
* @param array
* 数组
* @param target
* 目标
* @return 找到，返回下标值；找不到返回0x80000000
*/
public int sequentialSearch(int[] array, int target) {
if (array == null) {
throw new NullPointerException("the array can't not be null!");
}
if (array.length <= 0) {
throw new IllegalArgumentException("the length of array is illgal!");
}
for (int index = 0; index < array.length - 1; index++) {
if (array[index] == target) {
return index;
}
}
return Integer.MIN_VALUE;
}
2.二分查找：
从数组的中间开始查找，若找到目标值则返回；若目标值比中间数小则递归查找前半部分；若目标值比中间数大则递归查找后半部分。
优点：比较次数较少，效率比较高
缺点：只适用于不经常变动有序数组
时间复杂度：O（log（n））
/**
* 二分查找算法
* @param array 有序数组
* @param target 目标数值
* @return 找到，返回下标值；找不到返回0x80000000
*/
public int binarySearch(int[] array, int target) {
if (array == null) {
throw new NullPointerException("the array can't not be null!");
}
if (array.length <= 0) {
throw new IllegalArgumentException("the length of array is illgal!");
}
int low = 0;
int high = array.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (target == array[middle]) {
return middle;
}
if (target > array[middle]) {
low = middle + 1;
} else {
high = middle - 1;
}
}
return Integer.MIN_VALUE;
}
排序方法：
1.插入排序：
将一个数据插入到已经排好序的有序数据中，在有序序列中选出合适的位置插入，从而得到一个新的、个数加一的有序数据。
优点：是稳定的排序方法。
缺点：算法适用于少量数据的排序
时间复杂度为O(n^2)。
<span style="white-space:pre"> </span>public int[] insertSort(int[] array) {
if (array == null) {
throw new NullPointerException("the array can't not be null!");
}
if (array.length <= 0) {
throw new IllegalArgumentException("the length of array is illgal!");
}
for (int i = 0; i < array.length - 1; i++) {
int index = halfFindIndex(array, array[i], i);
if (index != i) {
int temp = array[i];
for (int j = i; j > index; j--) {
array[j] = array[j - 1];
}
array[index] = temp;
}
}
return array;
}
private int halfFindIndex(int[] array, int target, int end) {
int low = 0;
int high = end;
int middle = 0;
while (low <= high) {
middle = (low + high) / 2;
if (target < array[middle]) {
low = middle + 1;
} else {
high = middle - 1;
}
}
if (target > array[middle]) {
middle++;
}
return middle;
}
2.冒泡排序
每次将相邻的两个数进行比较，如果想升序，则大数往后，反之亦然。
优点：算法简单,稳定算法
缺点：效率低下的排序方法，在数据规模很小时，可以采用；
时间复杂度:无序O(n^2)，有序o(1)
<span style="white-space:pre"> </span>public int[] bubbleSort(int[] array) {
if (array == null) {
throw new NullPointerException("the array can't not be null!");
}
if (array.length <= 0) {
throw new IllegalArgumentException("the length of array is illgal!");
}
int flag = array.length - 1;
while (flag > 0) {
int end = flag;
flag = 0;
for (int i = 0; i < end; i++) {
if (array[i] > array[i + 1]) {
int temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
flag = i;
}
}
}
return array;
}
3.归并排序
采用分治的思想，通过分割和合并，达到目的
优点：算法简单,稳定算法
平均时间复杂度：O(nlog2n)
空间复杂度：O(n) (用于存储有序子序列合并后有序序列)
/**
* 归并排序
*
* @param unSortArray
* @return
* @throws NullPointerException
* @throws IllegalArgumentException
*/
public int[] mergerSort(int[] unSortArray) throws NullPointerException,
IllegalArgumentException {
if (unSortArray == null) {
throw new NullPointerException("the array is null!");
}
if (unSortArray.length <= 0) {
throw new IllegalArgumentException("the size of array is illgal!");
}
int last = unSortArray.length - 1;
int[] temp = new int[unSortArray.length];
return merger(unSortArray, 0, last, temp);
}
/**
* 递归实现归并排序
*
* @param unSortArray
* 无序数组
* @param first
* 开始下标
* @param last
* 最后有效下标
*/
private int[] merger(int[] unSortArray, int first, int last, int[] temp) {
if (temp == null) {
return null;
}
if (first < last) {
int middle = (first + last) / 2;
// 左边
merger(unSortArray, first, middle, temp);
// 右边
merger(unSortArray, middle + 1, last, temp);
// 排序
mergerArray(unSortArray, first, middle, last, temp);
}
return unSortArray;
}
/**
* 将两个有序序列合并成一个有序序列
*
* @param array
* 一个无序序列
* @param first
* 开始的坐标
* @param last
* 最后的坐标
* @param temp
* 暂存数组
*/
private void mergerArray(int[] array, int first, int mid, int last,
int[] temp) {
int start = first;
int latterIndex = mid + 1;
int tempIndex = 0;
while (start <= mid && latterIndex <= last) {
// 比较将数放进暂存数组中
if (array[start] < array[latterIndex]) {
temp[tempIndex++] = array[start++];
} else {
temp[tempIndex++] = array[latterIndex++];
}
}
while (start <= mid) {
// 将middle以前的有序序列暂存到数组中
temp[tempIndex++] = array[start++];
}
while (latterIndex <= last) {
// 将middle以后的有序序列暂存到数组中
temp[tempIndex++] = array[latterIndex++];
}
for (int i = 0; i < tempIndex; i++) {
// 将暂存数组里的数复制到一开始的无序序列中
array[first + i] = temp[i];
}
}
4.快速排序
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
是不稳定的算法
快速排序时间复杂度下界为O(nlgn)，最坏情况为O(n^2)。在实际应用中，快速排序的平均时间复杂度为O(nlgn)
只要对快速排序做简单的操作，就能使时间复杂度总是O(nlgn):
1.对排序数据进行打乱；
2.随机挑选基准数.
额外空间O(log(n))
<span style="white-space:pre"> </span>public int[] quickSort(int[] unSortArray, int left, int right)
throws NullPointerException, IllegalArgumentException {
if (unSortArray == null) {
throw new NullPointerException("the array is null!");
}
if (unSortArray.length <= 0) {
throw new IllegalArgumentException("the size of array is illgal!");
}
if (left < right) {
int start = left;
int end = right;
// 选第一个为基准
int x = unSortArray[start];
while (start < end) {
while (start < end && x < unSortArray[end]) {
// 找到小于基准的数
end--;
}
if (start < end) {
// 交换位置
unSortArray[start] = unSortArray[end];
start++;
}
while (start < end && x > unSortArray[start]) {
// 找到大于基准的数
start++;
}
if (start < end) {
// 交换位置
unSortArray[end] = unSortArray[start];
end--;
}
}
unSortArray[start] = x;
quickSort(unSortArray, left, start - 1); // 递归调用
quickSort(unSortArray, start + 1, right);
}
return unSortArray;
}