Java基础面试题3(排序算法)

1、冒泡排序：和快速排序一样属于交换排序的一种

public class Sort{

    public void generatArray(int [] array){
        Random random = new Random();
        for (int i=0;i<array.length;i++) {
            array[i]=random.nextInt(100);
        }
        for (int a : array) {
            System.out.print(a+",");
        }
        System.out.println();
    }
    
    public void bubbleSort(int [] array){
        int tmp;
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                }
            }
        }
        for (int a : array) {
            System.out.print(a+",");
        }
        System.out.println();
    }
    
    public static void main(String args[]){
        Sort sort = new Sort();
        int array[]=new int[10];
        sort.generatArray(array);
        sort.bubbleSort(array);
    }
}

2、快速排序：是对冒泡排序的改进

public class Sort{

    public void generatArray(int [] array){
        Random random = new Random();
        for (int i=0;i<array.length;i++) {
            array[i]=random.nextInt(100);
        }
        for (int a : array) {
            System.out.print(a+",");
        }
        System.out.println();
    }
    
    public void quickSort(int [] array,int l,int r){
        if(l>=r)
            return;
        int k = array[l];
        int i =l,j=r;
        while(i<j){
            while(i<j && k<array[j])
                j--;
            if(i<j){
                array[i]=array[j];
                i++;
            }
            while(i<j&&k>array[i])
                i++;
            if(i<j){
                array[j]=array[i];
                j--;
            }
        }
        array[i]=k;
        quickSort(array,l,i-1);
        quickSort(array,i+1,r);
    }
    
    public static void main(String args[]){
        Sort sort = new Sort();
        int array[]=new int[10];
        sort.generatArray(array);
        sort.quickSort(array, 0, array.length-1);
        for (int a : array) {
            System.out.print(a+",");
        }
        System.out.println();
    }
}

3、插入排序：

public class Sort{

    public void insertSort(int [] array){
        for(int i=1;i<array.length;i++){
            int tmp = array[i];
            int  j;
            for(j=i;j>0 && array[j-1]>tmp;j--)
                array[j]=array[j-1];
            array[j]=tmp;
        }
        
        for (int a : array) {
            System.out.print(a+",");
        }
        System.out.println();
    }
    
    public static void main(String args[]){
        Sort sort = new Sort();
        int array[]=new int[10];
        sort.generatArray(array);
        sort.insertSort(array);
    }
}

Java基础面试题3(排序算法),布布扣,bubuko.com

Java基础面试题3(排序算法)

原文：http://blog.csdn.net/heqiangflytosky/article/details/22102255