梅庄

算法回顾---简单排序算法

发表于 | 分类于
选择排序&插入排序&冒泡排序&希尔排序

简单算法比较

为什么要学习$ O(n^2) $的排序算法

  • 基础
  • 编码简单，易于实现，是一些简单情境的首选
  • 在一些特殊情况下，简单的排序算法更有效
  • 简单的排序算法思想衍生出复杂的排序算法
  • 作为子过程，改进更复杂的排序算法

选择排序

从左到右，每次找最小的元素，然后swap到当前i的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
void selectionSort(T arr[], int n)
{
    for(int i = 0; i<n; i++)
    {
//      寻找[i, n)区间里的最小值
        int minIndex = i;
        for(int j = i+1; j<n; j++)
        {
            if(arr[j] < arr[minIndex])  minIndex = j;
        }
        swap(arr[i], arr[minIndex]);
    }
}

插入排序

想象拍扑克牌
在前面已经排好的元素中，找当前要排元素要插入的位置，然后把该要排元素插进去即可
(将每一个要排的元素与前面序列中每一个元素前面那一个元素作比较)
与选择排序的区别

  • 插入排序在第二重循环可以提前结束

    基础版本

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    template<typename T>
    void insertionSort(T arr[], int n) 
    {
        for(int i = 1; i<n; i++)
        {
    //      寻找元素arr[i]合适的插入位置
    //      与j位置元素前面那一个位置的元素作比较
    //      第二重循环可以提前结束 
             for(int j = i; j>0; j--) 
             {
                if(arr[j] < arr[j-1])
                    swap(arr[j], arr[j-1]);
                else
                    break; 
             }
        }
    }

为什么基础版本的插入排序比选择排序还要差

  • 因为插入排序每次都有交换，交换每次有三次操作，比赋值耗时的多
  • 而选择排序每次遍历，只有最后才交换一次，少了大量的交换操作

改进版本

每次把要排的元素先拿出来，保存一个副本，将交换操作用赋值操作代替

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename T>
void insertionSort(T arr[], int n) 
{
    for(int i = 1; i<n; i++)
    {
//      寻找元素arr[i]合适的插入位置
//      与j位置元素前面那一个位置的元素作比较
//      第二重循环可以提前结束 
        T e = arr[i];
        int j;  //保存元素e应该插入的位置 
         for(j = i; j>0; j--) //注意这里不能写成int j = i
         {
            if(arr[j-1] > e)    arr[j] = arr[j-1];
            else break;
         }
         arr[j] = e;
    }
}

当数组中元素近乎有序的时候，插入排序相当可以
当基本上有序的时候，插入排序的复杂度$O(n)$就可以解决

  • 选择排序不论是否有序，两重循环都必须执行完成
  • 而插入排序可以提前跳出第二重循环，在数组近乎有序时，可以达到O(n)

冒泡排序

冒泡排序整体性能比不上插入排序
优化：

  1. 如果上一次冒泡排序没做调整，那说明已经有序了，后面也不用动
  2. 优化,每一趟Bubble Sort都将最大的元素放在了最后的位置
    所以下一次排序,最后的元素可以不再考虑
    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
    template<typename T>
    void bubbleSort( T arr[] , int n){
        bool swapped;
        //int newn; // 理论上,可以使用newn进行优化,但实际优化效果较差
        do{
            swapped = false;
            //newn = 0;
            for( int i = 1 ; i < n ; i ++ )
                if( arr[i-1] > arr[i] ){
                    swap( arr[i-1] , arr[i] );
                    swapped = true;
                    // 可以记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                    // 实际优化效果较差,因为引入了newn这个新的变量
                    //newn = n;
                }
            //n = newn;
            // 优化,每一趟Bubble Sort都将最大的元素放在了最后的位置
            // 所以下一次排序,最后的元素可以不再考虑
            // 理论上,newn的优化是这个优化的复杂版本,应该更有效
            // 实测,使用这种简单优化,时间性能更好
            n --;
        }while(swapped);
    }

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename T>
void shellSort(T arr[], int n){
    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
    int h = 1;
    while( h < n/3 )
        h = 3 * h + 1;
    while( h >= 1 ){
        // h-sort the array
        for( int i = h ; i < n ; i ++ ){
            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for( j = i ; j >= h && e < arr[j-h] ; j -= h )
                arr[j] = arr[j-h];
            arr[j] = e;
        }
        h /= 3;
    }
}

插入排序–>希尔排序
(尝试和之前第h个元素进行比较)
将h逐渐从一个很大的数缩小到1，将一个无序的数组一步一步缩小到一个近乎有序的数组
复杂度可以达到$O(n^1.5)$
当n = 10 0000

随机数组的情况

排序算法 所用时间
Selection Sort 29.424s
Insertion Sort 18.096s
Bubble Sort 67.163s
Shell Sort 0.053 s

近乎有序的情况

排序算法 所用时间
Selection Sort 26.942s
Insertion Sort 0.017 s
Bubble Sort 14.799s
Shell Sort 0.015 s