排序算法的实现

2019/10/04 Algorithm

常用的排序算法的C++实现,并总结算法的时空复杂度。

常见的排序算法的时空复杂度

排序方法 平均时间 最好时间 最坏时间 空间复杂度 稳定性
插入排序 稳定
希尔排序 不稳定
选择排序 不稳定
堆排序 不稳定
冒泡排序 不稳定
快速排序 稳定
归并排序 不稳定

插入排序

思路:待排序的元素(红色)左区域(橙色)是已经排序好的元素,右区域(蓝色)是等候排序的元素,重复遍历左区域找到合适的位置插入。

#include <iostream>
using namespace std;

void InsertSort(int *a, size_t n){
    for(size_t i = 1; i<n; i++){
        int end = i-1;
        int temp = a[i];
        while(end >= 0){
            if(a[end] > temp){
                a[end+1] = a[end];
                end--;
            } else {
                break;
            }
        }
        a[end+1] = temp;
    }
}

希尔排序

思路:希尔排序维护一个gap,将原数组分成gap份,对每份数组执行插入排序算法,然后减少gap值并重复上述操作,直至gap等于1。其中gap满足:

#include <iostream>
using namespace std;

void ShellSort(int *a, size_t n){
    int gap = n;
    while(gap > 1){
        gap = gap/3 + 1;
        for(size_t i = 0; i<n-gap; i++){
            int end = i;
            int temp = a[end+gap];
            while(end >= 0 && a[end] > temp){
                a[end+gap] = a[end];
                end -= gap;
            }
            a[end+gap] = temp;
        }
    }
}

选择排序

思路:不断遍历数组找出其最小值和最大值,将最小值交换到数组最前端,将最大值交换到数组最后端,重复操作。

#include <iostream>
using namespace std;

void SelectSort(int *a, size_t n){
    int begin = 0;
    int end = n-1;
    while(begin < end){
        int minvalueIndex = begin;
        int maxvalueIndex = begin;
        for(size_t i=begin; i<=end; i++){
            if(a[minvalueIndex] > a[i])
                minvalueIndex = i;
            if(a[maxvalueIndex] < a[i])
                maxvalueIndex = i;
        }
        int temp1 = a[begin];
        int temp2 = a[end];
        a[begin] = a[minvalueIndex];
        a[end] = a[maxvalueIndex];
        a[minvalueIndex] = temp1;
        a[maxvalueIndex] = temp2;
        begin++;
        end--;
    }
}

堆排序

思路:将数组转变为最大堆(或最小堆),然后将堆顶元素交换到数组最后一位,重复该操作。注意,升序排序的时候使用最大堆,降序排序的时候使用最小堆。

图中左上方的4步操作是将数组转变为最大堆,建立堆的基本操作就像是泡泡浮出水面一样,最大值往堆顶移动。图中右下方是将堆顶交换到数组的最后一位,然后维护最大堆的性质,不断重复,使得堆变小直到所有值排序完毕。

#include <iostream>
#include <algorithm>
using namespace std;

void AdjustDown(int *A, int root, size_t n){
    int parent = root;
    int leftChild = parent * 2 + 1;
    int rightChild = leftChild + 1;
    int temp = leftChild;
    while(temp < n){
        if(rightChild < n && A[rightChild] > A[leftChild]){
            temp = rightChild;
        }
        if(A[temp] > A[parent]){
            swap(A[temp], A[parent]);
            parent = temp;
            temp = parent * 2 + 1;
            leftChild = temp;
            rightChild = temp + 1;
        } else {
            break;
        }
    }
}

void heapSort(int* A, size_t n){
    // 建堆
    for(int i=(n-2)/2; i>=0; i--){
        AdjustDown(A, i, n);
    }
    // 排序
    int end = n - 1;
    while(end > 0){
        swap(A[0], A[end]);
        AdjustDown(A, 0, end);
        end--;
    }
}

冒泡排序

思路:遍历数组,每每两个相邻元素比较,按照升序或者降序规则调换位置,重复数组长度次直到所有元素排序完毕。

#include <iostream>
#include <algorithm>
using namespace std;

