算法之排序

引言

本文将结合图文、Cpp 代码以及相应的例题,整理总结一些典型的排序算法。

首先,推荐一个算法可视化网站VisuAlgo,文中动图皆录屏于自此。

鉴于动图非常好理解,代码也易懂,就不赘述了,原理摘选于百度百科。

  1. 冒泡排序(Bubble Sort)
  2. 选择排序(Selection Sort)
  3. 插入排序(Insertion Sort)
  4. 归并排序(Merge Sort)
  5. 快速排序(Quick Sort)
  6. 内置函数 sort

排序算法

冒泡排序(Bubble Sort)

原理:重复地走访过要排序的元素列,依次比较两个相邻的元素,如果他们的顺序(如从大到小、首字母从A到Z)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。

Bubble

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;

void BubbleSort(int arr[], int len);

int main(){
    int arrays[] = {1, 5, 3, 9, 6, 4, 7, 2, 8};
    int length = sizeof(arrays)/sizeof(arrays[0]);
    BubbleSort(arrays, length);
}

void BubbleSort(int arr[], int len){
    bool swapped;
    do{
        swapped = false;
        for (int i = 0; i < len; i++){
            if (arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                swapped = true;
            }
        }
    }while(swapped);
}

选择排序(Selection Sort)

原理:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。

Selection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
using namespace std;

void SelectionSort(int arr[], int len);

int main(){
    int arrays[] = {1, 5, 3, 9, 6, 4, 7, 2, 8};
    int length = sizeof(arrays)/sizeof(arrays[0]);
    SelectionSort(arrays, length);
}

void SelectionSort(int arr[], int len){
    int index = 0, current;
    do{
        current = index;
        for (int i = index + 1; i < len; i++){
            if (arr[i] < arr[current]){
                current = i;
            }
        }
        swap(arr[current], arr[index]);
        index++;
    }while(index < len);
}

插入排序(Insertion Sort)

原理:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。

Insertion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;

void InsertionSort(int arr[], int len);

int main(){
    int arrays[] = {1, 5, 3, 9, 6, 4, 7, 2, 8};
    int length = sizeof(arrays)/sizeof(arrays[0]);
    InsertionSort(arrays, length);
}

void InsertionSort(int arr[], int len){
    int i, j, temp;
    for (i = 1; i < len; i++){
        temp = arr[i];
        for (j = i - 1; j >= 0 && arr[j] > temp; j--){
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = temp;
    }
}

归并排序(Merge Sort)

原理:该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。

Merge

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
#include<iostream>
using namespace std;

void MergeSort(int arr1[], int arr2[], int left, int right);
void Merge(int arr1[], int arr2[], int left, int mid, int right);

int main(){
    int arr1[] = {1, 5, 3, 9, 6, 4, 7, 2, 8}, arr2[9];
    int length = sizeof(arr1)/sizeof(arr1[0]);
    MergeSort(arr1, arr2, 0, length - 1);
}

void MergeSort(int arr1[], int arr2[], int left, int right){
    // 如果只有一个元素,则无需排序
    if (left == right){
        return;
    }else{
        int mid = (left + right) / 2;
        // 拆分左边
        MergeSort(arr1, arr2, left, mid);
        // 拆分右边
        MergeSort(arr1, arr2, mid + 1, right);
        // 合并
        Merge(arr1, arr2, left, mid, right);
    }
}

void Merge(int arr1[], int arr2[], int left, int mid, int right){
    int l = left, r = mid + 1, index = left;
    // 一一判断两数组各元素大小,有序放入新数组中
    while (l <= mid && r <= right){
        if (arr1[l] <= arr1[r]){
            arr2[index++] = arr1[l++];
        }else{
            arr2[index++] = arr1[r++];
        }
    }
    while (l <= mid){
        arr2[index++] = arr1[l++];
    }
    while (r <= right){
        arr2[index++] = arr1[r++];
    }
    // 将有序数组存入原数组
    for (int i = 0; i <= right; i++){
        arr1[i] = arr2[i];
    }
}

快速排序(Quick Sort)

原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

Quick

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
#include<iostream>
using namespace std;

void QuickSort(int arrays[], int left, int right);

int main(){
    int arrays[] = {1, 5, 3, 9, 6, 4, 7, 2, 8};
    int length = sizeof(arrays)/sizeof(arrays[0]);
    QuickSort(arrays, 0, length-1);
}

void QuickSort(int arrays[], int left, int right){
    if (left >= right){
        return;
    }
    // 将最左端元素设为 pivot
    int pivotIndex = left;
    int storeIndex = pivotIndex + 1;
    // 与 pivot 比较,将比他小的元素都移向一侧
    for (int i = pivotIndex + 1; i <= right; i++){
        if (arrays[i] < arrays[pivotIndex]){
            swap(arrays[i], arrays[storeIndex++]);
        }
    }
    // 交换后,以原 pivot 为中心,左侧比他小,右侧比他大
    swap(arrays[pivotIndex], arrays[--storeIndex]);
    // 排序原 pivot 左侧元素
    QuickSort(arrays, left, storeIndex - 1);
    // 排序原 pivot 右侧元素
    QuickSort(arrays, storeIndex + 1, right);
}

计数排序(Counting Sort)

原理:对于给定的输入序列中的每一个元素x,确定该序列中值小于x的元素的个数(此处并非比较各元素的大小,而是通过对元素值的计数和计数值的累加来确定)。

Counting

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
#include<iostream>
using namespace std;

void CountingSort(int arrays[], int bucket[], int length);

int main(){
    int arrays[] = {1, 5, 3, 9, 6, 4, 7, 2, 8};
    int bucket[10] = {0};
    int length = sizeof(arrays)/sizeof(arrays[0]);
    CountingSort(arrays, bucket, length);
}

void CountingSort(int arrays[], int bucket[], int length){
    for (int i = 0; i < length; i++){
        bucket[arrays[i]]++;
    }
    int index = 0;
    for (int i = 1; i < 10; i++){
        while (bucket[i]){
            arrays[index] = i;
            index++;
            bucket[i]--;
        }
    }
}

内置函数 sort

  1. 需要头文件
  2. 语法描述:sort(begin, end, cmp),其中 cmp 参数可自行编写排序规则,默认为升序排序。
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<algorithm>
using namespace std;

bool cmp(int x, int y){
    return x < y;
}

int main(){
    int arrays[] = {1, 5, 3, 9, 6, 4, 7, 2, 8};
    int length = sizeof(arrays)/sizeof(arrays[0]);
    sort(arrays, arrays + length, cmp);
}

实例-成绩排序

成绩排序

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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

struct Student{
    char name[101];
    int age;
    int score;
}S[1001];

bool cmp(Student a, Student b){
    if (a.score != b.score) return a.score < b.score;
    int tmp = strcmp(a.name, b.name);
    if (tmp != 0)
        return tmp < 0;
    else
        return a.age < b.age;
}

int main(){
    int n;
    while (cin >> n){
        for (int i = 0;i < n;i++){
            cin >> S[i].name >> S[i].age >> S[i].score;
        }
        sort(S, S + n, cmp);
        for (int i = 0;i < n;i++){
            cout << S[i].name << " " << S[i].age << " " << S[i].score << endl;
        }
    }
}

真题:成绩排序