命名有点不规范请各位体谅。
1交互 排序 冒泡 和 快速排。
数据的代码的数据互换。
package paixu; import java.lang.reflect.Field; import java.util.Random; /** * 数据交互 * @author MZFAITHDREAM * */ public class 数据互换 { public static void main(String[] args) { // TODO Auto-generated method stub int[] m = { 1, 5, 4, 6, 7, 4, 5, 8, 56, 45 }; for (int i = 0; i < m.length; i++) { int k = i; for (int j = i + 1; j < m.length; j++) { if (m[j] < m[k]) { k = j; //互换数据 int temp = m[j]; m[j] = m[i]; m[i] = temp; } } } for (int i = 0; i < m.length; i++) { System.out.println(m[i] + " "); } new 数据互换().one(); new 数据互换().Two(); new 数据互换().Tree(); new 数据互换().frou(); new 数据互换().six(); } private void six() { // 第六种方案 想必大家已经学了四种方法，已经对两个数互换信心满满，那么接下来，我们来看一道面试题： Integer a = 10; Integer b = 20; swop(a, b); // 打印结果：a = 20, b = 10 System.out.println("a = " + a + ", b = " + b); } private static void swop(Integer a, Integer b) { // 完成此处代码 //我会想到异或运算 a = a ^ b; // 此时, a == a ^ b b = a ^ b; // b == a ^ b ^ b == a, 此时b == a a = a ^ b; // a == a ^ b ^ a == b, 此时a == b //思考为什么没数据没有交换 System.out.println("交换后：a = " + a + ", b = " + b); System.out.println("whywhywhywhy"); System.out.println("这是跟java设计模式有关 java的24种设计模式"); a = b + (b = a) * 0; // a == b + a * 0 == b, a == b System.out.println("交换后: a = " + a + ", b = " + b); //如何用 } private void frou() { //如a ^ b，若a、b两个值不同，则异或结果为1; //若a、b两个数相同，则异或结果为0。 不同为一相同为0 /** * 分别把结果以二进制的形式输出 * */ System.out.println("3的二进制：" + Integer.toBinaryString(3)); System.out.println("4的二进制：" + Integer.toBinaryString(4)); System.out.println("3 ^ 3 的二进制：" + Integer.toBinaryString(3 ^ 3)); System.out.print("3 ^ 0 的二进制：" + Integer.toBinaryString(3 ^ 0)); if (3 == (3 ^ 0)) System.out.println(",也就是十进制的3"); System.out.print("4 ^ 3 ^ 3 的二进制：" + Integer.toBinaryString(4 ^ 3 ^ 3)); if (4 == (4 ^ 3 ^ 3)) System.out.println(",也就是十进制的4"); } private void Tree() { System.out.println("方案三"); /** * 随机生成两个0-100之间的整数， * 其中Math.random()会生成[0-1)之间任意的double类型的数 * 因此101表示生成的数范围区间在：[0-101) */ int a = (int) (Math.random() * 101); int b = (int) (Math.random() * 101); System.out.println("交换前: a = " + a + ", b = " + b); a = b + (b = a) * 0; // a == b + a * 0 == b, a == b System.out.println("交换后: a = " + a + ", b = " + b); } private void Two() { /** * 贪心 * 不借助第三个变量进行数据 */ Random random = new Random(48); int a = random.nextInt(101); int b = random.nextInt(101); System.out.println("交换前的数据：a = " + a + ", b = " + b); five(); a = a + b; // a == a + b b = a - b; // b == a + b - b == a, 此时b == a a = a - b; // a == a + b - a == b, 此时a == b System.out.println("交换后的数据：a = " + a + ", b = " + b); } private void five() { System.out.println("调用five方法"); Random random = new Random(48); int a = random.nextInt(101); int b = random.nextInt(101); System.out.println("--------------------------------------------异或运算"); a = a ^ b; // 此时, a == a ^ b b = a ^ b; // b == a ^ b ^ b == a, 此时b == a a = a ^ b; // a == a ^ b ^ a == b, 此时a == b System.out.println("交换后：a = " + a + ", b = " + b); } /** * 八种方案交换数据 * 方案一 */ public void one() { int a=123; int b=789; System.out.println("输入"+a); System.out.println("输入"+b); System.out.println("a与b的数据进行交换"); // 定义空的字符串 if(a>b) { System.out.println("a的值最大·"+a); }else { int t = a; // t == a a = b; // a == b b = t; // b == t == a System.out.println(a); System.out.println(b); } } }
运行结果
冒泡排序
package paixu; import java.util.Arrays; /** * 冒泡排序 * @author MZFAITHDREAM * */ public class 冒泡排序 { /** * 1. 相邻两个数两两相比，n[i]跟n[j+1]比，如果n[i]>n[j+1]，则将连个数进行交换， 2. j++, 重复以上步骤，第一趟结束后，最大数就会被确定在最后一位，这就是冒泡排序又称大（小）数沉底， 3. i++,重复以上步骤，直到i=n-1结束，排序完成。 * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] n = new int[]{100,55,66,77,88}; int temp; for (int i = 0; i < n.length-1; i++) { for (int j = 0; j <n.length-1; j++) { if(n[j]>n[j+1]){ temp = n[j]; n[j] = n[j+1]; n[j+1] = temp; } } } System.out.println("冒泡排序的思想是两个两个比较大的在后面小的在前面"); System.out.println(Arrays.toString(n)); } }
package paixu; import java.util.Arrays; public class 快速排序 { /* * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[]{10,6,3,8,33,27,66,9,7,88}; // f(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void f(int[] arr,int start,int end){ //直到start>=end时结束递归 if(start<end){ int left = start; int right = end; int temp = arr[start]; while(left<right){ //右面的数字大于标准数时，右边的数的位置不变，指针向左移一个位置 while(left<right && arr[right]>temp){ right--; } //右边的数字及下标小于或等于基本数，将右边的数放到左边 if(left<right) { arr[left] = arr[right]; left++; } // 左边的数字小于或等于标准数时，左边的数的位置不变，指针向右移一个位置 while(left<right && arr[left]<=temp){ left++; } //左边的数字大于基本数，将左边的数放到右边 arr[right] = arr[left]; } //一趟循环结束，此时left=right，将基数放到这个重合的位置， arr[left] = temp; //将数组从left位置分为两半，继续递归下去进行排序 f(arr,start,left); f(arr,left+1,end); } } }
2 插入排序 希尔 与插入。
package paixu; import java.util.Arrays; public class 插入排序 { public static void main(String[] args) { int[] n = new int[]{55,66,77,88,99100}; int temp = 0,j; for (int i = 1; i < n.length; i++) { temp = n[i]; for (j = i; j >0; j--) { //如果当前数前面的数大于当前数，则把前面的数向后移一个位置 if(n[j-1]>temp){ n[j] = n[j-1]; //第一个数已经移到第二个数，将当前数放到第一个位置，这一趟结束 if(j==1){ n[j-1] = temp; break; } }else{//如果不大于，将当前数放到j的位置，这一趟结束 n[j] = temp; break; } } System.out.println(Arrays.toString(n)); } System.out.println(Arrays.toString(n)); }
希尔
package paixu; import java.util.Arrays; public class 希尔排序{ /** * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐 * 渐减少，每组包含的关键词越来越多，当增量减至 * 1时，整个文件恰被分成一组，算法便终止。 简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动， 插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲， 比较和移动元素均需n-1次。 而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后 分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这 种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时， 其实多数情况下只需微调即可，不会涉及过多的数据移动。 来看下希尔排序的基本步骤，在此选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处做示例使用希尔增量。 * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[]{10,6,3,8,33,27,66,9,7,88}; shellSort(arr); System.out.println(Arrays.toString(arr)); } private static void shellSort(int[] arr) { int temp; //控制增量序列,增量序列为1的时候为最后一趟 for (int i = arr.length/2; i >0; i/=2) { //根据增量序列，找到每组比较序列的最后一个数的位置 for (int j = i; j < arr.length; j++) { //根据该比较序列的最后一个数的位置，依次向前执行插入排序 for (int k = j-i; k >=0; k-=i) { if(arr[k]>arr[k+i]){ temp = arr[k]; arr[k] = arr[k+i]; arr[k+i] = temp; } } } } } }
3选择排序 选择排序 推排序。
package paixu; import java.util.Arrays; import java.util.Scanner; public class 选择排序 { /** * 1.选择排序 * 1. 第一个跟后面的所有数相比，如果小于（或小于）第一个数的时候，暂存较小数的下标，第一趟结束后，将第一个数，与暂存的那个最小数进行交换，第一个数就是最小（或最大的数） 2. 下标移到第二位，第二个数跟后面的所有数相比，一趟下来，确定第二小（或第二大）的数 重复以上步骤 直到指针移到倒数第二位，确定倒数第二小（或倒数第二大）的数，那么最后一位也就确定了，排序完成 * @param args */ /** * * @paraargs */ public static void main(String[] args) { // 创建Scanner对象随机输入六个数进行选择排序 Scanner sc=new Scanner(System.in); System.out.println("选择排序的思想遍历一遍后将将最小的一个数排在第一位"); System.out.println("请输入第一个数"); int a=sc.nextInt(); System.out.println("请输入第二个数"); int b=sc.nextInt(); System.out.println("请输入第三个数"); int c=sc.nextInt(); System.out.println("请输入第四个数"); int d=sc.nextInt(); System.out.println("请输入第五个数"); int f=sc.nextInt(); System.out.println("请输入第六个数"); int e=sc.nextInt(); int []arr={a,b,c,d,e,f}; for (int i = 0; i < arr.length -1; i++) { //第一次遍历选择最小的元素 int minpos=i; for (int j = i+1; j < arr.length; j++) { minpos =arr[j] <arr[minpos] ?j:minpos; } System.out.println("minpose:"+minpos); swap(arr, i, minpos); System.out.println("经过第"+i+"次循环之后，数据内容"); print(arr); } } static void swap(int[] arr,int i,int j ) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } static void print (int [] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }
推排序 二叉树
package paixu; /** * 二叉数 * @author MZFAITHDREAM * 先序 根 left right * 中序 left 中 right * 后序 left right 中 * */ public class 二叉树 { /** * 树的遍历 * @param args */ /** * 先序 * @param arr * @param index */ static void preOrdwr (int[] arr,int index) { if(index>=arr.length) return; // 先输出根节点 System.out.println(arr[index]); // 输出为left preOrdwr(arr, index*2+1); System.out.println(arr[index]); preOrdwr(arr, index*2+2); } /** * 中序 * @param arr * @param index */ static void inOrder (int[] arr,int i) { if(i>=arr.length) return; // 输出left inOrder(arr, i*2+1); System.out.println(arr[i]); // 先输出根节点 // 输出为right inOrder(arr, i*2+2); } public static void main(String[] args) { // 声明一维数组 int [] arr= {36,47,48,54,33,5,89,5,37,94,5,79,49}; preOrdwr(arr, 0); System.out.print("==============="); inOrder(arr, 0); } }
package paixu; import java.util.Arrays; /** * 转换为伪代码 * @author MZFAITHDREAM *以计算机为中心递归 *考虑边界的问题 *完善推排序 *left =2*i+1 *right=2* * 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆 *；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。 *大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] */ public class 推排序 { /** * 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种 * 选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)， * 它也是不稳定排序。首先简单了解下堆结构。堆 * @param args */ public static void main(String[] args) { // 声明一维数组 int [] arr= {9,8,7,6,5,4,3,2,1}; // 调用方法 sort(arr); System.out.println(Arrays.toString(arr)); } private static void sort(int[] arr) { //构建大顶推 for (int i = arr.length/2-1; i>=0; i--) { adjustHeap(arr, i, arr.length); } for (int j =arr.length-1;j>0; j--) { swap(arr, 0, j); adjustHeap(arr, 0, j); } } /** * 调动大顶推的过程 */ public static void adjustHeap(int []arr,int i,int length) { // 取出当前元素 int temp=arr[i]; // arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] for(int k=i*2+1;k<length;k=k*2+1) { if(k+1<length && arr[k]<arr[k+1]) { k++; } if(arr[k]>temp) { arr[i]=arr[k]; i=k; }else { break; } } //将temp值放在最终位置 arr[i]=temp; } /** * 元素开始交换 */ public static void swap(int [] arr,int a,int b) { int temp=arr[a]; arr[a]=arr[b]; arr[b]=temp; } }
4 归并排序
归并两个数组
package paixu; /** * 归并数组 */ import java.util.Arrays; public class 归并数组 { public static void main(String[] args) { int A[] = new int[12]; for (int i = 0; i < 7; i++) { A[i] = 2*i+1; } System.out.println("A数组："+Arrays.toString(A)); int B[] = new int[5]; for (int i = 0; i < B.length; i++) { B[i] = 3*i+1; } System.out.println("B数组："+Arrays.toString(B)); int []res = f(A,7,B,5); System.out.println("合并后的数组："+Arrays.toString(res)); } private static int[] f(int []A,int p, int B[],int r) { int current = p+r-1; p--; r--; while(p!=-1&&r!=-1){ if (A[p]>=B[r]) { A[current] = A[p]; current--; p--; }else { A[current] = B[r]; current--; r--; } } return A; } }
归并排序
package paixu; import java.util.Arrays; import java.util.Scanner; /** * /** * 归并排序就是递归得将原始数组递归对半分隔， * 直到不能再分（只剩下一个元素）后，开始从最小的数组向上归并排序 1. 向上归并排序的时候，需要一个暂存数组用来排序， 2. 将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移， 3. 直到一个数组空，这时，不用判断哪个数组空了，直接将两个数组剩下的元素追加到暂存数组里， 4. 再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束。 * @author MZFAITHDREAM * */ public class 归并排序 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc=new Scanner(System.in); System.out.println("归并排序"); System.out.println("请输入第一个数"); int a=sc.nextInt(); System.out.println("请输入第二个数"); int b=sc.nextInt(); System.out.println("请输入第三个数"); int c=sc.nextInt(); System.out.println("请输入第四个数"); int d=sc.nextInt(); System.out.println("请输入第五个数"); int f=sc.nextInt(); System.out.println("请输入第六个数"); int e=sc.nextInt(); int []arr={a,b,c,d,e,f}; merge(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } //归并 public static void merge(int[] arr,int low,int high){ int center = (high+low)/2; if(low<high){ //递归，直到low==high， 也就是数组已不能再分了， merge(arr,low,center); merge(arr,center+1,high); //当数组不能再分，开始归并排序 mergeSort(arr,low,center,high); System.out.println(Arrays.toString(arr)); } } //排序 public static void mergeSort(int[] arr,int low,int center,int high){ //用于暂存排序后的数组的临时数组 int[] tempArr = new int[arr.length]; int i = low, j = center+1; //临时数组的下标 int index = 0; System.out.println(index); //循环遍历两个数组的数字，将小的插入到临时数组里 while(i<=center && j<= high){ //左边数组的数小，插入到新数组 if(arr[i]<arr[j]){ tempArr[index] = arr[i]; i++; }else{//右边数组的数小，插入到新数组 tempArr[index] = arr[j]; j++; } index++; } //处理左半边数组多余的数据，将左半边多余的数据直接追加的临时数组的后面 while(i<=center){ tempArr[index] = arr[i]; i++; index++; } //处理右半边数组多余的数据，将右半边多余的数据直接追加的临时数组的后面 while(j<= high){ tempArr[index] = arr[j]; j++; index++; } //将临时数组中的数据重新放进原数组 for (int k = 0; k < index; k++) { arr[k+low] = tempArr[k]; System.out.println(tempArr[k]); } } }
5非比较排序 计数排序 桶排序 基数排序
计数排序
package paixu; import java.util.Arrays; public class 计数排序 { private static final int[] A1 = {100,93,97,92,96,99,92,89,93,97,90,94,92,95}; public int[] countSort() { int max = Integer.MIN_VALUE; for (int num : A1) { max = Math.max(max, num); } // 初始化计数数组count 设计一个新的数组 length=max+1 int[] count = new int[max+1]; // 对计数数组各元素赋值 for (int num : A1) { count[num]++; } // 创建结果数组 int[] result = new int[A1.length]; // 创建结果数组的起始索引 int index = 0; // 遍历计数数组，将计数数组的索引填充到结果数组中 for (int i=0; i<count.length; i++) { while (count[i]>0) { result[index++] = i; count[i]--; } } // 返回结果数组 return result; } public static void main(String[] args) { new 计数排序().countSort(); } }
桶排序
package paixu; import java.util.ArrayList; import java.util.List; /** * 桶排序 * @author MZFAITHDREAM * */ public class 桶排序 { public static void main(String[] args) { // 声明数组 int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24}; // 创建桶 List[] buckets=new ArrayList[5]; for(int i=0;i<buckets.length;i++)//初始化 { buckets[i]=new ArrayList<Integer>(); } for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中 { int index=a[i]/10;//对应的桶号 buckets[index].add(a[i]); } 每个桶内进行排序(使用系统自带快排) for(int i=0;i<buckets.length;i++) { buckets[i].sort(null); for(int j=0;j<buckets[i].size();j++)//顺便打印输出 { System.out.print(buckets[i].get(j)+" "); } } } }
基数排序
package paixu; import java.util.Arrays; /** * 基数排序 * @author MZFAITHDREAM * */ public class 基数排序 { * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[]{10,6,3,8,33,27,66,9,7,88}; radixSort(arr); } private static void radixSort(int[] arr) { //求出待排数的最大数 int maxLength=0; for (int i = 0; i < arr.length; i++) { if(maxLength<arr[i]) maxLength = arr[i]; System.out.println("遍历的次数"+i); } //根据最大数求最大长度 maxLength = (maxLength+"").length(); //用于暂存数据的数组 int[][] temp = new int[10][arr.length]; //用于记录temp数组中每个桶内存的数据的数量 int[] counts = new int[10]; //用于记录每个数的i位数 int num = 0; //用于取的元素需要放的位置 int index = 0; //根据最大长度决定排序的次数 for (int i = 0,n=1; i < maxLength; i++,n*=10) { for (int j = 0; j < arr.length; j++) { num = arr[j]/n%10; temp[num][counts[num]] = arr[j]; counts[num]++; System.out.println("开始的位置"+num); } //从temp中取元素重新放到arr数组中 for (int j = 0; j < counts.length; j++) { for (int j2 = 0; j2 < counts[j]; j2++) { arr[index] = temp[j][j2]; System.out.println(j2); index++; } counts[j]=0; } index=0; } System.out.println(Arrays.toString(arr)); } }
