6个经典数据结构JAVA解法.rar_数据结构 java

/** * 简单排序---冒泡和选择、插入排序 */ public class SimpleSort { //定义私有属性数组 private int[] array; int nElems; /** * 构建器/ * 初始化方法,给类属性赋值 * @param int[] array */ public SimpleSort(int[] array){ this.array = array; nElems = array.length; } /** * 交换值的方法 * @param int i * @param int j */ protected void swap(int i,int j) { int c; c = array[i]; array[i] = array[j]; array[j] = c; } /** * 冒泡排序 * 规则: 1. 比较相邻的两个数； * 2. 如果左边的数大，则交换两个数； * 3. 右移一位，转1； * 4. 当碰到最近一个排定的数后，返回队列左端重新开始下一趟排序。直到所以数都排定。 */ public void bubbleSort(){ int out, in; for (out = nElems - 1; out > 0; out--) { // outer loop(backward) for (in = 0; in < out; in++) { // inner loop(forward) System.out.println(" "); System.out.println(in+" ============================= "); System.out.print(array[in]+" "); if (array[in] > array[in + 1]) { // out of order? System.out.println(in+": "+array[in]+" "+array[in + 1]+" "); swap(in, in + 1); // swap them System.out.println(" "); System.out.println(in+": "+array[in]+" "+array[in + 1]+" "); } // end if System.out.println(array[in]+" "); System.out.println(" "); } // end inner loop System.out.println((out+1)+": after sort is : "); for (int i = 0;i < nElems;i++) { System.out.print(" " + array[i] + " "); } } // end outer loop } // end bubbleSort() /** * 选择排序 * 规则: 1. 扫描全部数据一趟，将最小值与第0个位置上的数据交换； * 2. 扫描除第0个位置外的剩下数据，将最小值与第1个位置上的数据交换； * 3. 依此类推，直至全部数据排列有序。 */ public void selectSort() { int out, in, min; for (out = 0; out < nElems-1; out++) { // outer loop min = out; // minimum for (in = out + 1; in < nElems; in++) { // inner loop if (array[in] < array[min]) { // if min greater, min = in; // we have a new min } } // end for (in) swap(out, min); // swap them System.out.println(" "); System.out.println((out+1)+": after sort is : "); for (int i = 0;i < nElems; i++) { System.out.print(" " + array[i] + " "); } } // end for (out) } // end selectionSort() /** * 选择排序 * 规则: 从数组下标为1的数据开始，依次将其与自身左边的全部或部分数据（部分有序序列）进 * 行比较，并插入到适当的位置，使得插入后的序列依然保持部分有序。 * 直至操作完最后一个数据为止。 */ public void insertSort() { int in, out; for (out = 1; out < nElems; out++) { // out is dividing line int temp = array[out]; // remove marked item System.out.println(""); System.out.println("-------------- "+out+"---------------"); System.out.println("temp==== "+temp); in = out; // start shifts at out System.out.println("in==== "+in); while (in>0 && array[in-1] >= temp) { // until one is smaller, array[in] = array[in-1]; // shift item right, System.out.println(" "); System.out.println((out)+": after sort is : "); for (int j = 0;j < nElems; j++) { System.out.print(" " + array[j] + " "); } --in; // go left one position } System.out.println(" "); System.out.println("temp======= "+temp); array[in] = temp; // insert marked item System.out.println("in======= "+in); System.out.println(" "); System.out.println((out)+": after sort is : "); for (int i = 0;i < nElems; i++) { System.out.print(" " + array[i] + " "); } } } // end insertionSort() /** * 主函数，测试。 * @param String[] args */ public static void main(String[] args) { // bubbleSort run test int[] test1 = {61,20,150,55,56,70,100,10,55}; SimpleSort simpleSort1 = new SimpleSort(test1); simpleSort1.bubbleSort(); System.out.println(" "); System.out.println(" test1 array after sort is : "); for(int i = 0;i<test1.length;i++){ System.out.print(" " +test1[i]+" "); } // selectSort run test System.out.println(" "); System.out.println(" ======================================= "); int[] test2 = {61,15,55,5,170,100,101,35}; SimpleSort simpleSort2 = new SimpleSort(test2); simpleSort2.selectSort(); System.out.println(" "); System.out.println(" test2 array after sort is : "); for(int j = 0;j<test2.length;j++){ System.out.print(" " +test2[j]+" "); } // insertSort run test System.out.println(" "); System.out.println(" ======================================= "); int[] test3 = {66,15,53,5,10,111,91,12}; SimpleSort simpleSort3 = new SimpleSort(test3); simpleSort3.insertSort(); System.out.println(" "); System.out.println(" test3 array after sort is : "); for(int n = 0;n<test3.length;n++){ System.out.print(" " +test3[n]+" "); } } }