七种排序算法

发表于 | 分类于 |

学习并记录了七种排序算法，计数排序、桶排序和基数排序这三个没有算法可见十大排序算法动图

排序根据排序记录是否全部被放置在内存中，分为内排序和外排序两种，外排序需要在内外存之间多次交换数据才能进行。

对于内排序，排序算法的性能主要受3个方面影响：

  • 时间性能
  • 辅助空间
  • 算法的复杂性

几种算法的各种指标进行对比，如下：

关于时间复杂度

1.平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序

2.线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序

3.O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

4.线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性

稳定排序的意思是：比如原本一组无序的元素中出现两个相同的值，那么经过稳定排序后这两个相

等的元素必然相邻，不改变原来无序状态下的先后顺序叫稳定的排序。

1.稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

2.不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

辅助记忆

时间复杂度记忆：
冒泡、选择、直接排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O（n2）O（n2）（一遍找元素O(n)O(n)，一遍找位置O(n)O(n)）；
快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)O(nlogn)（一遍找元素O(n)O(n)，一遍找位置O(logn)O(logn)）。

稳定性记忆-“快希选堆”（快牺牲稳定性）
排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

冒泡排序

原理：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续,直至比较最后两个数，将小数放前，大数放后。重复第一趟步骤，直至全部排序完成。

第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较；

第二趟比较完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较；

依次类推… 

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
package sort;

import java.util.Arrays;

//从小到大的顺序排序
public class BubbleSort {
    
    public static void bubble(int[] arrays){
        
        //装载临时变量
        int temp;
        
        //记录执行了多少趟
        int num=0;
        
        //记录是否发生了置换， 0 表示没有发生置换、 1 表示发生了置换
        int isChange;
        
        //外层循环是排序的趟数
        for(int i=0;i<arrays.length-1;i++){
            
            //每比较一趟就重新初始化为0
            isChange=0;
            
            //内层循环是当前趟数需要比较的次数
            for(int j=0;j<arrays.length-i-1;j++){
                
                //前一位与后一位与前一位比较，如果前一位比后一位要大，那么交换
                if(arrays[j]>arrays[j+1]){
                    temp=arrays[j];
                    arrays[j]=arrays[j+1];
                    arrays[j+1]=temp;
                    
                    //如果进到这里面了，说明发生置换了
                    isChange=1;
                }
            }
            
            //如果比较完一趟没有发生置换，那么说明已经排好序了，不需要再执行下去了
            if(isChange==0){
                break;
            }
            num++;
            }
        System.out.println(num);
        System.out.println(Arrays.toString(arrays));
    }   
    public static void main(String[] args) {
        int[] arrays={3,10,4,1,5};
        bubble(arrays);
    }
}

选择排序

