常见排序算法分析Java实现(内附大量注释)

前言

排序算法属于数据结构的内容,不算太难但是要完全掌握还是得一步一步的分析代码体会不同排序算法的思想,并且试着自己实现,在面试中经常会要求手写xx排序算法,如何让一串不规则的数字用最快的时间,最少的空间将这串数字有序,想想也是一件挺有趣的事。
各种排序方法性能的比较

排序方法 最好时间 最坏时间 时间复杂度 空间复杂度 稳定性
直接插入排序 O(n) O(n2) O(n2) O(1) 稳定
希尔排序 O(nlog2n) O(n3/2) O(nlog2n)) O(1) 不稳定
冒泡排序 O(n) O(n2) O(n2) O(1) 稳定
快速排序 O(nlog2n) O(n2) O(nlog2n) O(log2n) 不稳定
简单选择排序 O(n) O(n2) O(n2) O(1) 不稳定
堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 不稳定
二路归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 稳定

具体实现

为了直观，算法的思想及其步骤都写在了代码注释里

直接插入排序

先看代码

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
void justAddSort() {
      int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
      System.out.println("排序之前：");
      for (int i = 0; i < a.length; i++) {
          System.out.print(a[i] + " ");
      }
      //-------------好戏开始--------------------
      for (int i = 1; i < a.length; i++) { //从第二个元素开始向后遍历
          int temp = a[i];  //用一个int变量保存待插入元素a[i]的值，所以空间复杂度为O(1)
          int j;      //j代表待插元素temp的最终归宿;
          for (j = i - 1; j >= 0; j--) { //用一个for循环遍历i左边的元素，究竟temp放在哪里
              //将大于temp的往后移动一位
              System.out.println(j);
              if (a[j] > temp) { //只有a[j]比temp值大才有继续for循环的资本
                  a[j + 1] = a[j]; //因为a[i]的值赋给了temp,可以放心地右移元素
              } else { //直接跳出for循环;
                  break;
              }
          }
          a[j + 1] = temp; //因为在跳出for循环的时候执行了一次j--,所以这里是a[j+1],代表temp最终归宿
      }
      System.out.println("排序之后：");
      for (int i = 0; i < a.length; i++) {
          System.out.print(a[i] + " ");
      }
  }

直接插入排序如同玩扑克牌的人抓牌一样，将抓到的牌插入手中已排好的牌中一个适当的位置,下面介绍另一种插入排序。

二分法插入排序

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
void binarySort() {
    int[] a = {49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1};
    System.out.println("排序之前：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i] + " ");
    }

    for (int i = 0; i < a.length; i++) { //因为是从第0个开始插入,所以在插入第n个元素的时候,前面(n-1)个元素已经有序
        int temp = a[i]; //获取待插值
        int left = 0;    //1.用于查找temp的最终归宿，2.作为（n-1）个有序元素的头
        int right = i - 1; //作为有序元素的末端
        int mid = 0; //二分查找的精髓
        while (left <= right) {   //只要left<=right 就说明还没有找出适合的插入点
            mid = (left + right) / 2;
            if (temp < a[mid]) {   //待插值<a[mid] 则在mid左边的数组找
                right = mid - 1;
            } else {                //否则在mid右边的数组找
                left = mid + 1;
            }
        }
        for (int j = i - 1; j >= left; j--) { //将left右边的值都右移1位
            a[j + 1] = a[j];
        }
        if (left != i) { //left=i说明 temp是有序(n-1)个有序数组里的最大值可忽略，!=i则可以插入
            a[left] = temp;
        }
    }
    System.out.println("排序之后：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i] + " ");
    }
}

二分法插入排序也是稳定的。

二分插入排序的比较次数与待排序记录的初始状态无关，仅依赖于记录的个数。当n较大时，比直接插入排序的最大比较次数少得多。但大于直接插入排序的最小比较次数。算法的移动次数与直接插入排序算法的相同，平均移动次数为O(n2)。

