二分法

 顾明思意，二分法就是将我们的数组一分为二，然后拿我们要查找的数去和中间的那个元素比较，如果刚好等于中间那个元素，那么就返回中间位置的下标。如果比中间的元素小，那么再使用相同的方式从中间元素的前面部分去找；相反如果比中间元素更大，那么就在中间元素后面的部分去找。如此循环，这样就叫二分法，相信大家都意识到了，二分法之所以能这样做的前提是：数组已经是有序的（通常情况下是升序）。下面看一下二分法的具体实现： 

讯享网
以上图片就是整个二分法的实现过程，从上面可以看出，二分法排序关键是要确定中间元素的下标，那么中间元素的下标怎么来确定呢？在我们初始化的时候，定义一个整形变量start和一个end,分别指向数组的头和尾，那么中间元素的下标就是：（start + end）/2,然后比较中间元素和要查找元素的大小。如果此时中间的元素等于要查找的元素，那么就直接返回下标。如果要查找的元素比中间元素小，那么让end = middle - 1;相反，如果比中间元素大的话，就让start = middle + 1。 为什么要这样做呢，我们仔细想一想，中间元素的下标是不是每次都在变，而middle = (start + end) / 2,所以start 和end 实际上就是用来控制middle的。利用循环来使middle不断地改变，直到start < end的时候结束。下面是具体代码实现：

讯享网/ array:被查找的数组，默认升序 number:被查找的元素 */ public int EFSort(int[] array,int number){ 
    //定义起始位置 int start = 0; //定义结束位置 int end = array.length - 1; while(start < end){ 
    //每次循环让 中间元素下标等于（start + end） / 2  int middle = (start + end) / 2; //如果要查找的元素和中间元素相等，直接返回middle if(array[middle] == number){ 
    return middle; }else{ 
    //如果中间元素比number大，那么去前面找 if(array[middle] > number){ 
    end = middle - 1; }else{ 
    //否则就去后面找 start = middle + 1; } } } return -1; }

排序算法之：冒泡排序

 冒泡排序的原理其实非常简单：当我们拿到一个数组过后，从头开始，第一个元素与第二个元素比较，把大的放后面，小的放前面；然后第二个元素与第三个元素比较，大的放后面，小的放前面；然后第三个与第四个比较；第四个与第五个比较......如此下去直到把数组中最大的那个数放到数组的末尾。这样就完成了第一堂冒泡排序。然后进行下一轮比较，这时，上一轮比较出来的最大的元素就不用参与比较了。所以冒泡排序每轮的比较次数都在减少。看一个例子： 数组array[4,5,2,1,9,8,6] 第一趟：4和5比，不要用交换；5和2比，交换[4 , 2 , 5 , 1 , 9 , 8 , 6] ；5和1比：交换[4 , 2 , 1 , 5 , 9 , 8 , 6] ；5和9比，不用交换；9和8比，交换[4 , 2 , 1 , 5 , 8 , 9 , 6] ；9和6比，交换[4 , 2 , 1 , 5 , 8 , 6 , 9]；这样第一趟就把最大的元素排到了最后面，可以看出第一次只比较了6次 第二趟：4和2比，交换[2 , 4 , 1 , 5 , 8 , 6 , 9]；4和1比，交换[2 , 1 , 4 , 5 , 8 , 6 , 9]；4和5比，不用交换；5和8比，不用交换；8和6比：交换[2 , 1 , 4 , 5 , 6 , 8 , 9]；8就不用和9比，所以比较次数比上一轮少一次。 第三趟、第四趟.......这样数组最终会被排序成[1 , 2 , 4 , 5 , 6 , 8 , 9] 

讯享网public int[] bubbleSort(int[] array){ 
    //第一堂的比较次数最多：array.length - 1 for(int i = 0;i < array.length - 1;i++){ 
    //每一趟的比较次数都比上一次少1 for(int j = 0;j<array.length -1 - i;j++){ 
    if(array[j] > array[j+1]){ 
    int temp = array[j+1]; array[j+1] = array[j]; array[j] = temp; } } } return array; }