void BubbleSort(int *a, size_t n){
    size_t end = n;
    int exchange = 0;
    while(end > 0){
        for(int i=1; i<end; i++){
            if(a[i-1] > a[i]){
                swap(a[i-1], a[i]);
                exchange = 1;
            }
        }
        // exchange等于0表明数组本身已经是升序,所以程序结束。
        if(exchange == 0){
            break;
        }
        end--;
    }
}

快速排序

快速排序的思路是分治法,将问题划分为若干个子问题,将子问题排序好之后实现对整个数组的排序。

左右指针法

// 1. 将数组的最后一个元素作为基准值
// 2. 分别找出比基准值大、小的值,交换他们的位置。
// 3. 重复2直到LR区间剩余1个值。
// 4. 将剩余区间的值与基准值交换。

// 此时基准值左右分别是比其小的数、比其大的数的集合。

#include <iostream>
using namespace std;

int PartSort(int* a, int L, int R){
    int begin = L;
    int end = R;
    int key = R;

    while(begin < end){
        while(begin < end && a[begin] <= a[key]){
            begin++;
        }
        while(begin < end && a[end] >= a[key]){
            end--;
        }
        swap(a[begin], a[end]);
    }
    swap(a[begin], a[R]);
    return begin;
}

void QuickSort(int* a, int L, int R){
    if(L >= R)
        return;
    int div = PartSort(a, L, R);
    QuickSort(a, L, div-1);
    QuickSort(a, div+1, R);
}

挖坑大法

// 1. 将数组的最后一个元素作为基准值key。
// 2. L寻找比key大的值,将L的值赋给R,此时L相当于一个坑。
// 3. R寻找比key小的值,将R的值赋给L,此时R相当于一个坑。
// 4. 重复该操作直到LR区间为1,将key赋给LR区间。

// 此时基准值左右分别是比其小的数、比其大的数的集合。

#include <iostream>
using namespace std;

int PartSort(int* a, int L, int R){
    int key = a[R];
    while(L < R){
        while(L < R && a[L] <= key){
            L++;
        }
        a[R] = a[L];
        while(L < R && a[R] >= key){
            R--;
        }
        a[L] = a[R];
    }
    a[L] = key;
    return L;
}

void QuickSort(int* a, int L, int R){
    if(L >= R)
        return;
    int div = PartSort(a, L, R);
    QuickSort(a, L, div-1);
    QuickSort(a, div+1, R);
}

前后指针法

// 1. 将数组的最后一个元素作为基准值key。
// 2. cur指针从L开始寻找比key小的值。
// 3. prev指针指向即将要存放cur找到的值。
// 4. 重复该操作直到cur与R之间的区间为1。

// 此时基准值左右分别是比其小的数、比其大的数的集合。

#include <iostream>
using namespace std;

int PartSort(int* a, int L, int R){
    int cur = L;
    int prev = L-1;
    int key = a[R];
    while(cur < R){
        if(a[cur] < key && ++prev != cur)
            swap(a[cur], a[prev]);
        cur++;
    }
    swap(a[++prev], a[R]);
    return prev;
}

void QuickSort(int* a, int L, int R){
    if(L >= R)
        return;
    int div = PartSort(a, L, R);
    QuickSort(a, L, div-1);
    QuickSort(a, div+1, R);
}

归并排序

归并排序的思路是分而治之。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

#include <iostream>
using namespace std;

void merge(int* a, int L, int R, int* tmp){
    if(L >= R)
        return;
    int mid = L + (R-L)/2;
    merge(a, L, mid, tmp);
    merge(a, mid+1, R, tmp);

    int begin1 = L;
    int end1 = mid;
    int begin2 = mid+1;
    int end2 = R;
    int index = L;

    while(begin1 <= end1 && begin2 <= end2){
        if(a[begin1] <= a[begin2])
            tmp[index++] = a[begin1++];
        else
            tmp[index++] = a[begin2++];
    }
    while(begin1 <= end1)
        tmp[index++] = a[begin1++];
    while(begin2 <= end2)
        tmp[index++] = a[begin2++];

    index = L;
    while(index <= R){
        a[index] = tmp[index];
        index++;
    }
}

void MergeSort(int* a, size_t n){
    int* tmp = new int[n];
    merge(a, 0, n-1, tmp);
    delete[] tmp;
}

Search

    Table of Contents