希尔排序

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
void shellSort(){

        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1};
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //希尔排序
        int d = a.length; //d代表方阵的长度大小,只和方阵以外的且相同顺序的元素对比交换(如第一方阵的1号元素只和第二方阵的1号元素对比)
        while(true){ //负责切换d的大小
            d = d / 2;
            for(int x=0;x<d;x++){// 遍历d内的元素
                for(int i=x+d;i<a.length;i=i+d){ //联系d之外的元素
                    int temp = a[i];
                    int j;
                    for(j=i-d;j>=0&&a[j]>temp;j=j-d){   //对比其他方阵内同位置元素的大小
                        a[j+d] = a[j];    //将大值跨方阵移一位
                    }
                    a[j+d] = temp;  //将保存的temp值放在最后一次移动过的下标,因为脱离for循环的时候执行过j=j-d,所以这里是a[j+d]
                }
            }
            if(d == 1){   //当d=1,执行完上述逻辑，并结束此次排序，因为d不可再分
                break;
            }
        }
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

希尔排序先将整个待排序记录序列分割成为若干子序列,分别进行直接插入排序,待整个记录基本有序时,再对全体记录进行直接插入排序,减少移动次数,提高了效率！

简单选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void simpleChoose(){
       int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
       System.out.println("排序之前：");
       for (int i = 0; i < a.length; i++) {
           System.out.print(a[i]+" ");
       }
       for (int i = 0; i < a.length; i++) {
           int temp=a[i];           //temp用来保存遍历过的元素中的最小值
           int num=i;              //num用来保存遍历过的元素中的最小值的index
           for (int j=i+1;j<a.length;j++){ // 此处for循环好比一个比赛，找出最小值
               if (a[j]<temp){
                   temp=a[j];          //temp保存暂时的最小值
                   num=j;              //num保存暂时的最小值index
               }
           }
           a[num]=a[i];        //将a[i]与右边的最小值互换
           a[i]=temp;

       }
       System.out.println("排序之后：");
       for (int i = 0; i < a.length; i++) {
           System.out.print(a[i]+" ");
       }
   }

简单选择排序可以理解成为每次循环遍历找出最小值的过程

堆排序

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
void heapSort(){

           int[] a={49,38,65,97,76,13,27,49,78,34,12,98,1};
           int arrayLength=a.length;
           //循环建堆
           for(int i=0;i<arrayLength-1;i++){
               //建堆
               buildMaxHeap(a,arrayLength-1-i);
               //交换堆顶和最后一个元素
               swap(a,0,arrayLength-1-i);

               System.out.println(Arrays.toString(a));
           }
       }
       //对data数组从0到lastIndex建大顶堆
       public static void buildMaxHeap(int[] data, int lastIndex){
           //从lastIndex处节点（最后一个节点）的父节点开始
           for(int i=(lastIndex-1)/2;i>=0;i--){
               //k保存正在判断的节点
               int k=i;
               //如果当前k节点的子节点存在
               while(k*2+1<=lastIndex){
                   //k节点的左子节点的索引
                   int biggerIndex=2*k+1;
                   //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在
                   if(biggerIndex<lastIndex){
                       //若果右子节点的值较大
                       if(data[biggerIndex]<data[biggerIndex+1]){
                           //biggerIndex总是记录较大子节点的索引
                           biggerIndex++;
                       }
                   }
                   //如果k节点的值小于其较大的子节点的值
                   if(data[k]<data[biggerIndex]){
                       //交换他们
                       swap(data,k,biggerIndex);
                       //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值
                       k=biggerIndex;
                   }else{
                       break;
                   }
               }
           }
       }
       //交换
       private static void swap(int[] data, int i, int j) {
           int tmp=data[i];
           data[i]=data[j];
           data[j]=tmp;
       }