排序算法之：快速排序

 快速排序很多时候称之为快排，他的核心思想呢就是：定义一个标准数，然后比标准数小的全部放在数组左边，比标准数大的全部放在数组右边（当然也可以反过来）。通常情况下我们将数组的第一个元素作为一个标准数，然后再用两个变量start、end分别指像数组的头和尾，因为标准数定义在数组的第一个元素，所以我们从右边开始遍历数组当遇到比标准数小的时候我们就执行 array[start] = array[end]；然后从左边开始遍历找到比标准数大的元素执行：array[end] = array[start]; 注意遍历的时候如果不满足条件就start ++ 或则end --。 最后start和 end 相等。这时就把之前定义的标准数放在这儿：array[start] = 标准数。 比如有一个数组：array [2，8，6，1，0，3，7，4]； 1、标准数：int stand = array[0]; //stand = 9 2、start = 0，end = array.length - 1; while(start < end){ //从右边开始，直到找到比标准数小的 while( array[end] >=stand && start < end ){ end--; } //while循环结束后，表示已经找到比标准数小的数了，所以现在要做的就是把这个值赋给 start 所指向的地方 array[start] = array[end]; //然后从左边开始，直到找到比标准数大的，放在数组右边 while( array[start] <= stand && start < end ){ start++; } //while循环结束后，表示已经找到比标准数大的数了，所以现在要做的就是把这个值赋给 end 所指向的地方 array[end] = array[start]; } //最外层while循环结束，表示start = end 这是用标准数来代替这个位置 array[start] = stand; 这就是第一趟快排，上面的数组经过这样的操作后会变成这个样子： array[0，1，2，6，8，3，7，4] 可以看到2左边的数都比2小，2右边的数都比2大。这时候利用递归把2的左边、右边在使用快排，这样数组就被排序好了。下面用代码来实现： 

讯享网/ array:需要排序的数组 start:开始下标 end:结束下标 当start和end相等时，即使递归结束条件 */ public void quickSort(int[] array,int start,int end){ 
    if(start < end){ 
    //默认标准数为start所值的元素 int stand = array[start]; //分别用两个变量来表示start和end int startPoint = start; int endPoint = end; while( startPoint < endPoint ){ 
    //从右边开始，直到找到比标准书小的数 while(array[endPoint] >= stand && startPoint < endPoint){ 
    endPoint--; } //把这个比标准数小的数赋值给startPoint对应的地方 array[startPoint] = array[endPoint]; //从左边开始，直到找到比标准书大的数 while(array[startPoint] <= stand && startPoint < endPoint){ 
    startPoint++; } // //把这个比标准数大的数赋值给endPoint对应的地方 array[endPoint] = array[startPoint]; } //这是startPoint = endPoint,把标准值赋值给他们指向的位置 array[startPoint] = stand; //或者array[endPoint] = stand; //然后调用递归将左半边继续采用快排： quickSort(array,start,startPoint); //继续对右半边快排： quickSort(array,startPoint+1,end); } }

排序算法之：直接插入排序

直接插入排序的思路比较简单：首先我们拿到一个数组，从它的第二个元素开始，再用一个循环来遍历它之前的元素，如果他之前的元素比他大，那么就交换。

以上图片是直接插入排序的实现思路，下面通过代码来实现一下：

public void insertSort(int[] array){ 
    //从第二个元素开始 for(int i = 1;i<array.length;i++) //遍历第i个元素之前的数据，依次比较大小 //用一个临时变量来存储第i个元素 int temp = array[i]; for(int j = i - 1;j >= 0 && array[j] >= array[j+1];j--){ 
    array[j+1] = array[j]; array[j] = temp; } }

排序算法之：希尔排序

