Java中几种排序算法-蒲公英云

1、冒泡排序算法
通过多次比较（相邻两个数）和交换来实现排序

public class bubble { 
    public static void bubbleSort(int[] a) { 
         int temp;
         for (int i = 1; i < a.length; i++) { 
              //将相邻两个数进行比较，较大的数往后冒泡
              for (int j = 0; j < a.length - i; j++) { 
                  if (a[j] > a[j + 1]) { 
                   //交换相邻两个数
                      temp=a[j];
                      a[j]=a[j+1];
                      a[j+1]=temp;
                  }
              }
         }
     } 
    public static void main(String[] args) { 
        int[] mao= { 213,123,342,543,12,67,98,320,421,4,15,54,27,34,17};
        System.out.print("排序前的数组为：\n");  //输出排序前的数组
        for(int i=0;i<mao.length;i++)
        { 
            System.out.print(mao[i]+" ");
        }
        System.out.print("\n");
        bubbleSort(mao);                    //排序操作
        System.out.print("排序后的数组为：\n");
        for(int i=0;i<mao.length;i++)
        { 
            System.out.print(mao[i]+" ");  //输出排序后的数组
        }
        System.out.print("\n");
    }
}

2、直接插入排序
通过对未排序的数据执行逐个插入至合适的位置而完成排序

public class straight{ 
    public static void straightInsertion(int[] arr) { 
        int current;//要插入的数
        //从1开始第一次一个数不需要排序
        for (int i = 1; i < arr.length; i++) { 
            current = arr[i];
            int j = i - 1;    //序列元素个数
            //从后往前循环，将大于当前插入数的向后移动
            while (j >= 0 && arr[j] > current) { 
                arr[j + 1] = arr[j];  //元素向后移动
                j--;
            }
            arr[j + 1] = current;  //找到位置，插入当前元素
        }
    }
}

3、快速选择排序
通过多次比较和交换来实现排序。首先设定一个分界值，将所有数值与分界值比较，左小右大，比较和交换数据值进而完成排序

public class quick{ 
    static void quickSort(int[] arr,int left,int right)    { 
        int f,t,rtemp,ltemp;
        ltemp=left;
        rtemp=right;
        f=arr[(left+right)/2];        //分界值
        while(ltemp<rtemp)
        { 
            while(arr[ltemp]<f)
            { 
                ++ltemp;
            }
            while(arr[rtemp]>f) 
            { 
                --rtemp;
            }
            if(ltemp<=rtemp)
            { 
                t=arr[ltemp];
                arr[ltemp]=arr[rtemp];
                arr[rtemp]=t;
                rtemp--;
                ltemp++;
            }
        }
        if(left<rtemp) 
        { 
            quickSort(arr,left,ltemp-1);        //递归调用
        }
        if(ltemp<right) 
        { 
            quickSort(arr,rtemp+1,right);        //递归调用
        }
    }
}

4、希尔排序，又称Shell排序或缩小增量排序
(1)将有n个元素的数组分成n/2个数字序列，第1个数据和第n/2+1个数据为一对。
(2)一次循环使每一个序列对排好顺序。
(3)然后，再变为n/4个序列，再次排序。
(4)不断重复上述过程，随着序列减少最后变为一个，也就完成了整个排序。

public class shell{ 
    static void shellSort(int[] a){ 
        int h,temp,x=0;
        for(int r=a.length/2;r>=1;r/= 2)    //划组排序
        { 
            for(int i=r;i<a.length;i++)
            { 
                temp=a[i];
                int j=i-r;
                while(j>=0 && temp<a[j])
                { 
                    a[j+r]=a[j];
                    j-=r;
                }
                a[j+r]=temp;
            }
            x++;
        }
    }
}

5、堆排序
构造堆结构、堆排序输出来实现排序

