基本排序算法实现

发表于 分类于
本文字数： 6.7k 阅读时长 ≈ 6 分钟

本文介绍一些常见的基本排序算法的实现，以及相应的时间空间负责度分析。包括冒泡排序、插入排序、选择排序、归并排序、快速排序、堆排序这六种比较排序算法，以及计数排序这种线性时间排序算法。算法基于 C++ 语言实现。

1. 冒泡排序

学的第一个算法估计就是冒泡排序算法了。原理很简单，每次从左到右两两比较，把大的交换到后面，每次都会把当前未排序数组的最大元素放到最右边。

步骤：

  1. 从左开始比较相邻的两个元素 nums[j] 和 nums[j+1]，如果 nums[j] > nums[j+1] 就交换两者；
  2. 执行比较和交换，直到到达当前未排序数组的最后一个元素；
  3. 重复执行 1 和 2，直到当前未排序数组只有一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
void bubble_sort(vector<int> &nums){
    vector<int>::size_type i, j;
    for (i = 0; i < nums.size()-1; i++){
        for (j = 0; j+1 < nums.size()-i; j++){
            if (nums[j] > nums[j+1]){
                int temp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = temp;
            }   
        }   
    }   
}

复杂度分析：

由于我们需要执行 n 次冒泡，每次冒泡要执行 n 次比较（实际是 1 到 n 的等差数列，也就是 (1+n)n/2 ），所以总的时间复杂度是 O(n^2) ；只需要常数个额外的元素空间存储临时数据，空间复杂度为 O(1)。

2. 插入排序

插入排序的原理是从左向右，把当前位置的数与它前面的数进行比较，找到最适合它的位置放入，使前面部分有序。

步骤：

  1. 选出当前位置的数 nums[i]，从左向右，将 nums[i] 与它前面的每一个元素相比较，如果 nums[i] < nums[j]，则将 nums[i] 与 nums[j] 交换；
  2. 再选择 nums[i+1] 与其前面的数进行比较。
1
2
3
4
5
6
7
8
9
10
11
void insert_sort(vector<int> &nums){
    for (size_t i = 1; i < nums.size(); i++){
        for (size_t j = 0; j < i; j++){
            if (nums[i] < nums[j]){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }   
        }   
    }   
}

复杂度分析：

总共要插入 n 次，每次插入的复杂度是 O(n)，所以总的时间复杂度为 O(n^2)，空间复杂度为 O(1)。

3. 选择排序

选择排序的原理是，每次都从乱序数组中找到最小值，放到当前乱序数组头部，最终使数组有序。

步骤：

  1. 从左开始，选择后面元素中最小值，和当前元素交换；
  2. 直到未排序数组只有一个元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
void select_sort(vector<int> &nums){                             
    for (size_t i = 0; i < nums.size()-1; i++){                               
        size_t min_index = i;                                                 
        for (size_t j = i+1; j < nums.size(); j++){                           
            if (nums[j] < nums[min_index]){                                   
                min_index = j;                                                
            }                                                                 
        }
        int temp = nums[i];
        nums[i] = nums[min_index];
        nums[mid_index] = temp;                                       
    }                                                                         
}

复杂度分析：

需要选择 n 次最小值，且每次选择最小值的复杂度又是 O(n)，所以总共的时间复杂度为 O(n^2)；空间复杂度为 O(1)。

4. 归并排序

归并排序是采用分治法的一个典型例子。这个排序的特点是把一个数组打散成小数组，然后再把小数组拼凑再排序，直到最终数组有序。

步骤：

  1. 把当前数组分化成 n 个单位为 1 的子数组，然后两两比较合并单位为 2 的 n/2 个子数组；
  2. 继续进行这个过程，按照 2 的倍数进行子数组的比较合并，直到最终数组有序；
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 merge_sort(vector<int> &nums){                               
    _merge_sort(nums, 0, nums.size()-1);                                      
}                                                                             
                                                                              
