Sorting Algorithms

Posted on Edited on In Disqus:
The description of some sorting algorithms, and how to implement then with C++.

[TOC]

插入排序

  • 概念: 从头到尾逐个处理数据，将当前数据和它前面的序列进行比较：若当前数据小于前一个数据，则交换位置；否则移动数组，处理下一个数据
  • 特征: 稳定
  • 性能: O(n) / O(n^2) / O(n^2)
  • 代码: 
1
2
3
4
5
6
template<class type>
void insSort(type Arr[], int size){
    for(int i = 0; i < size-1; i++)
        for(int j = i+1; j >= 1 && Arr[j] < Arr[j-1]; j--)
            swap(Arr, j-1, j);
}

冒泡排序

  • 概念: 从头到尾逐个处理数据，每次将当前数据和它后面的序列进行比较：若当前数据大于后一个数据，则交换位置，并后移下标；否则仅后移下标
  • 特征: 稳定
  • 性能: O(n^2) / O(n^2) / O(n^2)
  • 代码:
1
2
3
4
5
6
7
template<class type>
void bubSort(type Arr[], int size){
    for(int i = 0; i < size; i++)
        for(int j = size-1; j > i; j--)
            if(Arr[j] < Arr[j-1])
                swap(Arr, j-1, j);
}

选择排序

  • 概念: 第i次选择数组中第i小的数值，插入到第i个位置
  • 特征: 不稳定
  • 性能: O(n^2) / O(n^2) / O(n^2)
  • 代码: 
1
2
3
4
5
6
7
8
9
10
11
template<class type>
void selSort(type Arr[], int size){
    for(int i = 0; i < size; i++){
        int lowIndex = i;
        for(int j = i+1; j < size; j++){
            if(Arr[lowIndex] > Arr[j])
                lowIndex = j;
        }
        swap(Arr, i, lowIndex);
    }
}

shell排序

  • 概念: 用 Gap 将数组等分划分，对较小的划分数组进行插入排序，再将较小的划分数组合并为较大的数据，并进行插入排序，直到得到完整的有序数组

  • 特征: 不稳定

  • 性能 (Gap = 2): O(n) / O(n^2) / O(n^1.5)

  • 代码:

1
2
3
4
5
6
7
8
9
10
11
template<class type>
void shellSort(type Arr[], int size, int gap){
    for(int inc = size/gap; inc > 0; inc/=gap){
        for(int i = 0; i < inc; i++){
            for(int j = i; j < size-inc; j+=inc){
                for(int k = j+inc; k >= inc && Arr[k] < Arr[k-inc]; k-=inc)
                    swap(Arr, k-inc, k);
            }
        }
    }
}

快速排序

  • 概念: 选择数组中的一个数字作为轴值，将比轴值小的数放在轴值左边，比轴值大的数放在轴值右边，并通过递归依次处理轴值左边和右边的序列
  • 特征: 不稳定
  • 性能: O(nlogn) / O(n^2) / O(nlogn)
  • 代码:
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<class type>
int partition(type Arr[], int left, int right){
    int tmp = left;
    int tmp_val = Arr[tmp];
    left++;

    while(true){
        while(left <= right && Arr[left] <= tmp_val)  left++;
        while(left <= right && Arr[right] >= tmp_val) right--;
        if(left > right)    break;
        swap(Arr, left, right);
    }
    swap(Arr, tmp, right);
    return right;
}

template<class type>
void quickSort(type Arr[], int left, int right){
    if(left >= right) return;

    int p = partition(Arr, left, right);
    quickSort(Arr, left, p-1);
    quickSort(Arr, p+1, right);
}

归并排序

  • 概念: 每次通过递归将数组划分为长度相同的子序列，并用临时数组来进行排序；接着将子序列合并为一个更大的数组并排序
  • 特征: 稳定 / 使用等长度的临时数组 (也可以通过 reverse 来实现)
  • 性能: O(nlogn) / O(nlogn) / O(nlogn)
  • 代码:
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
template<class type>
void mergeSortCore(type Arr[], type tmp[], int left, int right){
    if(left >= right)   return;

    int mid = left + (right - left) / 2;
    mergeSortCore(Arr, tmp, left, mid);
    mergeSortCore(Arr, tmp, mid+1, right);
    
    int i = left, j = mid + 1, cur = left;
    while(i <= mid && j <= right){
        if(Arr[i] < Arr[j]) tmp[cur++] = Arr[i++];
        else tmp[cur++] = Arr[j++];
    }
    
    while(i <= mid) tmp[cur++] = Arr[i++];
    while(j <= right)   tmp[cur++] = Arr[j++];
    
    for(cur = left; cur <= right; cur++)
        Arr[cur] = tmp[cur];
}