希尔排序也是非常有意思的一种排序算法，他是基于直接选择排序进行优化得到的一种算法。他的关键思想就是利用步长来对数进行分组，然后对这些分组进行直接插入排序。

下面使用代码来实现希尔排序：

讯享网public void shellSort(int[] array){ 
    //定义步长 int d = array.length / 2; while( d != 0 ){ 
    //内部使用直接插入排序,因为使用了步长，所以起始位置不再是1，而是步长d for(int i = d;i<array.length;i++){ 
    int temp = array[i]; for(int j = i -d;j >= 0 && array[j] >= array[j+d];j = j-d ){ 
    array[j+d] =array[j]; array[j] = temp; } } //步长为原来的半 d = d/2; } }

排序算法之：简单选择排序

简单选择排序的思路比较简单，从第一个元素开始，然后默认他是最小的数并且用整型变量index记录位置，然后从它开始遍历，遇到比他小的，就让把这个数的下标赋值给index，这样第一次循环下来，index下标对应的数就是最小的那个数。然后把它赋值给本次循环开始的位置。第二次循环就从数组的第二个元素开始，用相同的方法进行遍历。直到从最后一个元素开始，这样数组就被排序好了。下面我们看一下具体的代码：

public void simpleSelectSort(int[] array){ 
    for(int i = 0;i < array.length;i++){ 
    int index = i; //从当前这个元素开始向后遍历，i前面的元素已经排序好了 for(int j = i;j<array.length;j++){ 
    if(array[j] < array[index]){ 
    index = j; } } //最后把index对应的元素和i对应的元素交换 int temp = array[i]; array[i] = array[index]; array[index] = temp; } }

排序算法之：堆排序

在介绍堆排序之前我们先来回顾一下二叉树相关的知识：
1、二叉树：指的是树里面每个节点的子节点数都小于等于2
2、满二叉树：所有的叶子节点都在最后一层，总节点数：2的n次方-1（n表示树的高度）
3、完全二叉树：所有的叶子节点都在最后一层或倒数第二层，并且，叶子节点在倒数第二层右连续，在最后一层左连续，且对于第n个节点而言：
其左儿子节点：2n + 1，其右儿子节点：2n + 2,其父节点：(n-1)/2
二对于一棵二叉树而言，如果每个双亲节点的权重都比其子节点的权重大，那么称这个二叉树为大顶堆（左），反正称为小顶堆（右）

由于我们是对数组进行排序，而数组是连续的存储结构，所以我们要使用完全二叉树的性质，首先我们要找到最后一个非叶子节点的位置，利用完全二叉树的性值，数组的最后一个叶子节点的下标为array.length - 1，则他的父节点就是最后一个非叶子节点。所以最后一个非叶子节点的下标为： (array.length - 2) /2,找到最后一个非叶子节点以后，将他的权值和它的两个子节点比较，如果他的权值比两个子节点的都大，就不用进行交换，否则需要交换。下面用代码来具体演示：

讯享网/ array:需要排序的数组 size:待排序数组的大小 index:开始比较的位置 */ public void maxHeap(int[] array,int size,int index){ 
    if(index <= size){ 
    //左儿子节点的下标 int leftNode = 2 * index + 1; //右儿子节点的下标 int rightNode = 2 * index + 2; int max = index;//默认父节点的权重最大 //判断左儿子存不存在以及权重是否大于夫节点： if(leftNode <= size && array[leftNode] > array[index]){ 
    max = leftNode; } //判断右儿子儿子存不存在以及权重是否大于父节点： if(rightNode <= size && array[rightNode] > array[index]){ 
    max = rightNode; } //交换 int temp = array[max]; array[max] = array[index]; array[index] = temp; //交换以后，可能改变子节点这棵树的顺序，所以还要对子节点这个树进行递归 maxHeap(array,size,max); } } public void heapSort(int[] array){ 
    //先找到最后一个非叶子节点 int index = (array.length - 2)/2； //先将数组变成一个大顶堆 for(int i = index,i >= 0;i--){ 
    maxHeap(array,array.length - 1;i) } //然后将堆顶的元素赋值给数组最后面的元素 for(int j = array.length - 1;j > 0;j--){ 
    //交换 int temp = array[j]; array[j] = array[0]; array[0] = temp; maxHeap(array,j-1,0); } }

