查找和排序算法是算法的入门知识，其经典思想可以用于很多算法当中。因为其实现代码较短，应用较常见。
一. 排序
常见的排序方式有：冒泡排序、选择排序、插入排序、快速排序。
1. 冒泡排序
特点： 效率低，实现简单
冒泡排序是最简单的排序之一了，其大体思想就是通过与相邻元素的比较和交换来把小的数交换到最前面。这个过程类似于水泡向上升一样，因此而得名。举个栗子，对8, 5, 3, 2, 4这个无序序列进行冒泡排序。首先从后向前冒泡，8和5比较，把5交换到前面，序列变成5, 8, 3, 2, 4。再使用8和3比较再交换，同理变成5, 3, 8, 2, 4。按照这样的规则，比较完成以后序列变成了5, 3, 2, 4, 8。总共冒泡次数为4次（无需与集合中自身进行比较，所以要少比较一次）。然后用目前第一个元素(5)进行冒泡操作，同理第二次比较完成以后的序列变成了3, 2, 4, 5, 8。总共冒泡次数为3次(除去自身，以及上次比较过的元素8)，按照规则对剩下的序列依次冒泡就会得到一个有序序列。冒泡排序的时间复杂度为O(n^2)。
/*
* 冒泡排序
* 升序（比较相邻的元素。如果前一个值比后一个值大，则交换两个元素的位置）
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。通过这样操作，最后的元素应该会是最大的值。
* 针对所有的元素重复以上的步骤，除了上一次操作的最后一个（因为上一次排序的已经判断过比本次元素的值大）。
* 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
* @param array 需要排序的整型数组
*/
private static int[] bubbleSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i = 0; i < array.length; i++) {
//每一个元素都不用与自身进行比较所以会减少一次比较次数，要进行-1的操作。
//每排一次序，数组最后的元素都会由大到小排列。所以随着排序的次数增加，比较的次数会越来越少。
// 直到没有任何一对数字需要比较。此时排序完成
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j + 1] < array[j]) {
// 升序（比较相邻的元素。如果前一个值比后一个值大，则交换两个元素的位置）
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
2. 选择排序
特点：效率低，容易实现。
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，还是对8, 5, 3, 2, 4这个无序序列进行简单选择排序，第一次选择8以外的最小数来和8进行交换，第一次排序后就变成了2, 5, 3, 8, 4。然后在选择5以外的集合中的最小数来和5进行交换，第二次排序以后就变成了2, 3, 5, 8, 4。同理对剩下的序列多次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)。
/**
* 选择排序算法
* 在未排序序列中找到最小元素，存放到排序序列的起始位置
* 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
* 以此类推，直到所有元素均排序完毕。
*/
public static int[] selectionSort(int[] arr) {
//选择
for (int i = 0; i < arr.length; i++) {
int min = arr[i]; //默认第一个是最小的。
int index = i; //记录最小的下标
//不用与自身比较所有要做+1操作
for (int j = i + 1; j < arr.length; j++) {
//通过与数组中的的数据进行比较得出，最小值和下标
if (min > arr[j]) {
min = arr[j];
index = j;
}
}
//然后将最小值与本次循环的，开始值交换
int temp = arr[i];
arr[i] = min;
arr[index] = temp;
}
return arr;
}
3. 插入排序
特点：效率低，容易实现。
插入排序不是通过交换位置而是通过比较找到合适的位置插入元素来达到排序的目的的。举个栗子，对8, 5, 3, 2, 4这个无序序列进行简单插入排序。首先假设第一个数的位置时正确的，然后5要插到8前面，把8后移一位，变成5, 8, 3, 2, 4。注意在插入一个数的时候要保证这个数前面的数已经有序。简单插入排序的时间复杂度也是O(n^2)。
// 插入排序
public static int[] insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// j表示当前元素的位置，将其和左边的元素比较，若当前元素小与左边的元素，就进行位置交换，也就相当于插入左边.
// 这样当前元素位于j-1处，j--来更新当前元素,j一直左移不能越界，因此应该大于0
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
int temp = arr[j]; // 元素交换
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
return arr;
}
4. 快速排序
特点：高效
从数列中挑出一个元素，称为 “基准”（pivot），重新排序数列，比基准值小的所有元素摆放在基准左面，比基准值大的所有元素摆在基准的右面。再在左面和右面的数列中挑出一个基准元素，再按照上面的步骤分成两个数列。如此不断递归地把小于基准值元素的子数列和大于基准值元素的子数列排序，直到子序列为一个元素为止。
动画讲解快速排序
快速排序是不稳定的，其时间平均时间复杂度是O(nlgn)。
二. 查找
查找(searching)是这样一个过程，即在某个项目组中寻找某一指定目标元素，或者确定该组中并不存在该目标元素。
常见的查找方式有：顺序查找、二分法查找、插值查找。
1. 顺序查找
基本思想：顺序查找也称为线形查找，属于无序查找算法。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
顺序查找的时间复杂度为O(n)。
/**顺序查找平均时间复杂度 O（n）
* @param searchKey 要查找的值
* @param array 数组（从这个数组中查找）
* @return 查找结果（数组的下标位置）
*/
public static int orderSearch(int searchKey,int[] array){
if(array==null||array.length<1)
return -1;
for(int i=0;i<array.length;i++){
if(array[i]==searchKey){
return i;
}
}
return -1;
}
2. 二分法查找
算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小 于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
时间复杂度为 O(logN)
说明：元素必须是有序的，如果是无序的则要先进行排序操作。
/**
* 二分查找又称折半查找，它是一种效率较高的查找方法。 【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
*
* @param array
* 有序数组 *
* @param searchKey
* 查找元素 *
* @return searchKey的数组下标，没找到返回-1
*/
public static int binarySearch(int[] array, int searchKey) {
int low = 0;
int high = array.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (searchKey == array[middle]) {
return middle;
} else if (searchKey < array[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return -1;
}
由此看来，在处理已排序数据的查找工作时，二分查找法显然效率高于线性查找法。这种优势在数据量越大的时候越明显。
比如说，现在有序数组中含有100万个数据，我们要求查找特定元素。如果使用线性查找法，我们必须对这一100万个数据依次考察以确定出目标元素是不是存在，最好的情况是目标元素在数组的第一个位置a[0]，这样只要一次就查找到目标元素了，最坏情况是目标元素在数组的最后a[999999]，这样我们就得比较100万次才能知道目标元素到底在不在，平均下来看的话也需要50万次比较。而如果使用二分查找法，我们大约做20次比较就可以知道目标元素是不是存在于数组中了。
就是既然二分查找法效率这么高，甩线性查找法好多条街，那为什么还要线性查找法呢？其实，线性查找法也不是一无是处，它最大的优点就是简单，特别简单。还有一点就是二分法本身也有局限性，那就是二分法必须要求待查数组是已排序的，比如我给你一个很大的数组，但是这个数组并没有排序，那你如果想用二分查找法的话还必须先给数组排序，然后再查找。这样就会造成除查找之外的额外成本（排序）。
网友评论