【数据结构】用java实现不同的七种排序算法和性能比较

短命女 2022-10-04 15:49 122阅读 0赞

### 文章目录 ###

*   *  1.直接插入排序
     *  2.希尔排序
     *  3.冒泡排序
     *  4.快速排序
     *  5.选择排序
     *  6.堆排序
     *  7.归并排序

--------------------

## 1.直接插入排序 ##

public class DifferentSort { 
        public static void main(String[] args) { 
            Insert insert = new Insert();
            insert.sort();
        }
    }
    class Insert { 
        int total;
        int[] data = new int[10];
    
        Insert() { 
            Random random = new Random();
            for (int i = 0; i < 10; i++)
                data[i] = random.nextInt() %100;
    
        }
    
        void sort() { 
            total = 10;
            int j;
            int temp;
            for (int i = 1; i < total; i++) { 
                temp = this.data[i];
                j = i - 1;
              // System.out.println(j);
    
                    while (data[j] > temp && j >=0) { 
                        data[j+1] = data[j];
                        j--;
                     if(j < 0) break;
    
                    }
                data[j+1] = temp;
    
            }
            for (int i = 1; i < total; i++)
                System.out.println(data[i]);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]

## 2.希尔排序 ##

插入排序的改进版，插入排序当序列为正序或基本有序时时间复杂度为o(n),希尔排序的基本思想：待排序列划分为若干组，每组内进行直接插入排序，然后再对整个序列直接排序  
步长的变化：1<dl<=n/2  
初始步长可以直接决定希尔排序的性能

class  Shell{ 
        int total;
        int[] data = new int[10];
    
        Shell() { 
            total = 10;
            Random random = new Random();
            for (int i = 0; i < 10; i++)
                data[i] = random.nextInt(100) %60;
            for (int i = 0; i < 10; i++)
                System.out.print(data[i]+",");
    
        }
        public void shell_sort(){ 
            int temp;
            int j;
            int dl = this.total/2;//初始步长
            while(dl >=1){ 
                for(int i = 1+dl;i < total;i++)
                { 
                    temp = data[i];
                    j = i-dl;
                    while (j>=0 && data[j] > temp)
                    { 
                        data[j+dl] =data[j];
                        j = j-dl;
                        if(j < 0) break;
                    }
                    data[j+dl] = temp;
                }
                dl  = dl/2;
            }
            System.out.println("希尔排序后");
            for (int i = 1; i < total; i++)
                System.out.print(data[i]+",");
        }
    
    }

结果：  
18,29,29,48,12,17,15,0,0,33,希尔排序后  
0,0,12,15,17,29,29,33,48,  
改数字为十万后：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]

## 3.冒泡排序 ##

每一次都浮上来最小的元素，是稳定的排序算法  
以下用exchange作为标记，如果为false表示已经排序完成，可以不再执行下一次循环

class pop{ 
        int total = 100000;
    
        int[] data = new int[total];
       pop() { 
           Random random = new Random();
           for (int i = 0; i < total; i++)
               data[i] = random.nextInt() % 60000;
           for (int i = 0; i < total; i++)
               System.out.print(data[i] + ",");
       }
    
        public void pop_sort() { 
           boolean exchange = false;
    for(int i = 1;i < total;i++)
    { 
        for(int j = total-1;j >= i;j--)
        { 
            if(data[j] < data[j-1])
            { 
                exchange = true;
                int temp = data[j];
                data[j]= data[j-1];
                data[j-1] = temp;
            }
    
        }
        if(exchange == false) break;
    }
            System.out.println("冒泡排序后");
            for (int i = 1; i < total; i++)
                System.out.print(data[i]+",");
        }
    }

结果：  
![在这里插入图片描述][20210712021144402.png]  
明显看出来冒泡排序实在太慢，与希尔排序相比差了有五十倍  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 3]

## 4.快速排序 ##

首先选一个元素作为中间元素，然后对两边进行同样的操作,递归进行

class Quick{ 
        Integer partion;
      int total = 10000;
        //Integer n = 100;解析为 Integer num = Integer.valueOf(100);
        //valueOf(参数)方法其实调用的是 new Integer(100);
      int[]data= new int[total];
     