排序算法之：归并排序

在归并排序之前先了解一下归并的原理：把两个有序的数组归并成一个数组：如下图：

下面用代码来具体实现一下：

/ low:从哪儿开始归并 middle:从哪儿开始将数组分割成两个数组 hign:归并范围的临界值 */ public void merge(int[] array,int low,int middle,int hign){ 
    //首先我们需要定义一个新数组来存放归并后的结果，这里我们借助middle来将array抽象成两个数组 第一个 [low,middle] 第二个[middle+1,hign] int[] newArray = new int[hign - low + 1]; //第一个数组起始位置 int lowPoint = low; //第二个数组起始位置 int startPoint = middle + 1; //新数组的下标 int index = 0; while( lowPoint <= middle && startPoint <= hign ){ 
    if(array[lowPoint] <= array[startPoint]){ 
    newArray[index] = array[lowPoint]; lowPoint++; }else{ 
    newArray[index] = array[startPoint]; startPoint++; } index++; } //把剩下的元素再追加到newArray中，因为两个分割出来的数组长度可能不一样 while( lowPoint <= middle ){ 
    newArray[index] = array[lowPoint]; lowPoint++; index++; } while( startPoint <= hign ){ 
    newArray[index] = array[startPoint]; startPoint++; index++; } //再把新数组赋值给旧数组 for(int i = 0; i < newArray.length;i++){ 
    array[low+i] = newArray[i]; } } //除此之外我们还需要一个函数来将待排序的数组进行无线分割，分割成有序的状态，如下图： public void mergeSort(int[] array,int start,int end){ 
    //递归条件：起始位置小与末位，如果两个变量相等了，没必要再分割了 if(start < end ){ 
    //定义分割位置 int middle = (start + end)/2; //利用递归分割左边 mergeSort(array,start,middle); mergeSort(array,middle+1,end); merge(array,start,middle,end); } }

排序算法之：基数排序

基数排序算法的核心是：第一次循环先用个位来将数进行分组，然后将这些书又放回原数组，再利用十位进行分组如此下去，直到用这些书最大的位数来进行分组后，排序结束。可以看出基数排序的循环次数取决于最大的那个数是几位数。
下面用代码来实现一下：

讯享网public void radixSort(int[] array){ 
    //定义一个最小数 int max = Integer.MIN_VALUE; //找到数组中最大的元素 for(int i : array){ 
    if(i > max){ 
    max = i; } } //可以把上面的是个筒子看成一个二维数组,数组的行代表筒的下标，数组列代表元素个数，最多也就数组的长度 int[][] temp = new int[10][array.length]; //因为要进行不断的取放，所以还要定义一个一维数组来标识对应筒子里面有对少个元素，而且还可以记录下标 int[] record = new int[10]; //判断最大数的位数，决定循环次数 int ws = (""+max).length(); for(int j = 0, n=1;j < ws;j++,n = n*10 ){ 
    //遍历每一个元素 for(int k = 0;k < array.length; k++){ 
    int ys = array[k]/n%10; temp[ys][record[ys]] = array[k]; record[ys]++; } //取出来： int index = 0; //遍历余数对应的筒子 for(int l = 0;l < record.length; l++){ 
    if(record[l] != 0){ 
    for(int m = 0;m < record[l];m++){ 
    array[index] = temp[l][m]; index++; } //将record重置为0，下一轮循环要对十位进行操作 record[l] = 0; } } } }

以上就是我个人对二分法以及八大基本排序算法的理解，欢迎各位小伙伴不吝赐教，提出优化建议。