template<class type>
void mergeSort(type Arr[], int size){
    type *tmp_arr = new type[size];
    mergeSortCore(Arr, tmp_arr, 0, size-1);
    delete[] tmp_arr;
}
  • 优化: 不需要临时数组

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
template<class type>
void reverse(type Arr[], int len){
    int i = 0, j = len-1;
    while(i < j)  swap(Arr, i++, j--);
}

template<class type>
void exchange(type Arr[], int leftLen, int rightLen){
    reverse(Arr, leftLen);
    reverse(Arr + leftLen, rightLen);
    reverse(Arr, leftLen + rightLen);
}

template<class type>
void mergeSortExchange(type Arr[], int left, int mid, int right){
    int i = left, j = mid + 1;
    while(i <= mid && j <= right){
        while(i <= mid && Arr[i] <= Arr[j])   i++;
        while(j <= right && Arr[j] < Arr[i])   j++;
        exchange(Arr + i, mid + 1 - i, j - mid - 1);
        
        i = i + j - mid;
        mid = j - 1;
    }

}

template<class type>
void mergeSortNoTmp(type Arr[], int left, int right){
    if(left >= right)   return;

    int mid = left + (right - left) / 2;
    mergeSortNoTmp(Arr, left, mid); // [left, mid]
    mergeSortNoTmp(Arr, mid + 1, right);    // [mid+1, right]
    mergeSortExchange(Arr, left, mid, right);

}

堆排序

  • 概念: 构建最大堆，每次将堆顶元素弹出，并用剩余元素继续构建最大堆，直到空堆

  • 特征: 不稳定

  • 性能: O(nlogn)

  • 代码:

    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
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    template<class type>
    void pushHeap(type Arr[], int hole){
        type t = Arr[hole];
        int parent = (hole - 1) / 2;
        while(hole > 0 && Arr[parent] < t){
            Arr[hole] = Arr[parent];
            hole = parent;
            parent = (hole - 1) / 2;
        }
        Arr[hole] = t;
    }

    template<class type>
    void popHeap(type Arr[], int size){
        type t = Arr[size-1];
        Arr[size-1] = Arr[0];
        size--;

        int hole = 0;
        int child = 2 * (hole + 1);
        while(child < size){
            if(Arr[child - 1] > Arr[child])
                child--;
            Arr[hole] = Arr[child];
            hole = child;
            child = 2 * (hole + 1);
        }
        if(child == size){
            Arr[hole] = Arr[child - 1];
            hole = child - 1;
        }
        Arr[hole] = t;
        pushHeap(Arr, hole);

    }

    template<class type>
    void makeHeap(type Arr[], int size){
        for(int i = 0; i < size; i++)
            pushHeap(Arr, i);
    }

    template<class type>
    void makeHeap2(type Arr[], int size){
        int parent = (size - 2) / 2;

        while(parent >= 0){
            int hole = parent;
            int child = 2 * (hole + 1);
            type t = Arr[hole];
        
            while(child < size){
                if(Arr[child - 1] > Arr[child])
                    child--;
                Arr[hole] = Arr[child];
                hole = child;
                child = 2 * (hole + 1);
            }
            if(child == size){
                Arr[hole] = Arr[child - 1];
                hole = child - 1;
            }
            Arr[hole] = t;
            pushHeap(Arr, hole);
            parent--;
        }

    }

    template<class type>
    void heapSort(type Arr[], int size){
        makeHeap(Arr, size);
        // makeHeap2(Arr, size);
        for(int j = size; j>1; j--)
            popHeap(Arr, j);
    }

代码下载地址：https://xiaoli777.github.io/codes/Sortings.cpp