void _merge_sort(vector<int> &nums, int begin, int end){          
    if (begin < end){                                                         
        int mid = (begin + end)/2;                                            
        _merge_sort(nums, begin, mid);                                        
        _merge_sort(nums, mid+1, end);                                        
        _merge(nums, begin, mid, end);                                        
    }                                                                         
}                                                                             
                                                                              
void _merge(vector<int> &nums, int begin, int mid, int end){      
    vector<int> tmp; /* 非空间原址排序 */                                     
    int i = begin, j = mid+1;                                                 
    while ( (i != mid+1) && (j != end+1) ){                                   
        if (nums[i] <= nums[j])                                               
            tmp.push_back(nums[i++]);                                         
        else                                                                  
            tmp.push_back(nums[j++]);                                         
    }                                                                         
                                                                              
    while ( i != mid+1 )                                                      
        tmp.push_back(nums[i++]);                                             
                                                                              
    while ( j != end+1 )                                                      
        tmp.push_back(nums[j++]);                                             
                                                                              
    for (size_t i = 0; i < tmp.size(); i++)                                   
        nums[begin+i] = tmp[i];                                               
}

复杂度分析：

采用分治法，可以将循环的次数减少为 logn，所以总共的时间复杂度为 O(nlogn)；

因为在合并数组时需要申请一个临时数组，所以算法的空间复杂度为 O(n)。

5. 快速排序

快速排序算法也是利用分治法实现的一个排序算法。快速排序与归并排序不同，它不是一半一半的分子数组，而是选择一个主元，把比这个数小的挪到左边，把比这个数大的移到右边。然后不断对左右两部分也执行相同的步骤，直到整个数组有序。

步骤：

  1. 选择一个主元，一般选择最后一个元素（或者随机选取，保证平均性能）；
  2. 将小于主元的移到左边，大于主元的移到右边；
  3. 递归的对子数组重复执行1,2，直到整个数组有序。
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 quick_sort(vector<int> &nums){                               
    _quick_sort(nums, 0, nums.size()-1);                                      
}                                                                             
                                                                              
void _quick_sort(vector<int> &nums, int p, int r){                
    if (p < r){                                                               
        int q = _partition(nums, p, r);                                       
        _quick_sort(nums, p, q-1);                                            
        _quick_sort(nums, q+1, r);                                            
    }                                                                         
}                                                                             
                                                                              
int _partition(vector<int> &nums, int p, int r){                  
    int x = nums[r];                                                          
    int i = p-1;                                                              
    for (int j = p; j < r; j++){                                              
        if (nums[j] <= x){                                                    
            i = i+1;                                                          
            swap(nums[i], nums[j]);                                           
        }                                                                     
    }                                                                         
    swap(nums[i+1], nums[r]);                                                 
    return i+1;                                                               
}

复杂度分析：

快速排序算法的平均时间复杂度为 O(nlogn)，但存在一些情况使得其时间复杂度为 O(n^2)，如数组是已排序的情况；

时间复杂度为 O(1)。

6. 堆排序

堆排序常用于求一个数组中最大 k 个元素。因为堆实际上是一个完全二叉树，所以用它可以用一维数组来表示。因为最大堆的第一位总为单签堆中的最大值，所以每次将最大值移除后，调整堆即可获得下一个最大值，通过一遍一遍执行这个过程就可以得到前 k 大元素，或者使堆有序。（最小堆的概念与最大堆对应）

步骤：

  1. 构造最大堆：首先将当前元素放入最大堆下一个位置，然后将此元素依次和它的父节点比较，如果大于父节点就和父节点交换，直到比较到根节点。重复执行到最后一个元素。
  2. 调整最大堆：即将根节点移除后重新整理堆。整理方法为将根节点和最后一个节点交换，然后把堆看做n-1长度，将当前根节点逐步移动到其应该在的位置。
  3. 堆排序：重复执行2，直到所有根节点都已移除。
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
void heap_sort(vector<int> &nums){                                 
    build_heap(nums);                                                         
    int heap_size = nums.size();                                              
    for (int i = nums.size()-1; i > 0; i--){                                  
        swap(nums[0], nums[i]);                                               
        heap_size--;                                                          
        heapify(nums, 0, heap_size);                                          
    }                                                                         
}                                                                             
                                                                              
