排序算法Java_实现

1.引言

查找和排序算法是算法的入门知识，其经典思想可以用于比较常见。

1.1 内部排序和外部排序的区别

内部排序：待排序记录存放在计算机随机存储器中(内存)进行排序的过程。

外部排序：待排序记录的数量很大，以至于内存不能一次容纳全部记录，所以在排序过程中需要对外存进行访问的排序过程

1.2 内部排序算法的分类

1.3 内部排序算法复杂度

(一) 冒泡排序

冒泡排序，从下往上遍历，每次遍历往上固定一个最小值

添加一个标志位，当某次冒泡排序没有元素交换时，则冒泡结束，元素已经有序，可以有效减少冒泡次数。

  public class BubbleSort{
     public int [] bubbleSort(int []Arr,int n)
     {
          //以flag为标记，标记数组是否已经排序完成
           boolean flag = true;
           //固定左边的数字
           for(int i=0;i<n-1&flag;i++)
           {
              flag = false;
              //从后面(下面)往前(上)遍历
              for(int j=n-2;j>=i;j--)
              {
                 if(A[j]>A[j+1])
                 {
                    swap(A,j,j+1);
                    flag = true;
                 }
              }
           }
           return A;
     }
     //数组是按引用传递，在函数中改变数组起作用
     private void swap(int []A,int i,int j)
     {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
        
     }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

(二) 简单选择排序

初始升序：交换0次，时间复杂度为O(n);
初始降序：交换n-1次，时间复杂为O(n^2);
特点：交换移动数据次数少，比较次数多。

   import java.util.*;


    public class Selection{
         public int [] selectionSort(int [] A,int n){     
          //简短选择排序算法，排序结果为递增数组
          //记录最小下标值
          int min=0;
          //固定左边的数字
          for(int i=0;i<A.length-1;i++)
          {
             min=i;
             //找到下标i开始后面的最小值
             for(int j=i+1;j<A.length;j++)
             {
                if(A[min]>A[j])
                {
                  min=j;
                }
             }
             //确保稳定排序，数值相等就不用交换
             if(i!=min)
             {
               swap(A,i,min);
             }
          }
 
         }
         return A;
    }
  
  private void swap(int []A,int i,int j)
  {
       int temp = A[i];
       A[i]=A[j];
       A[j]=temp;
       
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

(三)直接插入排序

   public class InsertionSort{
    
        public int[] insertionSort(int[] A,int n)
        {
          //用模拟插入扑克牌的思想
          //插入的扑克牌
          int i, j,temp;
          //已经插入一张，继续插入
          for(i=1;i<n;i++)
          {
            temp = A[i];
            //把i前面所有大于要插入的牌往后移一位，空出一位给新的牌
            for(j=i;j>0&&A[j-1]>temp;j--)
            {
             A[j]=A[j-1];
            }
            //把空出来的一位填满插入的牌
            A[j] = temp;
          }

            return A;
        }
   }
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(四) 希尔排序

基本思想：算法先将要排序的一组数按某个增量d(n/2,为要排序数的个数)分成若干组，每组中记录的下标相差d,对每组中全部元素进行直接插入排序，然后再用一个较小的增量(d/2)对它进行分组，在每组中再进行直接插入排序。当增量减到一时，进行直接插入排序后，排序完成
希尔排序(缩小增量法)属于插入类排序，是将整个无序列分割成若干小的子序列分别进行插入排序的方法。

  import java.util.*;
  public class ShellSort{
    public int[] shellSort(int []A,int n)
    {
       //要插入的纸牌
       int temp,j,i;
       //设定增量D，增量D/2逐渐减小
       for(int D =n/2;D>=1;D=D/2)
       {
            //从下标d开始，对数组d进行插入排序
            for(j=D;j<n;j++)
            {  
               temp=A[j];
              for(i=j;i>=D&&A[i-D]>temp;i-=D)
               { 
                A[i]=A[i-D];
               }
            A[i] = temp;
           }
       }
        return A;
    }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

(五) 堆排序

【堆】 1、堆是完全二叉树 2、大顶堆：每个节点的值都大于或等于其左右孩子节点的值，称为大顶堆。3、小顶堆：每个节点的值都大于或等于其左右孩子节点的值，称为小顶堆。
【完全二叉树数组表示形式】：如果i>1,则双亲结点[i/2]。也就是说下标i与下标i2+1是双亲子女关系。
（注意如果排序对象为数组时，下标从0开始，所以下标i与下标21+1和2*i+2是双亲子女关系）

    import java.util.*;
    public class HeapSort{
        public  int[] heapSort(int[] A,int n)
        {
             //堆排序方法
              
               int i;
               //先把A[]数组构建成一个大顶堆。
               //从完全二叉树的最下层最右边的非终端点开始构建。
               for(i=n/2-1;i>=0;i--)
               {
                 HeapAdjust(A,i,n);
               }
       //开始遍历
       for(i=n-1;i>0;i--)
       {
         swap(A,0,i);
         //每交换一次得到一个最大值然后丢弃
         HeapAdjust(A,0,i);
       }
             return A;
        }
  //A[i] 代表的是下标为i的根节点
   private void HeapAdjust(int [] A,int i, int n)
   {
        //【注意】这里下标从0开始
         int temp;
         //存储根节点
         temp =A[i];
         //沿根节点的左右孩子中较大的往下遍历，由于完全二叉树特性i在左子节点2*i+1  i的右子节点 2*i+2
         for(int j=2*i+1;j<n;j=j*2+1)
         {
             if(j<n-1&&A[j]<A[j+1])
             {
                ++j;
             }
             if(temp>=A[j])
             {
                break;
             }
             //将子节点赋值给根节点
             A[i]=A[j];
             //将子节点下标赋给i
             i=j;
             
         }
         //将存储的根节点的值赋值给子节点
         A[i]=temp;
   }

private void swap(int []A,int i,int j)
{
   int temp = A[i];
   A[i]=A[j];
   A[j]=temp;
   
}


    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60