public class pratice { 
    public static void heapSort(int a[],int n)            
    { 
        int i,j,h,k;
        int t;
        for(i=n/2-1;i>=0;i--)    //将a[0,n-1]建成大根堆
        { 
            while(2*i+1<n)         //第i个结点有右子树 
            { 
                j=2*i+1 ;
                if((j+1)<n)
                {             
                    if(a[j]<a[j+1])            //右左子树小于右子树，则需要比较右子树
                        j++;                 //序号增加1，指向右子树 
                }
                if(a[i]<a[j])                //比较i与j为序号的数据
                {             
                    t=a[i];                  //交换数据 
                    a[i]=a[j];
                    a[j]=t;            
                    i=j ;                    //堆被破坏，需要重新调整
                }
                else                     //比较左右子结点均大则堆未破坏，不再需要调整
                { 
                    break;
                }
            }
        }
        //输出构成的堆
        System.out.print("原数据构成的堆:");        
        for(h=0;h<n;h++)
        { 
            System.out.print(" "+a[h]);                //输出
        }
        System.out.print("\n");
        for(i=n-1;i>0;i--)
        { 
            t=a[0];                            //与第i个记录交换
            a[0] =a[i];
            a[i] =t;
            k=0;
            while(2*k+1<i)                     //第i个结点有右子树 
            { 
                j=2*k+1 ;
                if((j+1)<i)
                {             
                    if(a[j]<a[j+1])            //右左子树小于右子树，则需要比较右子树
                    { 
                        j++;                 //序号增加1，指向右子树 
                    }
                }
                if(a[k]<a[j])                //比较i与j为序号的数据
                {             
                    t=a[k];                  //交换数据 
                    a[k]=a[j];
                    a[j]=t;            
                    k=j ;                    //堆被破坏，需要重新调整
                }
                else                     //比较左右子结点均大则堆未破坏，不再需要调整
                { 
                    break;
                }
            }
        }
    }
}

6、归并排序
两两合并，进行比较、交换来实现排序

public class marge { 
    public static void mergeOne(int a[],int b[],int n,int len){  //完成一遍合并的函数 
        int i,j,k,s,e;
        s=0;
        while(s+len<n)  
        { 
            e=s+2*len-1;
            if(e>=n)                         //最后一段可能少于len个结点 
            { 
                e=n-1;
            }
            //相邻有序段合并
            k=s;
            i=s;
            j=s+len;
            while(i<s+len && j<=e)             //如果两个有序表都未结束时，循环比较 
            { 
                if(a[i]<=a[j])                //如果较小的元素复制到数组b中 
                { 
                   b[k++]=a[i++];
                }
                else
                { 
                    b[k++]=a[j++];
                }
            }
            while(i<s+len)                    //未合并的部分复制到数组b中 
            { 
                b[k++]=a[i++];
            }
            while(j<=e)
            { 
               b[k++]=a[j++];                 //未合并的部分复制到数组b中 
            }
            s=e+1;                         //下一对有序段中左段的开始下标 
        }
        if(s<n)                             //将剩余的一个有序段从数组A中复制到数组b中
        { 
            for(;s<n;s++)
            { 
                b[s]=a[s];
            }
        }
    }
    static void mergeSort(int a[],int n)                //合并排序
    { 
        int h,count,len,f;
        count=0;                            //排序步骤
        len=1;                             //有序序列的长度 
        f=0;                                //变量f作标志
        int[] p=new int[n];
        while(len<n)
        { 
            if(f==1)                           //交替在A和P之间合并 
            { 
                mergeOne(p,a,n,len);            //p合并到a
            }
            else
            { 
                mergeOne(a,p,n,len);            //a合并到p
            }
            len=len*2;                        //增加有序序列长度
            f=1-f;                             //使f值在0和1之间切换 
            count++;
            System.out.printf("第"+count+"步排序结果:");    //输出每步排序的结果
            for(h=0;h<SIZE;h++)
            { 
                System.out.printf(" "+a[h]);            //输出
            }
            System.out.print("\n");
        }
        if(f==1)                                //如果进行了排序
        { 
            for(h=0;h<n;h++)                    //将内存p中的数据复制回数组a
            { 
                a[h]=p[h];
            }
        }
    }
}