首页 > 代码库 > java实现 数据结构之8大排序

java实现 数据结构之8大排序

2024-07-25 01:27:22   229人阅读

数据结构中8大排序（java方式实现）
 
    * 
        * 冒泡排序
        * 插入排序
        * 选择排序
        * shell排序
        * 堆排序
        * 归并排序
        * 二叉树排序
        * 快速排序
 
    * 冒泡排序
 
     private void bubblesort() {
           int data [] = create();
           print (data );
           long start = start ();
           for( int i =0 ; i< data .length - 1; i ++){
               for( int j =i + 1; j <data . length; j ++){
                    if( data [i ]> data[ j ])
                         swap (i , j, data );
               }
           }
           end (start , "冒泡" );
           print (data );
      }
     private void swap( int i , int j , int [] data ) {
           int temp = 0 ;
          temp = data[ i ];
          data [ i] = data [ j];
          data [ j] = temp ;
      }
      public static long start (){
           return   System.currentTimeMillis ();
      }
      public static void  end (long start , String str ){
           long end = System.currentTimeMillis();
          System . out. println (str + "排序花费的时间  = "+( end- start ));
      }
 
     static int [] create () {
           int array [] = new int[ 1000];
           for( int i =0 ; i< 1000 ; i ++){
               try {
                   Thread . sleep( 1 );
               } catch (InterruptedException e ) {
                    // TODO Auto-generated catch block
                   e . printStackTrace();
               }
              array [ i] = new Random (). nextInt( 100000 );
           }
           return array;
      }
 
    * 插入排序
 
     private void insertsort() {
           int data [] = create();
           print (data );
           long start = start ();
           int temp = 0 , j = 0;
           for( int i =0 ; i< data .length ; i++){
              temp = data[ i ];
              j = i- 1 ;
               while( j >=0 && data[ j ]>temp ){
                   data [ j+ 1 ] = data[ j ];
                   j --;
               }
              data [ j+ 1 ] = temp;
           }
           end (start , "插入" );
           print (data );
      }
 
    * 选择排序
 
     private void selectsort() {
           int data [] = create();
           print (data );
           int k =0 ;
           long start = start ();
           for( int i =0 ; i< data .length - 1; i ++){
              k = i;
               for( int j =i + 1; j <data . length; j ++){
                    if( data [k ]> data[ j ]){
                        k = j;
                    }
               }
               swap (i , k, data );
           }
           end (start , "选择" );
           print (data );
      }
 
    * shell 排序
 
private void shellsort() {
           int data [] = create();
           print (data );
           long start = start ();
           int j = 0 ;
           int temp = 0 ;
           int gap = 0 ;
           int n = data . length;
           while( gap <data . length){
              gap = gap* 3 +1 ;
           }
           
           while( gap >0 ){
               for( int i =gap ; i< n ; i ++){
                   j = i- gap ;
                   temp = data[ i ];
                    while( j >=0 && data[ j ]>temp ){
                        data [ j+ gap ] = data[ j ];
                        j = j- gap ;
                    }
                   data [ j+ gap ] = temp;
               }
              gap = ( gap -1 )/ 3;
               
               
           }
           print (data );
           end (start , "shell" );
      }
 
    * 堆排序
 
     public   void heapsort() {
           int data [] = create();
           print (data );
           long start = start ();
           crateheap (data );
           for( int i =data . length- 1 ; i >= 1; i --){
               swap (i , 0, data );
               heapfiy (data , 0, i );
           }
           end (start , "堆" );
           print (data );
      }
     private void crateheap( int[] data ) {
           int n = data . length;
           for( int i =n / 2- 1 ; i > 0; i --){
               heapfiy (data , i, n );
           }
           
      }
     private void heapfiy( int[] data , int i, int n ) {
           int left = i * 2+ 1 ;
           int right = i * 2+ 2 ;
           int large = 0 ;
           if( left <n && data[ left ]>data [ i])
              large = left;
           else
              large = i;
           if( right <n && data[ right ]>data [ large])
              large = right;
           if( large !=i ){
               swap (large , i, data );
               heapfiy (data , large, n );
           }
      }
 
    * 归并排序
 
     public   void mergesort() {
           int data [] = create();
           print (data );
           long start = start ();
           merge (data , 0, data .length - 1);
           end (start , "归并" );
           print (data );
      }
     public void merge( int data [],int low ,int high){
           int mid = ( low+ high )/2 ;
           if( low <high ){
           merge (data , low, mid );
           merge (data , mid+ 1 , high );
           merge1 (data , low, mid , high );
           }
      }
     private void merge1( int[] data , int low, int mid , int high ) {
           int temp [] = new int [ high -low + 1];
           int i = low ;
           int j = mid + 1;
           int k = 0 ;
           while( i <=mid && j<= high ){
               if( data [i ]< data[ j ]){
                   temp [ k++] = data [ i++];
               }else {
                   temp [ k++] = data [ j++];
               }
           }
           
           while( i <=mid ){
              temp [ k++] = data [ i++];
           }
           while( j <=high ){
              temp [ k++] = data [ j++];
           }
           
           for( int k2 =0 ; k2< temp .length ; k2++){
              data [ k2+ low ] = temp[ k2 ];
           }
           
      }
 
    * 二叉树排序
 
public class BinaryTree {
      int data ;       //根节点数据
      BinaryTree left ;    //左子树
      BinaryTree right ;   //右子树
      public BinaryTree( int data)     //实例化二叉树类
      {
       this. data = data ;
       left = null;
       right = null;
      }
      public void insert( BinaryTree root, int data ){     //向二叉树中插入子节点
            if( data >root . data)                                //二叉树的左节点都比根节点小
            {
             if( root .right ==null ){
              root . right = new BinaryTree( data );
             }else {
              this. insert (root . right, data );
             }
            }else {                                          //二叉树的右节点都比根节点大
             if( root .left ==null ){
              root . left = new BinaryTree( data );
             }else {
              this. insert (root . left, data );
             }
            }
           }
      
}
  public static void inOrder( BinaryTree root ){     
 
            if( root !=null){
             inOrder (root . left);
             System . out. print (root . data+ "--" );
             inOrder (root . right);
            }
           }
 
    * 快速排序
 
     public void quicksort() {
           int data [] = create();
           print (data );
           long start = start ();
           quick1 (data , 0, data .length - 1);
           end (start , "快速" );
           print (data );
      }
     public int [] quick1 (int data [],int left, int right ){
           int mid ;
           if( left <right ){
              mid = quick ( data, left , right );
               quick1 (data , left, mid -1 );
               quick1 (data , mid+ 1 , right );
           }
           return data;
      }
     private int quick( int[] data , int left, int right ) {
           int mid = data [ left];
           while( left <right ){
               while( left <right && data[ right ]>=mid )
                   right --;
              data [ left] = data [ right];
               
               while( left <right && data[ left ]<=mid )
                   left ++;
              data [ right] = data [ left];
           }
           
          data [ left] = mid ;
           
           return left;
      }

java实现 数据结构之8大排序


联系
我们