应聘中经常考得排序详解.doc

/* * author Administrator * 冒泡排序的算法 * 比较n轮，每一轮都把最大元素移动到数组后端 */public class Maopaosort private static int count = 0;public static void Sort(int a) int temp = 0;int i = 0, j = 0;for (i = 1; i a.length; i+) /找到最大值for (j = 0; j aj + 1) / 这里的“”号决定了最后是升序，“”则是降序temp = aj + 1;/ temp仅做暂存单元aj + 1 = aj;aj = temp;printAll(a);printAll(a);/ 打印结果public static void printAll(int a) System.out.println(第 + (+count) + 次：);for (int i = 0; i a.length; i+) System.out.print(ai + );System.out.println();public static void main(String args) / 定义一个整型的数组int Data = new int10;for (int i = 0; i Data.length; i+) Datai = (int) (Math.random() * 100);/ 取得的数据在0到100之间不包括0System.out.println(排序之前：);for (int i : Data) System.out.print(i + );System.out.println();System.out.println(排序之后：);Sort(Data);/* * author Administrator *插入排序的思想 *从第二个元素开始，因为左侧的数组为排序后的数组， *只要将当前元素插入到左侧数组的适当位置，就能保持数组为有序 *然后处理第三个元素.直到最后一个元素 */public class Insertsort private static int count = 0;public static void printAll(int a) System.out.println(第 + (+count) + 次：);for (int i = 0; i a.length; i+) System.out.print(ai + );System.out.println();public static void Sort(int data) /从第二个元素开始for (int i = 1; i 0; j-) if (dataj - 1 dataj) int temp = 0;temp = dataj - 1;dataj - 1 = dataj;dataj = temp;printAll(data);/ printAll(data);/ 打印结果public static void main(String args) int data = new int10;for (int i = 0; i data.length; i+) datai = (int) (Math.random() * 100);System.out.println(排序之前：);for (int i : data) System.out.print(i + );System.out.println();System.out.println(排序之后：);Sort(data);/* * author Administrator * 简单选择排序的思想 * 每遍历未排序部分一次都产生一个最小值，并将最小值移到数组的前端 */public class Simpleselectionsort private static int count = 0;public static void printAll(int a) System.out.println(第 + (+count) + 次：);for (int i = 0; i a.length; i+) System.out.print(ai + );System.out.println();public static void Sort(int data) for(int i=0;idata.length;i+)int minindex=i;for(int j=i+1;jdata.length;j+)/遍历未排序部分产生一个最小值if(datajdataminindex)/记录最小值的角标minindex=j;/将得到的最小值移到数组的前端swap(data,minindex,i);printAll(data);public static void swap(int data, int minindex, int i) int temp =0;temp =dataminindex;dataminindex=datai;datai=temp;public static void main(String args) int data = new int10;for (int i = 0; i data.length; i+) datai = (int) (Math.random() * 100);System.out.println(排序之前：);for (int i : data) System.out.print(i + );System.out.println();System.out.println(排序之后：);Sort(data);/* * author Administrator * 快排的算法 * param pData 需要排序的数组 * param left 左边的位置,初始值为0 * param right 右边的位置,初始值为数组长度 * 选择数组中的一个元素作为标准，将所有比标准小的元素放到左边， * 所有比标准大的元素放到右边。 * 并对左边和右边的元素做一样的快速排序过程。 */ public class Qsort public static void QuickSort(int pData, int left, int right) int i, j;int k = 0;int middle, temp;i = left;j = right;middle = pDataleft;while (true) while (+i) right - 1 & pDatai left & pDataj middle);System.out.println(i + , + j);if (i = j)break;temp = pDatai;pDatai = pDataj;pDataj = temp;pDataleft = pDataj;pDataj = middle;for (k = 0; k pData.length; k+) System.out.print(pDatak + );System.out.println();if (left i)QuickSort(pData, i, right);public static void main(String args) int pData = new int10;for (int i = 0; i 10; i+)pDatai = (int) (Math.random() * 100);for (int i = 0; i pData.length; i+) System.out.print(pDatai + );System.out.println();Qsort.QuickSort(pData, 0, pData.length);System.out.println(n*);for (int i = 0; i =leftIndex)/如果要找的数比midVal大if(midValval)/在arr左边数中找find(leftIndex,midIndex-1,val,arr);else if(midValval)/在arr的右边去查找find(midIndex+1,rightIndex,val,arr);else if(midVal=val)System.out.println(找到下标+midIndex);elseSystem.out.println(没有该数!);public static void main(String args) /int arr=0,1,2,3,4,5,6,7,8;/int temp=0;/排序/外层循环,它决定一共走几趟int arr=new int10;for (int i = 0; i 10; i+) /arri=(int)(Math.random()*10);arri=i*10;/Arrays.sort(arr);for (int i = 0; i arr.length; i+) System.out.print(arri+t);find(0,arr.length-1,900,arr); /* * author lcc *归并排序(双数组) *归并排序中的“归并”的意思是将两个或者两个以上的有序表组合成一个新的有序表。他的实现无论是顺序存储结构还是链表结构，都可以在O(m+n)的时间级上实现。 *复杂度： *时间复杂度：O(nlogn) *空间复杂度：O(n) *在实现单数组的归并排序之前，首先了解一下双数组的归并排序 *这个双数组归并的前提是两个数组a和b都是已经排序好的 */public class Test1 public static void main(String args) int a=1,2,3,4,6,7,8,10; int b=1,2,5,9; int c = new inta.length+b.length; mergeSort(a,a.length,b,b.length,c); System.out.println(Arrays.toString(c); public static void mergeSort(int a,int n,int b,int m,int c) int i,j,k; i=j=k=0; /只有满足in&jm才执行，分别扫描两个数组，将数组中的元素进行对比，从小到大赋值给临时数组c while(in&jm) if(aibj) ck+=ai+; else ck+=bj+; /将剩余的a数组的元素放入c中 while(in) ck+=ai+; /将剩余的b数组的元素放入c中 while(jm) ck+=bj+; /* * author lcc *下面开始实现单数组的归并排序算法 *思想：首先将数组中个单独的一个元素作为一个已经排序好的序列，然后，将两两相邻的元素进行归并排序，依次类推，直到最后归并为一个排序好的序列 */如上图：首先将每个元素作为一个已经排序好的序列，一共7个序列然后，将每两个相邻的序列归并为一个序列，如49 38归并排序后变成 38 49，依次分成了4个序列，然后再将之前已经排序好的两个相邻的序列进行排序，变成2个序列，每个序列都是排序好的，最后归并为一个排序好的序列public class MergeSort public static void main(String args) int array = 49,38,65,97,76,13,27; System.out.println(Arrays.toString(array); System.out.println(-排序前-); mergeSort(array,0,array.length-1); System.out.println(-排序后-); System.out.println(Arrays.toString(array); /* * 这里依然需要递归来达到数组元素的排序，如果有两个已有元素的数组的话，就不用这么麻烦您了 * 不过这种归并排序依然是效率最好的排序方法之一，而且还是稳定的（相比快速排序，快速排序不稳定） */ public static void mergeSort(int array,int low,int high) if(lowhigh) mergeSort(array,low,(low+high)/2);/左边排序 mergeSort(array,(low+high)/2+1,high);/右边排序 merge(array,low,(high+low)/2,high);/将两个序列归并为一个序列 System.out.println(Arrays.toString(array); public static void merge(int array,int low,int mid,int high) int temp=new inthigh-low+1; int i = low; int j = mid+1; int k=0; /* * 将arra