void build_heap(vector<int> &nums){                                
    for (int i = nums.size()/2 - 1; i >= 0; i--)                              
        heapify(nums, i, nums.size()-1);                                      
}                                                                             
                                                                              
void heapify(vector<int> &nums, int root, int heap_size){          
    int left = 2*root, right = 2*root+1;                                      
    int max_index = root;                                                     
    if ( left < heap_size && nums[left] > nums[root] )                        
        max_index = left;                                                     
    if ( right < heap_size && nums[right] > nums[max_index] )                 
        max_index = right;                                                    
    if ( max_index != root ){                                                 
        swap(nums[max_index], nums[root]);                                    
        heapify(nums, max_index, heap_size);                                  
    }                                                                         
}

复杂度分析：

堆执行一次调整需要 O(logn) 的时间，在排序过程中需要遍历所有元素执行堆调整，所以最终时间复杂度为 O(nlogn)；空间复杂度为 O(1)。

7. 计数排序

计数排序假设 n 个输入元素中的每一个都是在 0 到 k 区间内的一个整数，其中 k 为某个整数。当 k = O(n) 时，排序的运行时间为 O(n)。

计数排序的基本思想是：对每一个输入元素 x，确定小于 x 的元素个数。利用这一信息，就可以直接把 x 放到它在输出数组中的位置上了。

在计数排序算法的代码中，假设输入是一个数组 nums[0..n-1]，nums.size() = n。我们还需要两个数组： ans[0..n-1] 存放排序的输出，C[0..k] 提供临时存储空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
void count_sort(vector<int> &nums, vector<int> &ans, int k){                  
    vector<int> C(k+1, 0);                                                    
    for (size_t i = 0; i < nums.size(); i++)                                  
        C[nums[i]] = C[nums[i]] + 1;                                          
                                                                              
    for (int j = 1; j <= k; j++)                                              
        C[j] += C[j-1];                                                       
                                                                              
    for (int i = nums.size()-1; i >= 0; i--){                                 
        ans[C[nums[i]]-1] = nums[i];                                          
        C[nums[i]] -= 1;                                                      
    }                                                                         
}

复杂度分析：

时间复杂度为 O(n)，空间复杂度也为 O(n)。

8. 希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破 O(n^2) 的第一批算法之一。

直接插入排序算法的算法时间复杂度为 O(n^2) ，但是，若待排记录序列为 “正序” 时，其时间复杂度可提高至 O(n)。另外一方面，当 n 值较小时，直接插入排序算法的效率也比较高。希尔排序算法正是从这两点分析出发对直接插入排序算法进行改进的。

它的基本思想：先将整个待排序序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对整体序列进行一次直接插入排序。

简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

基本步骤：

在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…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
// 针对有序序列在插入时采用交换法
void shell_sort(vector<int>& nums){
    int gap = nums.size()/2;
    //增量gap，并逐步缩小增量
    while (gap > 0){   
        //从第gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < nums.size(); i++){  
            int j = i;
            while (j-gap >= 0 && nums[j] < nums[j-gap]){
                swap(nums[j], nums[j-gap]);   //插入排序采用交换法
                j -= gap;
            } 
        } 
        gap /= 2;
    } 
}

// 针对有序序列在插入时采用移动法
void shell_sort(vector<int>& nums){
    int gap = nums.size()/2;
    //增量gap，并逐步缩小增量
    while (gap > 0){
        //从第gap个元素，逐个对其所在组进行直接插入排序操作
        for (int i = gap; i < nums.size(); i++){
            int j = i;
            int tmp = nums[j];   //记录nums[j]的值
            while (j-gap >= 0 && nums[j] < nums[j-gap]){
                nums[j] = nums[j-gap];   //把前一个值直接往后移
                j -= gap;
            }
            nums[j] = tmp;   //将记录的值放到该放的位置
        }
        gap /= 2;
    }
}

复杂度分析：

希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列{n/2, (n/2)/2 , …,1}(希尔增量)，其最坏时间复杂度依然为O(n^2^)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2^)。