堆排序在数据量非常大的时候非常有用,其大体思想和简单选择排序相似，堆排序是找出最大值，从右边开始建立有序数组。简单选择排序是找出最小值，从左边开始建立有序数组。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubbleSort(){
    int[] a={2222,49,38,65,97,76,13,27,49,78,34,12,64,1,8};
             System.out.println("排序之前：");
           for (int i = 0; i < a.length; i++) {
                     System.out.print(a[i]+" ");
                 }
            for (int i=0;i<a.length;i++){ //这个for循环控制第二个for循环遍历的元素个数
               for (int j=0;j<a.length-1-i;j++){ //第一次循环会将所有元素最大的移到最右边 第二次循环会将所有元素第二大的移到右2的位置
                   if (a[j]>a[j+1]){       //很显然,如果左边比右边大则交换
                       int temp=a[j+1];
                       a[j+1]=a[j];
                       a[j]=temp;
                   }
               }
                System.out.println(Arrays.toString(a));
            }
    System.out.println("排序之后：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
}

冒泡排序将相邻记录的关键字进行比较，若前面记录的value大于后面记录的value，则交换。较小的记录像水泡向前冒出，较大的记录像石块沉入后部。

快速排序

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
void quickSort(){
    int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
    System.out.println("排序之前：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
    //快速排序
    quick(a);
    System.out.println("排序之后：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
}
private static void quick(int[] a) {
    if(a.length>0){
        quickSort(a,0,a.length-1);
    }
}
private static void quickSort(int[] a, int low, int high) {
    if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
        int middle = getMiddle(a,low,high); //middle已经找到了数组中属于自己的位置 (middle左边都比middle小，middle右边都比middle大)
        quickSort(a, 0, middle-1);// 所以middle不再参与排序运算
        quickSort(a, middle+1, high);
    }
}
private static int getMiddle(int[] a, int low, int high) {
    int temp = a[low];//基准元素
    while(low<high){ //除非temp = a[high] 否则只执行以下两个while循环中的一个
        //找到比基准元素小的元素位置
        while(low<high && a[high]>=temp){ //这两个while循环目的就是 找到数组中属于temp的那个位置，其左都比temp小，其右都比temp大
            high--;
        }
        a[low] = a[high];
        while(low<high && a[low]<=temp){
            low++;
        }
        a[high] = a[low];
    }
    a[low] = temp;//或者a[high+1]=temp
    return low;
}

快排的思想就是为各个元素在数组上找到属于自己的座位。

归并排序

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
void gbSort(){
    int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
    System.out.println("排序之前：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
    //归并排序
    mergeSort(a,0,a.length-1);
    System.out.println("排序之后：");
    for (int i = 0; i < a.length; i++) {
        System.out.print(a[i]+" ");
    }
}

private static void mergeSort(int[] a, int left, int right) {
    if(left<right){
        int middle = (left+right)/2;
        //对左边进行递归
        mergeSort(a, left, middle);
        //对右边进行递归
        mergeSort(a, middle+1, right);
        //合并
        merge(a,left,middle,right);
    }
}

private static void merge(int[] a, int left, int middle, int right) {
    int[] tmpArr = new int[a.length];   //归并排序借助一个中间数组
    int mid = middle+1; //右边的起始位置
    int tmp = left;     //保存起始位置
    int third = left;   //中间数组的起始位置
    while(left<=middle && mid<=right){
        //从两个数组中选取较小的数放入中间数组
        if(a[left]<=a[mid]){
            tmpArr[third++] = a[left++];
        }else{
            tmpArr[third++] = a[mid++];
        }
    }
    //将剩余的部分放入中间数组
    while(left<=middle){
        tmpArr[third++] = a[left++];
    }
    while(mid<=right){
        tmpArr[third++] = a[mid++];
    }
    //将中间数组复制回原数组
    while(tmp<=right){
        a[tmp] = tmpArr[tmp++];
    }
}

归并排序算法的思路是:对任意长度n的序列，先看成n个长度为1的有序序列，然后归并为n/2个有序表，在对n/2个有序表两两归并，直到得到一个长为n的有序表。

视频演示

最后介绍一个特别棒的排序算法视频给大家
舞蹈展示排序算法

本文标题:常见排序算法分析Java实现(内附大量注释)

文章作者:杨凯文

发布时间:2017-08-29, 23:38:53

最后更新:2018-10-05, 23:11:13

原始链接:http://yangkw.com/2017/08/29/看得懂的常见排序算法分析(java实现)/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 前言
  2. 2. 具体实现
  3. 3. 视频演示
|