    int n = 0;
        Quick(){ 
    
            Random random = new Random();
            for (int i = 0; i < total; i++)
                data[i] = random.nextInt(1000) %1000;
            for (int i = 0; i < total; i++)
                System.out.print(data[i]+",");
        }
        public Integer getN(){ 
            return this.n;
        }
        public Integer get(){ 
            return this.total;
        }
        public int part(int begin,int end){ 
          int temp;
            temp = data[begin];
          int i = begin,j = end;
       while (i != j)
            { 
          while(i <j &&data[j] > temp) { 
    
             j--;
             }
          if(i < j){ 
              data[i] = data[j];//data[j]填补到空位中,交换
              i++;
          }
             while (data[i] < temp && i < j)
             { 
                 i++;
             }
             if(i < j){ 
                 data[j] = data[i];j--;//填补到后面的空位中
             }
            }
       data[i] = temp;//最终temp的位置
    
          
            return i;
        }
        public void Quick_sort(int n,int total){ 
    
           // Integer i = new Integer(10);
    
            if(n < total){ 
              int partnum =  part(n,total);
                Quick_sort(n,partnum-1);
                Quick_sort(partnum+1,total);
            }
            else { 
    
                return;
            }
        }
        public void display(){ 
            System.out.println("快速排序后");
            for (int i = 1; i < total; i++)
                System.out.print(data[i]+",");
        }
    }
    
        public static void main(String[] args) { 
            long now = System.currentTimeMillis();
    Quick quick = new Quick();
    
    quick.Quick_sort(quick.getN(),quick.get()-1);
    quick.display();
    long now2 = System.currentTimeMillis();
            System.out.println();
            System.out.println(now2-now+"ms");
        }

排十万个数字：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 4]  
目前的话看得出快速排序比希尔排序更快，性能是最好的。  
另外在这里尝试了用Integer,发现会导致程序死循环，原因还未查明，应该跟它的数字范围有关

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 5]

## 5.选择排序 ##

关键思想：每一次都把关键字最小或最大的元素放在最终位置上，选择排序包括堆排序和直接选择排序  
直接选择排序通过待排子表中完整地比较一遍以确定最大或最小元素，并放在子表的最前面/最后面

class choose{ 
        int total = 100000;
    
        int[] data = new int[total];
        choose(){ 
            Random random = new Random();
            for (int i = 0; i < total; i++)
                data[i] = random.nextInt(10000) % 10000;
            for (int i = 0; i < total; i++)
                System.out.print(data[i] + ",");
        }
        public void choose_sort(){ 
            int min = Integer.MAX_VALUE;
            for(int i = 0;i < total-1;i++)
            { 
                min = i;
                for(int j = i+1;j < total;j++)
                { 
                    if(data[j] < data[min])
                    { 
                        min = j;
                    }
                }
                if(min != i)
                { 
                    int temp = data[i];
                    data[i] = data[min];
                    data[min] = temp;
                }
            }
            System.out.println("选择排序后：");
            for (int i = 1; i < total; i++)
                System.out.print(data[i]+",");
        }
    }
    
        public static void main(String[] args) { 
            long now = System.currentTimeMillis();
    choose choose1 = new choose();
    choose1.choose_sort();
    
    long now2 = System.currentTimeMillis();
            System.out.println();
            System.out.println(now2-now+"ms");
        }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 7]

## 6.堆排序 ##

可以分两种情况分别讨论  
①如果初始序列是堆,则可通过反复执行如下操作而最终得到一个有序序列  
输出根:即将根(第一个元素)与当前子序列中的最后一个元素交换。  
调整堆:将输出根之后的子序列调整为堆(元素个数比输出前少1个)元  
②如果初始序列不是堆,则首先要将其先建成堆然后再按①的方式来实现  
现在的问题是:如何由一个无序序列建成一个堆?  
事实上,由无序序列建堆可通过反复调用筛选作来实现。为此需满足筛选的条件,即左右子树必须为堆。因此,建堆过程要从下往上逐子树地进行筛选。从易于编程的角度出发,根的下标自然是按从大到小,即按照根的下标从2到1的次序调整各子树为堆。  
由初始序列(12,15,30,80,100,46,78,3390,86,64,55,120,230,45)建堆的过程如图11-9所示。

最终得到的堆：  
（230,100,120,90,86,55,7833,80,15,64,12,46,30,45)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 9]  
代码：

class Heap{ 
    
