simplesort.java

6个经典数据结构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]+" ");
        }
    }
}