第一个选择排序：想想是先找最大的值，以此类推。如果有五个数他要循环4遍，如果有n个数，他要循环n-1次，效果很低。
package a; /** * 选择排序 * @author MZFAITHDREAM *n^2 */ public class Arrayxz { public static void main (String[] args) { int[] arr= {55,82,59,45,532}; for (int i = 0; i < arr.length -1; i++) { int maxpos=i; for (int j = i+1; j < arr.length; j++) { maxpos =arr[j] >arr[maxpos] ?j:maxpos; } System.out.println("minpose:"+maxpos); swap(arr, i, maxpos); 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 a; import java.util.Scanner; /** * 12/6用冒泡方式解决 * @author MZFAITHDREAM *键盘输入5个整数 要求使用冒泡排序将这5个整数从大到小进行排 *序并输出排序后的结果 */ public class EngA { public static void main(String[] args) { Scanner sc=new Scanner(System.in); 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 e=sc.nextInt(); int []array={a,b,c,d,e}; for(int i=0;i<(array.length-1);i++) { for(int j=i+1;j<array.length;j++) { if(array[i]>array[j]) { int z=array[i]; array[i]=array[j]; array[j]=z; }else { } } } System.out.println("从小到大："+array[0]+" "+array[1]+" "+array[2]+" "+array[3]+" "+array[4]); } static void print (int [] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } }
第三种排序方式归并排序。
package com.shuzu; import java.util.Arrays; public class Sor5 { * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr = new int[]{3,6,4,7,5,2}; 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; //循环遍历两个数组的数字，将小的插入到临时数组里 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]; } } }
1. 向上归并排序的时候，需要一个暂存数组用来排序，
2. 将待合并的两个数组，从第一位开始比较，小的放到暂存数组，指针向后移，
3. 直到一个数组空，这时，不用判断哪个数组空了，直接将两个数组剩下的元素追加到暂存数组里，
4. 再将暂存数组排序后的元素放到原数组里，两个数组合成一个，这一趟结束。
第四种方式快速排序。
package com.shuzu; import java.util.Arrays; public class Sor4 { 根据思路分析，第一趟的执行流程如下图所示： * @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}; // int[] arr = new int[]{1,3,2}; 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); } } }
第五种 希尔排序
package com.shuzu; import java.util.Arrays; public class Sor7 { /** * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐 * 渐减少，每组包含的关键词越来越多，当增量减至 * 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; } } } } } }
第六种堆排序
package com.shuzu; import java.util.Arrays; /** * 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就 * 是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重 * 新构造成一个堆，这样会得到n个元素的次小值。 * 如此反复执行，便能得到一个有序序列了 * @author MZFAITHDREAM * */ public class Sor28 { public static void main(String[] args) { int[] arr = new int[]{4,6,8,5,9}; int length = arr.length; //从最后一个非叶节点开始构建大顶堆 for (int i = arr.length/2-1; i >=0; i--) { maximumHeap(i,arr,length); } //从最小的叶子节点开始与根节点进行交换并重新构建大顶堆 for (int i = arr.length-1; i >=0; i--) { // System.out.println(Arrays.toString(arr)); swap(arr,0,i); length--; maximumHeap(0,arr,length); } System.out.println(Arrays.toString(arr)); } //构建大顶堆 public static void maximumHeap(int i,int[] arr,int length){ int temp = arr[i]; for (int j = i*2+1; j < length; j=j*2+1) { //如果右孩子大于做孩子，则指向右孩子 if(j+1<length && arr[j+1]>arr[j]){ j++; } //如果最大的孩子大于当前节点，则将大孩子赋给当前节点，修改当前节点为其大孩子节点，再向下走。 if(arr[j]>temp){ arr[i] = arr[j]; i = j; }else{ break; } } //将temp放到最终位置 arr[i] = temp; } //交换 public static void swap(int[] arr,int i,int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
第7种方式基数排序。
package com.shuzu; import java.util.Arrays; public class sor3 { /** * 基数排序第i趟将待排数组里的每个数的i位数放到tempj（j=1-10）队列中，然后再从这十个队列中取出数据，重新放到原数组里，直到i大于待排数的最大位数。 1.数组里的数最大位数是n位，就需要排n趟，例如数组里最大的数是3位数，则需要排3趟。 2.若数组里共有m个数，则需要十个长度为m的数组tempj（j=0-9）用来暂存i位上数为j的数，例如，第1趟，各位数为0的会被分配到temp0数组里，各位数为1的会被分配到temp1数组里...... 3.分配结束后，再依次从tempj数组中取出数据，遵循先进先进原则，例如对数组{1，11，2，44，4}，进行第1趟分配后，temp1={1,11}，temp2={2}，temp4={44，4}，依次取出元素后{1，11，2，44，4}，第一趟结束 4.循环到n趟后结束，排序完成 1. 时间复杂度： 每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。 假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。 系数2可以省略，且无论数组是否有序，都需要从个位 * @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]; } //根据最大数求最大长度 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]++; } //从temp中取元素重新放到arr数组中 for (int j = 0; j < counts.length; j++) { for (int j2 = 0; j2 < counts[j]; j2++) { arr[index] = temp[j][j2]; index++; } counts[j]=0; } index=0; } System.out.println(Arrays.toString(arr)); } }
重点在思想上的领悟。
