冒泡排序 1.排序思想
从无序序列头部开始，进行两两比较，根据大小交换位置，直到最后将最大的数据元素交换带无序队列队尾， 下一次继续这个过程。
2.时间复杂度
最好情况： O(n) 给出的数据有序 最坏情况： O(n^2) 无序
3.空间复杂度
O(1)4.稳定性
稳定5.用画图的方式结合文字进行总结
6.代码实现与分析
public static void bubbleSort(int[] array) { boolean swap = false; //表示是否发生交换 for (int i = 0; i < array.length - 1; ++i) { //外层循环，次数 for (int j = 0; j < array.length - 1 - i; ++j) {//内层循环，每一次的比较 if (array[j] > array[j + 1]) { int tmp = array[j]; //将前面大数字和后面小数字进行交换 array[j] = array[j + 1]; array[j + 1] = tmp; swap = true; //如果交换 swap就换成true } } if (!swap) { break; } } }选择排序
1.排序的思想
在执行第i趟操作作时候，从第i条记录后选择一条最小的记录和第i条进行比较交换2.时间复杂度
O(n^2)3.空间复杂度
O(1)4.稳定性：
不稳定5.用画图的方式结合文字进行总结
代码实现与分析 public static void selectSort(int[] array){ int tmp = 0; for (int i = 0; i<array.length;++i){//遍历数组 for (int j = i+1;j<array.length;++j){ //每次载遍历i后面的 数字 if (array[i]>array[j]){//每次将i与j进行比较然后交换 tmp = array[i]; array[i] = array[j]; array[j] = tmp; } } } }直接插入排序
1.排序的思想
每一次将一个待排序的元素，按其数字的大小插入到前面已经排好序的一组元素的合适位置上去，直到元
素全部插完为止。（分组排序）
2.时间复杂度
最优情况下： O(n) 给出的数据有序 最差情况下： O(n^2) 无序
3.空间复杂度
O(1)4.稳定性
稳定 优化希尔排序从某种意义上(分组)是对直接插入排序的优化
用画图的方式结合文字进行总结
7.代码实现与分析
public static void insertSort(int[] array){ int tmp = 0; int j = 0; for (int i = 1;i<array.length;++i) {//因为第一个数字不需要排序 所以i=1 tmp = array[i]; for ( j = i-1; j >= 0; --j) { //遍历待排数字后面的数字 然后进行比较交换 if (array[j] > tmp) { //将大的数字往后挪 array[j+1] = array[j]; }else{ break; //找到比待排数字小的数字就跳出循环，前面已经有序了 } } array[j+1] = tmp; } }Shell排序
1.排序思想
待排序列有n个元素，先去一个小于n的整数h1作为第一个增量，把待排序列以间隔h1分成若干子序列，子序列内使用插入排序；然后取第二个增量h2，（<h1），重复上述的划分和排序，直到索取的增量h1 = 1（h1 > h2 > ……>hi）。
2.时间复杂度
Shell排序是一种不稳定的排序算法，文献表明其时间复杂度受增量序列的影响明显大于其他因素，最环的情况是O(n2),好的情况在O(n1.3)，与增量序列选择有关。
3.空间复杂度
O(1)4.稳定性
不稳定5.用画图的方式结合文字进行总结
6.代码实现与分析
public static void shell(int[] array,int gap){ for (int i = gap;i<array.length;++i){ //以gap为间隔 分成若干进行遍历 int tmp = array[i]; int j = 0; for (j = i-gap;j>=0;j -= gap){ //记录后移，查找插入的位置 if (array[j] >tmp){ array[j+gap] = array[j]; }else{ break; } } array[j+gap] = tmp; } } public static void shellSort(int[] array){ int[] drr = {5,3,1}; //创建一个数组，为排序只作为间隔的值 for (int i = 0;i<drr.length;++i){ shell(array,drr[i]); } }快速排序
1.快速排序的思想
先从数列中取出一个数作为基准数；分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边；再对左右区间重复第二步，直到各区间只有一个数。
2.时间复杂度
最好情况：O(nlog2n)
最快情况：O(n2)
3空间复杂度
O(log2n)4.稳定性
不稳定5.优化
第一种：当数据量少的时候有插入排序 ；第二种：聚焦相同的基准元素法6.用画图的方式结合文字进行总结
7.代码实现与分析
import java.util.Arrays; import java.util.Random; /** * Created with IntelliJ IDEA. * Description:快排的三种排序方式以及两种优化方式 * 排序方式：1.固定位置选取基准法 2.随机选取基准法 3.三分取中法 * 优化方式：1、当数据量少的时候用插入排序 2.聚集相同基准元素法 * User: GAOBO * Date: 2018-09-16 * Time: 17:27 */ public class src2 { public static int partion(int[] array,int low,int high) { int tmp = array[low]; while (low < high) { while(low < high && array[high] >= tmp) { high--; } if(low >= high) { break;//array[low] = tmp; } else { array[low] = array[high]; } while(low < high && array[low] <= tmp) { low++; } if(low >= high) { break; } else { array[high] = array[low]; } } array[low] = tmp;//par return low; } public static void swap(int[] array,int low,int high) { int tmp = array[low]; array[low] = array[high]; array[high] = tmp; } // 排序方法：3.三分取中法 public static void medianOfThree(int[] array,int low,int high) { int mid = (high+low)>>1; //array[mid] <= array[low] <= array[high] if(array[low] > array[high]) {//array[low] <= array[high] swap(array,low,high); } if(array[low] < array[mid]) {//array[mid] <= array[low] swap(array,low,mid); } if(array[mid] > array[high]) {//array[mid] <= array[high] swap(array,mid,high); } } //优化：1、当数据量少的时候用插入排序 public static void insertSort(int[] array,int low,int high) { int tmp = 0; for(int i = low+1;i < high;i++) { tmp = array[i]; int j = 0; for(j = i-1;j >= low;j--) { if(tmp < array[j]) { array[j+1] = array[j]; } else { break; } } array[j+1] = tmp; } } //优化：2.聚集相同基准元素法 public static int[] focusParNum(int[] array,int low,int high,int par, int left,int right) { int[] brr = new int[2]; int parR = par+1; int parL = par-1; for(int i = par-1;i >= low;i--) { if(array[i] == array[par]) { if(i != parL) { swap(array,i,parL); parL--; } else { parL--; } } } left = parL; for(int i = par+1;i <= high;i++) { if(array[i] == array[par]) { if(i != parR) { swap(array,i,parR); parR++; } else { parR++; } } } right = parR; brr[0] = left; brr[1] = right; return brr; } public static void quick(int[] array,int low,int high) { //优化方式1：数据量少的时候 用直接插入排序 /*if(high - low < 100) { //直接插入排序 System.out.println("insert comeing"); insertSort(array,low,high); }*/ /* 1、无限趋近于一个终止条件 2、循环调用自己本身 */ /* //方式2、随机选取基准法 Random random = new Random(); //low --- high 2 7 7-2 = 5 === [0,5) //6 8 2===>[0,2)===0,1+6 int rand = random.nextInt((high-low)+1+low); //low rand swap(array,low,rand); //方式3、三分取中法*/ medianOfThree(array,low,high); int par = partion(array,low,high);//一次划分函数，第一个par//O(n) //优化方式2：聚集相同基准元素法 int left = par-1; int right = par+1; int[] brr = focusParNum(array,low,high,par,left,right); left = brr[0]; right = brr[1]; //保证一个前提：必须有两个数据以上 if(par > low+1) {//log2n quick(array,low,left); } if(par < high-1) { quick(array,right,high); } } public static void quickSort(int[] array) { quick(array,0,array.length-1); } public static String getColumnLable(int n) { String tmp = ""; // 按位找 int count = 1; while (((int) (n / Math.pow(26, count-1)) > 0)) { int w3 = ((int) (n % Math.pow(26, count)) / (int) Math.pow(26, count - 1)); char c = (char) (w3 + 64); tmp = c + tmp; count++; } return tmp; }堆排序
1.堆排序的基本思想
堆排序的原理就是这样，先构造出来大根堆（假设从小到大排序），然后取出堆顶元素（也就是最大的元素），放到数组的最后面，然后再将剩余的元素构造大根堆，再取出堆顶元素放到数组倒数第二个位置，依次类推，知道所有的元素都放到数组中，排序就完成了
2.时间复杂度
O(nlog2n)3.空间复杂度
O(1)4.稳定性
不稳定5.用画图的方式结合文字进行总结
6.代码实现与分析
public static void adjust(int[] array,int start,int end) { int tmp = array[start]; for(int i = 2*start+1; i <= end;i = i*2+1) { //1、是否有右孩子，如果有i表示的就是大的数字的下标 if((i < end) && array[i] < array[i+1]) { i++; } if(array[i] > tmp) { array[start] = array[i]; start = i; } if(array[i] <= tmp) { break; } } array[start] = tmp; } public static void heapSort(int[] array) { //1、调整大根堆 for(int i = (array.length-1-1)/2;i >= 0;i--) { adjust(array,i,array.length-1); } //1.交换 2.调整 for(int j = 0;j < array.length-1;j++) { int tmp = array[0]; array[0] = array[array.length-1-j]; array[array.length-1-j] = tmp; //-1:上面交换过后的节点不计算 adjust(array,0,array.length-1-j-1); } }归并排序
1.归并排序的基本思想：
归并排序就是利用归并思想对数列进行排序。根据具体的实现，归并排序包括"从上往下"和"从下往上"2种方式。
第一是从下往上的归并排序：将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。这样就得到了我们想要的排序结果。第二是从上往下的归并排序：它与"从下往上"在排序上是反方向的。它基本包括3步： ① 分解 – 将当前区间一分为二，即求分裂点 mid = (low + high)/2; ② 求解 – 递归地对两个子区间a[low…mid] 和 a[mid+1…high]进行归并排序。递归的终结条件是子区间长度为1。 ③ 合并 – 将已排序的两个子区间a[low…mid]和 a[mid+1…high]归并为一个有序的区间a[low…high]。
2.时间复杂度
O(nolg2n)3.空间复杂度
O(n)4.稳定性
稳定5.用画图的方式结合文字进行总结
6.代码实现与分析
public static void mergeSort(int[] array){ for (int i = 1;i<array.length;i *= 2){ merge(array,i); } } private static void merge(int[] array, int gap) { int[] tmp = new int[array.length]; int i = 0;//表示数组tmp的下标 //确定s1,s2,e1,e2 int start1 = 0; int end1 = start1 + gap-1; int start2 = end1+1; int end2 = start2 + gap-1 < array.length-1 ? start2 + gap-1 : array.length-1; //判断是否有两个归并段 while (start2 < array.length){ while (start1 <= end1 && start2 <= end2){ if (array[start1] < array[start2]){ tmp[i++] = array[start1++]; }else{ tmp[i++] = array[start2++]; } } //1.退出上面循环两种条件 while (start2 <= end2) { tmp[i++] = array[start2++]; } //2.start2 > end2 while (start1 <= end1) { tmp[i++] = array[start1++]; } //重新对start1 end1 start2 end2 赋值 start1 = end2+1; end1 = start1 + gap-1; start2 = end1+1; end2 = start2 + gap-1 < array.length-1 ? start2 + gap-1 : array.length-1; } while (start1 < array.length){ tmp[i++] = array[start1++]; } System.arraycopy(tmp,0,array,0,array.length); }基数排序 1.基数排序基本思想：
基数排序是这样一种排序算法，我们可以从低位（个位）开始，根据个位数排序一次，然后根据十位数排序，再根据百位数进行排序……最终完成整个数组的排序。 对于十进制数字而言，每一位只会是 0~9 这十个数字，我们通常使用桶排序（计数排序）来完成每一位数的排序。桶排序是一种稳定的排序算法，基数排序的正确性依赖一种稳定的排序算法。 基数排序其实是分 LSD(从低位向高位排序) 和 MSD(从高位向低位排序) 两种。
2.时间复杂度：
基数排序的时间复杂度为 O(n)。 基数排序使用桶排序对其每一位进行排序，即每一位的排序时间复杂度为 O(n)，假设最大的数有 digit 位，则共需要进行 digit * O(n) 次排序。时间复杂度依旧为 O(n)。
3.画图示意：
