java7种排序（需熟练掌握）

• • java7种排序算法
  • @[toc]
  • • 1.冒泡排序
    • 2.插入排序
    • 3.选择排序
    • 4.希尔排序
    • 5.归并排序
    • 6.快速排序
    • 7.基数排序（基于桶排序）

public void bubbleSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
            boolean flag=false;
            for (int j = 0; j array[j+1]){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                    flag=true;
                }
            }
            if (!flag){
                return;
            }
        }
    }

public void insertSort(int[] array){
        int insertValue=0;
        int index=0;
        for (int i = 1; i < array.length; i++) {
            //提取出要插入的数据
            insertValue=array[i];
            //放出哨兵向左移动检查可以插入的点
            index=i-1;
            while (index >=0&&insertValue 
 
3.选择排序 
public void selectSort(int[] array){
        for (int i = 0; i  
 
4.希尔排序 
public void shellSort(int[] array){
        //gap是步长
        //普通插入排序步长是一，这里的希尔插入排序步长不为一
        for (int gap = array.length/2; gap > 0; gap/=2) {
            //以下与插入排序唯一不同的是步长不为一
            int insertValue=0;
            int index=0;
            for (int i = gap; i < array.length; i++) {
                //提取需要插入的数据
                insertValue=array[i];
                //放出哨兵向前移动gap步长去检查可以插入的点
                index=i-gap;
                while (index>=0&&insertValue 
 
5.归并排序 
//借助另外的temp空间对每层分出来的部分进行治理（合并左右两个有序部分）
    public void merge(int[] array,int left,int mid,int right,int[] temp){
        int l=left;//左半部分头指针
        int r=mid+1;//右半部分头指针
        int t=0;//temp数组头指针
        while (l<=mid&&r<=right){
            //左右两边谁小谁进入temp数组
            if (array[l] 
 
6.快速排序 
//挖坑法
public void quickSort(int[] array,int left,int right){
        if (leftx){
                    //找到比基准数大的挖出，填最右边的坑，此处又形成了新的坑（左边）
                    array[r]=array[l];
                    r--;
                }
                while (l=x){
                    r--;
                }
                if (l 
 
7.基数排序（基于桶排序） 
public void radixSort(int[] array){
        //先获取最大的数的位数
        int max=array[0];
        for (int j : array) {
            if (j > max) {
                max = j;
            }
        }
        int maxLength=(max+"").length();

        //创建十个桶
        int[][] bucket=new int[10][array.length];
        //创建数组记录每个桶内的元素个数
        int[] bucketElementCounts=new int[10];
        for (int i = 0,n=1; i < maxLength; i++,n*=10) {
            //将原数组的数放入桶中
            for (int element : array) {
                int digitOfElement=element/n%10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]]=element;
                bucketElementCounts[digitOfElement]++;
            }
            //将十个桶中的数放入原数组，实现原数组的更新
            int index=0;
            for (int j = 0; j < 10; j++) {
                if (bucketElementCounts[j]!=0){
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        array[index++]=bucket[j][k];
                    }
                }
                bucketElementCounts[j]=0;
            }
        }
    }