基础算法系列
二分查找法
二分查找又称折半算法，此算法作为一个经典的查找算法是我们不得不掌握的算法这个算法查找的前提是查找的数据是有序的，我们以数组为例，使用二分查找法进行查找的时候我们应该先定义三个字段：
- left指向数组第一个数据
- right指向数组最后一个元素
- mid呢指向（left+right）/2位置的元素，就是他们中间的位置。
- 当我们要在一个数组中查找一条数据a时，有这么几个步骤：
- 首先我们拿a与mid比较，如果a与mid相等那么我们就成功找到了这个数据，程序停止。 如果a比mid小进行第3步,如果a比mid大进行第4步 既然a小于mid，那么mid与right之间的数肯定比a大，所以我们忽略它们，紧接着把right指向mid的前一个位置。（你可能会问为啥指向前一个位置不指向mid呀，因为我们已经确定了mid不等于a，那么我们就不需要在比较他了） 既然a大于mid，那么mid与left之间的数肯定比a小，所以我们忽略它们，紧接着把left指向mid的后一个位置。（不明白可以参考3哦） 如果left不大于right那么我们就还没有查找完毕，继续进行第一步。如果left已经大于了right，那么就代表在这个数组里我们没有找到想要的数据。 建议对二分查找不太熟悉的同学可以先在草稿纸上、电脑上或者脑海里定义一个0-16的有序数组跟着上边的步骤来查找一下数据5。
下面这个图是我画的图，来看一下跟你画的步骤或者想象的步骤一样么
如果上图你已经看明白了的话那么接下来我们就上代码吧，
public static void select(int[]num,int a){
int left=0;
int right=num.length-1;
int m=(left+right)/2;
while(left<=right){
if(num[m]==a){
System.out.println("在"+m+"位置找到");
return;
}
if (num[m]>a){
right=m-1;
}else{
left=m+1;
}
m=(left+right)/2;
}
System.out.println("没找到");
}上面的方法使用了一个普通的循环的方式，二分还存在一种递归的写法，这里也分享出来
public static void select(int[]num,int a,int left,int right){
if(left>right){
System.out.println("没找到");
return;
}
int m=(left+right)/2;
if(num[m]==a){
System.out.println("在"+m+"位置找到");
return;
}
if (num[m]>a){
right=m-1;
select(num, a,left,right);
}else{
left=m+1;
select(num, a,left,right);
}
}选择排序
假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么选择排序的排序流程为：
在这个数组中找出最小值与第一个元素交换，现在数组为[0,1,3,2,8,4,2] 在这个数组中除了第一个位置的元素外找出最小值与第二个元素交换，因为第二个元素就是最小的所以此次没有发生变化。现在数组为[0,1,3,2,8,4,2] 在这个数组中除了第一个、第二个位置的元素外找出最小值与第三个元素交换，现在数组为[0,1,2,3,8,4,2] 在这个数组中除了第一个、第二个、第三个位置的元素外找出最小值与第四个元素交换，现在数组为[0,1,2,2,8,4,3] 在这个数组中除了第一个、第二个、第三个、第四个位置的元素外找出最小值与第五个元素交换，现在数组为[0,1,2,2,3,4,8] 在这个数组中除了第一个、第二个、第三个、第四个、第五个位置的元素外找出最小值与第六个个元素交换，因为第六个元素就是最小的所以此次没有发生变化。现在数组为[0,1,2,2,3,4,8] 现在整个数组是不是已经变得有序了呢。接下来我们看图解版本
接下来上代码
int i; // 有序区的末尾位置
int j; // 无序区的起始位置
int min; // 无序区中最小元素位置
int []a=new int[]{3,1,0,2,8,4,2};
for(i=0,n=a.length; i<n; i++) {
min=i;
// 找出"a[i+1] ... a[n]"之间的最小元素，并赋值给min。
for(j=i+1; j<n; j++) {
if(a[j] < a[min])
min=j;
}
// 若min!=i，则交换 a[i] 和 a[min]。
// 交换之后，保证了a[0] ... a[i] 之间的元素是有序的。
if(min != i) {
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}插入排序
相信大家都有打扑克的经历，那么我们今天的插入排序就以拿牌为例开始讲（注意只是举例，不是按打牌的规则哦）
1.我们拿到了一张牌3，我们把它放手里，现在手里有牌[3]
2.我们拿到了一张牌1，拿它与手里最后一张牌也就是3比较，发现1比3小，所以我们把它插入到3的前面，现在手里有牌[1,3]
3.我们拿到了一张牌0，拿它与手里最后一张牌也就是3比较，发现0比3小，所以我们把它插入到3的前面，接着与3的上一张比较发现0比1还小，那么就把0在插入到1的前面，现在手里有牌[0,1,3]
4.我们拿到了一张牌2，拿它与手里最后一张牌也就是3比较，发现2比3小，所以我们把它插入到3的前面，接着与3的上一张比较发现2比1大，那么就不需要动了，现在手里有牌[0,1,2,3]
5.我们拿到了一张牌8，拿它与手里最后一张牌也就是3比较，8比3大，那么就不需要动了，现在手里有牌[0,1,2,3,8]
6.。。。
现在你明白什么叫做插入排序了么？
如果你不明白的话也没关系，我还专门画了一张图：
接下来上代码
int []num=new int[]{3,1,0,2,8,4,2};
for (int i=1,n=num.length;i<n;i++){
if(num[i]<num[i-1]){
for (int j=i;j>0;j--){
if(num[j]<num[j-1]){
int temp=num[j];
num[j]=num[j-1];
num[j-1]=temp;
}
}
}
}
for (int i:num){
System.out.print(i+",");
}快速排序
快速排序是一个运用了分治法和递归算法的排序方式。
假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么在进行快速排序的时候我们先要进行一些准备：
n作为一个数组中的标杆，一趟排序过后我们要把数组中所有大于n的数放在它的右边，所有小于n的放在它的左边。一般情况下我们会取数组第一个元素作为n，在此数组中就是n=3 i我们使用i来找数组中大于标杆的值，i初始指向数组第一个位置 j我们使用j来找数组中小于标杆的值，j初始指向数组最后一个位置 下面开始排序：
先从数组右边开始，我们发现j指向的元素2比标杆n小，那么我们将j指向的元素赋值给i指向的元素，停止操作。此时数组为[2,1,0,2,8,4,2]，i指向第一个位置，j仍指向最后一个。 从数组左边开始，i指向的元素2比标杆小，所以不做操作，使i++，i指向的元素1比标杆小，所以不做操作，使i++，一直到i指向8的时候比标杆大（注意此处如果等于的话也要操作），那么就把i指向的元素赋值给j指向的元素，此时数组为[2,1,0,2,8,4,8]，i指向第五个位置。也就是元素8，j仍然指向最后一个位置。 继续从右边操作，j指向的8不比n小，所以不做操作，j–，4不比3小，不做操作，j–。现在i和j的位置重合了，把n放到这个位置上。我们此轮的操作也就结束了，接下来我们把3所在的位置左边分为一个数组，右边位置分为一个数组再次进行刚才的操作。（此处就是一个递归调用了） 接下来就来看一个图片描述的过程
接下来上代码
public static void quickSort(int[] a, int l, int r) {
if (l < r) {
int i,j,n;
i = l;
j = r;
n = a[i];
while (i < j) {
while(i < j ){
if(a[j] < n){
a[i] = a[j];
break;
}
j--;
}
while(i < j ){
if(a[i] >= n){
a[j] = a[i];
break;
}
i++;
}
}
a[i] = n;
quickSort(a, l, i-1); /* 递归调用 */
quickSort(a, i+1, r); /* 递归调用 */
}
}希尔排序
希尔排序呢，其实可以理解为插入算法排序的一个升级版了.
我们知道，插入排序在进行排序时如果当数据量很大的时候，有一个很小的数据出现在了数组的最后，那么我们就要移动了这个数据前面所有的元素给它放置到合适的元素。例如：
我们要排序的数组为[1,2,3,4,5,6,7，。。。此处省略一百万。。.,0]。详细大家肯定不喜欢这个0往前移动一百万此吧。
希尔排序的出现其实就是为了解决这个问题的，希尔排序呢，使用了分治算法，先把整个大的数组根据某个增量分为若干个组，先对这若干个组进行一个调整，保证大部分小的数据会被调整到前面来。到最后再次进行插入排序，这样就大大加快了效率了。
来一个例子，我们要排序的数组为[3, 1, 0, 2, 8, 4, 2,6,9,1,3,-2,8],先来看一张图
上方图片所说的增量就是我们进行分组的依据了。我们在这里初始值取得是数组得2分之一（此值没有标准的定义，只需保证大于1且小于数组长度即可），而红线所指向得就是我们根据这个增量所分的组了，我们分别针对每组进行排序。 可以在增量为3的结果种看到，第一组3，2，8 变为了2，3，8、第二组第三组没变、第四组变为了1，2、第五组变为了3，8、第六组变为了-2，4. 接下来增量减半，我们的数组分为3组，分别进行排序。 现在增量值经过再次减半后已经变为1了，我们可以通过观察数组发现，在数组的后面基本不可能出现最小的数据了，现在对数组进行插入排序的效率已经非常高了。 不知道现在的你明白希尔排序了么？来看一看代码吧。
void shellSort(int list[], int length){
int gap,i,j,temp;
for (gap = length/2; gap > 0; gap /= 2){
for(i = gap; i < length; i++){
for(j = i-gap; j>=0 && list[j]>list[j+gap]; j -= gap){
temp = list[j];
list[j] = list[j+gap];
list[j+gap] = temp;
}
}
}
}冒泡排序
冒泡排序在排序算法中效率算最慢的一类了，但是因为它简单的缘故仍然是工作1-3年的程序员面试经常会碰到的算法问题，今天就来给大家分析一下冒泡排序的排序流程。
假如我们现在要排序的数组为[3,1,0,2,8,4,2]那么我们第一轮排序为
比较3和1，发现3比1大，那么我们就交换3和1，数组变成了[1,3,0,2,8,4,2] 比较3和0，发现3比0大，那么我们就交换3和0，数组变成了[1,0,3,2,8,4,2] 比较3和2，发现3比2大，那么我们就交换3和2，数组变成了[1,0,2,3,8,4,2] 比较3和8，发现3没有8大，那么不操作，数组还是[1,0,2,3,8,4,2] 比较8和4，发现8比4大，那么我们就交换8和4，数组变成了[1,0,2,3,4,8,2] 比较8和2，发现8比2大，那么我们就交换8和2，数组变成了[1,0,2,3,4,2,8] 现在第一轮的排序已经完成了，我们就筛选出来了最大值8，此时数字8已经在数组最后的位置了，下一轮排序我们就可以排除它了。
第二轮排序为：
比较1和0，发现1比0大，那么我们就交换1和0，数组变成了[0,1,2,3,4,2,8] 比较1和2，发现1没有2大，那么不操作，数组还是[0,1,2,3,4,2,8] 比较2和3，发现2没有3大，那么不操作，数组还是[0,1,2,3,4,2,8] 比较3和4，发现3没有4大，那么不操作，数组还是[0,1,2,3,4,2,8] 比较4和2，发现4比2大，那么我们就交换4和2，数组变成了[0,1,2,3,2,4,8] 现在第二轮排序完成了，数组最后的4和8是不是已经有序了呢。
聪明的你是不是已经发现了冒泡排序的规律了呢，那么你能用代码去手写一下实现么？
int []a=new int[]{3,1,0,2,8,4,2};
int i,j;
int flag; // 标记
for (i=a.length-1; i>0; i--) {
flag = 0; // 初始化标记为0
// 将a[0...i]中最大的数据放在末尾
for (j=0; j<i; j++) {
if (a[j] > a[j+1]) {
// 交换a[j]和a[j+1]
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = 1; // 若发生交换，则设标记为1
}
}
if (flag==0)
break; // 若没发生交换，则说明数列已有序。
}
for (int ii:a){
System.out.print(ii+",");
}腾讯云开发者