通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i(1<=i<=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
27
28
29
30
31
32
33
34
35
36
package sort;

import java.util.Arrays;

public class SelectionSort {
    public void sort(){
        int[] arrays= {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3};
        
         //记录当前趟数的最大值的角标
        int pos;
        
         //交换的变量
        int temp;
        
        //外层循环控制需要排序的趟数
        for(int i=0;i<arrays.length-1;i++){
            
            //新的趟数、将角标重新赋值为0
            pos=0;
            
            //内层循环控制遍历数组的个数并得到最大数的角标
            for(int j=0;j<arrays.length-i-1;j++){
                if(arrays[j]>arrays[pos]){
                    pos=j;
                }
            }
            
            //交换
            temp=arrays[pos];
            arrays[pos]=arrays[arrays.length-i-1];
            arrays[arrays.length-i-1]=temp;
        }
        
        System.out.println(Arrays.toString(arrays));
    }
}

直接插入排序

将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

就是把数组中元素一个个取出插入到有序表中，直到将数组元素全部插入到有序表中。 

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
package sort;

import java.util.Arrays;

public class InsertSort {
    public static void main(String[] args) {
        int[] arrays = {9, 8, 1, 4, 2, 3, 5, 6, 7, 13, 12, 14, 11, 15, 16, 17, 19, 18, 10};
        sort(arrays);
    }
    
    /**
     * 插入排序普通版
     * @param arrays
     */
    public static void sort(int[] arrays){ 
        
        //临时变量
        int temp;
        
         //外层循环控制需要排序的趟数(从1开始因为将第0位看成了有序数据)
        for(int i=1;i<arrays.length;i++){
            
            temp=arrays[i];
            
            int j=i-1;
            
            //如果前一位(已排序的数据)比当前数据要大，那么就进入循环比较[参考第二趟排序]
            while(j>=0 && arrays[j]>temp){
                
                //往后退一个位置，让当前数据与之前前位进行比较
                arrays[j+1]=arrays[j];
                
                //不断往前，直到退出循环
                j--;
            }
            
            //退出了循环说明找到了合适的位置了，将当前数据插入合适的位置中
            arrays[j+1]=temp;
        }
        System.out.println(Arrays.toString(arrays));
    }
}

希尔排序

在直接插入排序的基础上进行的优化，直接插入排序在n值小的时候效率比较高，在n很大的时候如果待排序序列基本有序，效率依然很高，时间效率可以提升为O(n)，希尔排序也称之为缩小增量排序。

原理：希尔排序也是利用插入排序的思想来排序。希尔排序通过将比较的全部元素分为几个区域来提
升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越
小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已
排好的了，插入效率比较高。

思路：
1.选取一个小于n的整数d（步长）；
2.按照步长d将待排序序列分为d组，从第一个记录开始间隔为d的为一个组；
3.对各组内进行直接插入排序，一趟过后，间隔为d的序列有序，随着有序性的改善，减少步长d重复进行；
4.直到d=1使得间隔为1的记录有序，也就达到了整体有序。 

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
package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arrays = {6,  4321, 432, 344, 55 };
        shellSort(arrays);
        System.out.println(Arrays.toString(arrays));
        
    }
    
    public static void shellSort(int[] arrays){
        
        //增量每次都/2
        for(int step=arrays.length/2;step>0;step/=2){
            
            //从增量那组开始进行插入排序，直至完毕
            for(int i=step;i<arrays.length;i++){
                
                int j=i;
                int temp=arrays[j];
                
                // j - step 就是代表与它同组隔壁的元素
                while(j-step>=0 && arrays[j-step]>temp){
                    arrays[j]=arrays[j-step];
                    j=j-step;
                }
                
                arrays[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
package sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr={ 1, 4, 5, 67, 2, 7, 8, 6, 9, 44, 34, 5, 5, 2, 34, 5, 62, 42, 1, 1324, 2346};
        //int[] arr = {23, 34, 33, 56, 45};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    
    
    /**
     * 快速排序
     *
     * @param arr
     * @param L   指向数组第一个元素
     * @param R   指向数组最后一个元素
     */
    
    public static void quickSort(int[] arr,int L,int R){
        
        int i=L;
        int j=R;
        
        //基准值
        int pivot=arr[(L+R)/2];
        
        //左右两端进行扫描，只要两端还没有交替，就一直扫描
        while(i<=j){
            
            //寻找直到比支点大的数
            while(arr[i]<pivot)
                i++;
            
            //寻找直到比支点小的数
            while(arr[j]>pivot)
                j--;
            
            //此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
            if(i<=j){
                int temp=arr[i];
                arr[i]=arr[j];
                arr[j]=temp;
                i++;
                j--;
            }
        }
        //上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
        
        //“左边”再做排序，直到左边剩下一个数(递归出口)
        if(L<j)
            quickSort(arr,L,j);
        
        //“右边”再做排序，直到右边剩下一个数(递归出口)
        if(i<R)
            quickSort(arr,i,R);     
    }
}

归并排序

归并排序是一种递归算法，不断将列表拆分为一半，如果列表为空或有一个项，则按定义进行排序。如果列表有多个项，我们分割列表，并递归调用两个半部分的合并排序。一旦对两半排序完成，获取两个较小的排序列表并将它们组合成单个排序的新列表的过程。

堆排序

堆是具有以下性质的完全二叉树：

  • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
  • 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序的基本思想是：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。