本
文
摘
要
这段时间也是闲了下来，就抽出时间总结了下Java的六大常用算法，希望可以帮到你们。
一.插入排序算法
插入排序的基本思想是在遍历数组的过程中，假设在序号 i 之前的元素即 [0..i-1] 都已经排好序，本趟需要找到 i 对应的元素 x 的正确位置 k ，并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位，为元素 x “腾位置”，最后将 k 对应的元素值赋为 x ，一般情况下，插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)
二.选择排序算法
选择排序的基本思想是遍历数组的过程中，以 i 代表当前需要排序的序号，则需要在剩余的 [i…n-1] 中找出其中的最小值，然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们很形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
三.冒泡排序法
所谓冒泡排序法就是将比较大的数字沉在最下面，较小的浮在上面
四.快速排序算法
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的，本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大。
可以随机,取名base，首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后,从序列的最左边开始找比base大的，如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小，循环以上两步,直到 low == heigh, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。
五.希尔排序
对于直接插入排序问题，数据量巨大时。
将数的个数设为n，取奇数k=n/2，将下标差值为k的书分为一组，构成有序序列。
再取k=k/2 ，将下标差值为k的书分为一组，构成有序序列。
重复第二步，直到k=1执行简单插入排序。
如何写成代码：
1.首先确定分的组数。
2.然后对组中元素进行插入排序。
3.然后将length/2，重复1,2步，直到length=0为止。
代码实现如下：
public void sheelSort(int[] a){ int d = a.length; while (d!=0) { d=d/2; for (int x = 0; x < d; x++) {//分的组数 for (int i = x + d; i < a.length; i += d) {//组中的元素，从第二个数开始 int j = i - d;//j为有序序列最后一位的位数 int temp = a[i];//要插入的元素 for (; j >= 0 && temp < a[j]; j -= d) {//从后往前遍历。 a[j + d] = a[j];//向后移动d位 } a[j + d] = temp; } } } }六.堆排序,对简单选择排序的优化。
1.将序列构建成大顶堆。
2.将根节点与最后一个节点交换，然后断开最后一个节点。
3.重复第一、二步，直到所有节点断开。
六.堆排序
对简单选择排序的优化。
1.将序列构建成大顶堆。
2.将根节点与最后一个节点交换，然后断开最后一个节点。
3.重复第一、二步，直到所有节点断开。
代码实现如下：
public void heapSort(int[] a){ System.out.println("开始排序"); int arrayLength=a.length; //循环建堆 for(int i=0;i buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } private void swap(int[] data, int i, int j) { // TODO Auto-generated method stub int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } //对data数组从0到lastIndex建大顶堆 private void buildMaxHeap(int[] data, int lastIndex) { // TODO Auto-generated method stub //从lastIndex处节点（最后一个节点）的父节点开始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在 while(k*2+1<=lastIndex){ //k节点的左子节点的索引 int biggerIndex=2*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 if(biggerIndex if(data[biggerIndex] biggerIndex++; } } //如果k节点的值小于其较大的子节点的值 if(data[k] swap(data,k,biggerIndex); //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 k=biggerIndex; }else{ break; } } } }常见的排序不止这六个，今天因为篇幅原因只能分享到这里了，喜欢我的
文章，请多多支持喔，你们的支持是我更新的动力。