        int total = 100000;
        //Integer n = 100;解析为 Integer num = Integer.valueOf(100);
        //valueOf(参数)方法其实调用的是 new Integer(100);
        int[]data= new int[total];
        Heap(){ 
            Random random = new Random();
            for (int i = 0; i < total; i++)
                data[i] = random.nextInt(10000) %10000;
            for (int i = 0; i < total; i++)
                System.out.print(data[i]+",");
        }
        public void build(int begin,int end){ //建立大根堆
            //end为最大元素下标
            //调整数组以begin为根的子树序列为根，其中最大的元素下标为end
            //假设以2k和2k+1为根的左右子树均为堆
                   int i = begin;
                   boolean finished = false;
                   int j = 2*i;
                   int temp = this.data[i];
                   while(j<= end && !finished)
                   { 
    
                       if(j+1<=end && this.data[j+1] > this.data[j])
                           j = j+1;//指向左右孩子的最大值
                       if(this.data[i] < this.data[j])
                       { 
                           this.data[i] = this.data[j];
                           i = j;
                           j = 2*j;
                       }
                       else finished = true;//如果原根最大，筛选结束
                   }
                   this.data[i] = temp;//原根的值填充到所搜索的当前空位置中
        }
        public void heap_sort(){ 
            for(int i = (total-1)/2;i>=0;i--)
            { 
                build(i,total-1);//建立初始堆
    
            }
            System.out.println();
    
            for(int i = total-1;i>=1;i--)
            { 
                int temp = this.data[0];
                this.data[0] = this.data[i];
                this.data[i] = temp;//先输出根
                build(0,i-1);//调整子序列data[0..i-1]
    
            };
            System.out.println("堆排序后");
            for (int i = 0; i < total; i++)
                System.out.print(data[i]+",");
        }
    }
    
        public static void main(String[] args) { 
            long now = System.currentTimeMillis();
    Heap heap=new Heap();
    heap.heap_sort();
    
    long now2 = System.currentTimeMillis();
            System.out.println();
            System.out.println(now2-now+"ms");
        }

结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 10]

## 7.归并排序 ##

public static void main(String[] args) { 
            long now = System.currentTimeMillis();
    Merge merge = new Merge();
    merge.merge_operation(0,merge.get()-1);
        System.out.println();
            for (int i = 0; i < merge.get(); i++)
                System.out.print(merge.data[i]+",");
    long now2 = System.currentTimeMillis();
            System.out.println();
            System.out.println(now2-now+"ms");
        }
    class Merge{ 
        int total = 100000;
    
       public int[]data= new int[total];
        Merge(){ 
            Random random = new Random();
            for (int i = 0; i < total; i++)
                data[i] = random.nextInt(10000) %10000;
            for (int i = 0; i < total; i++)
                System.out.print(data[i]+",");
        }
        public Integer get(){ 
            return this.total;
        }
        public void merge(int low, int mid, int high){ 
    
            int i = low;
            int j = mid + 1;
            int []tmp = new int[high - low +1];//分配足够空间
            int k = 0;
            while(j <= high && i <= mid)
            { 
                if(data[i] >data[j])
                { 
    
                    tmp[k++] = data[j++];
                }
                else tmp[k++] = data[i++];
            }
            while(j <= high)
                tmp[k++] = data[j++];
            while(i <= mid)
                tmp[k++] = data[i++];
            for(int k1 = 0;k1 < k;k1++)
                data[low+k1] = tmp[k1];
    
        }
        public void merge_operation(int low,int high) { 
            if (low < high) { 
                int mid =(low + high)/2;
                merge_operation(low,mid);
                merge_operation(mid+1,high);
                merge(low,mid,high);
            }
        }
    }

结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 11]  
还是比较快的，时间复杂度是o(nlogn)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70]: /images/20221004/db6b217131fb46ff9bf8aa9f9577ff01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 1]: /images/20221004/9987aa9898e44668b27115a35f746995.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 2]: /images/20221004/b45240af410a4a5e9d4e395e41c47345.png
[20210712021144402.png]: /images/20221004/4678af47261c4d11b1ba0afa8819470e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 3]: /images/20221004/b6a2d5de988946e4954bb84354bb69b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 4]: /images/20221004/f2115e77342247dc9cced5e8679c7c71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 5]: /images/20221004/31e2a05797f049e4aed5bb3de3b143fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 6]: /images/20221004/2e858076eb804009b27070e6ff910055.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 7]: /images/20221004/f22f4855003a4c39b0f5945732a620e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 8]: /images/20221004/266a0ebbf86c4888ac6021f8cb1ed5fc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 9]: /images/20221004/6f221909762548c4ad2078a647b40059.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 10]: /images/20221004/e76a93c9b5c54abab4580f080c908915.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzU4NTc0_size_16_color_FFFFFF_t_70 11]: /images/20221004/af5b1337c08d49debb3bd4505ac5ffcd.png