一、常见排序列表

常见排序列表

重点：插入排序、堆排序、并归排序、快速排序

Java的Collections.sort算法调用的是归并排序

二、冒泡排序算法

/**
 * 冒泡排序算法
 * @author AC
 */
public class Bubble {
    
    /**
     * {3,1,5,6,9,8,7,2,4}
     * 冒泡算法特点：
     * 像气泡一样，一个气泡一个气泡往上冒；一个数一个数的往右排。
     * 上面的气泡最大，下边的气泡最小；右边的数最大，左边的数最小。
     */
    public void sort(int[] arry) {
        for(int k = arry.length-1;k>0;k--) {
            for(int i =0;i<k;i++) {
                if(arry[i]>arry[i+1]) {
                    swap(i,i+1,arry);
                }
            }
        }   
    }
    
    public void swap(int indexA,int indexB,int []arry) {
        int temp =arry[indexB];
        arry[indexB] = arry[indexA];
        arry[indexA] = temp;
    }
}

排序太慢，基本不用

三、选择排序算法

/**
 * 选择排序算法
 * @author AC
 */
public class Selection {

    /**
     * {3,1,5,6,9,8,7,2,4}
     * 选择排序特点:选出最大值的下标
     * 内循环选（找）出当前循环中最大值的下标，把最大值下标位置的值和最后位置的值交换
     */
    public void sort(int[] arry) {
        for(int k = arry.length-1;k>0;k--) {
            int maxIndex = 0;
            for(int i=0;i<k;i++) {
                if(arry[maxIndex]<arry[i+1]) {
                    maxIndex = i+1;
                }
            }
            swap(maxIndex,k,arry);
        }   
    }
    
    public void swap(int indexA,int indexB,int []arry) {
        int temp =arry[indexB];
        arry[indexB] = arry[indexA];
        arry[indexA] = temp;
    }
}

排序不稳，基本不用

四、插入排序算法

/**
 * 插入排序算法
 * @author AC
 */
public class Insertion {
    
    /**
     * {3,1,5,6,9,8,7,2,4}
     * 插入排序:像打牌时插牌一样，抓一张新牌，就把它插在合适的位置
     */
    public void sort(int[] arry) {
        for(int k = 1;k<arry.length;k++) {
            for(int i = k;i>0;i--) {
                if(arry[i]<arry[i-1]) {
                    swap(i,i-1,arry);
                }
            }
        }
    }
    
    public void swap(int indexA,int indexB,int []arry) {
        int temp =arry[indexB];
        arry[indexB] = arry[indexA];
        arry[indexA] = temp;
    }
}

样本小组基本有序时候效率比较高