排序

冒泡排序

思想

冒泡排序是一个基于交换的排序。每一轮将序列中的最大值放到序列的尾部。循环每次先确定结尾length的值，然后从头遍历到最后寻找最大值，然后length再减减。

代码

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
#include <iostream>
#include <algorithm> 
#include <cstdlib>
#include <ctime>
#define MAXSIZE 10
void initArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        arr[i] = std::rand() % 20;
    }
}
void showArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}
void bubSort(int arr[], int length) {
    bool swapped;
    for (int i = 0; i < length - 1; i++) {
        swapped = false;
        for (int j = 0; j < length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; 
    }
}
int main() {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    int arr[MAXSIZE];
    initArr(arr, MAXSIZE);
    std::cout << "随机数组：";
    showArr(arr, MAXSIZE);
    bubSort(arr, MAXSIZE);
    std::cout << "排序后数组：";
    showArr(arr, MAXSIZE);
    system("pause");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
冒泡排序
void bubSort(int arr[], int length) {
    bool swapped;
    for (int i = 0; i < length - 1; i++) {
        swapped = false;
        for (int j = 0; j < length - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                std::swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break; 
    }
}

选择排序

思想

选择排序是一个基于交换的排序。循环每次都是先确定首位，然后从第一个开始遍历找最小值，然后首位再加加，再遍历。

代码

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
#include <iostream>
#include <algorithm> 
#include <cstdlib>
#include <ctime>
#define MAXSIZE 10

void initArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void selectSort(int arr[], int length) {
    for (int i = 0; i < length; ++i) {
        int k = i;
        for (int j = i + 1; j < length; ++j) {
            if (arr[j] < arr[k]) {
                k = j;
            }
        }
        std::swap(arr[i], arr[k]);
    }
}
int main() {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    int arr[MAXSIZE];
    initArr(arr, MAXSIZE);
    showArr(arr, MAXSIZE);
    selectSort(arr, MAXSIZE);
    showArr(arr, MAXSIZE);
    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
选择排序
void selectSort(int arr[], int length) {
    for (int i = 0; i < length; ++i) {
        int k = i;
        for (int j = i + 1; j < length; ++j) {
            if (arr[j] < arr[k]) {
                k = j;
            }
        }
        std::swap(arr[i], arr[k]);
    }
}

插入排序

思想

优点是：当原始学列已经基本有序时，再将一个新的数据插入进来比较方便和高效。

代码

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
#include <iostream>
#include <algorithm> 
#include <cstdlib>
#include <ctime>
#define MAXSIZE 10

void initArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void insertSort(int arr[], int length) {
    for (int i = 1; i < length; ++i) {
        for (int j = i; j >= 1 && arr[j] < arr[j - 1]; --j) {
            std::swap(arr[j], arr[j - 1]);
        }
    }
}

int main() {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    int arr[MAXSIZE];
    initArr(arr, MAXSIZE);
    showArr(arr, MAXSIZE);
    insertSort(arr, MAXSIZE);
    showArr(arr, MAXSIZE);
    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
插入排序
void insertSort(int arr[], int length) {
    for (int i = 1; i < length; ++i) {
        for (int j = i; j >= 1 && arr[j] < arr[j - 1]; --j) {
            std::swap(arr[j], arr[j - 1]);
        }
    }
}

希尔排序

思想

优化版的插入排序。适用于数据大的排序。优化点：步长增大了。原来插入排序的步长时1，而希尔排序的步长可以很大，可以逐渐减小到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
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm> 
#include <cstdlib>
#include <ctime>
#define MAXSIZE 10

void initArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void shellSort(int arr[], int length) {
    int h = 1;
    int t=length/3;
    while(h<t)
    	h=h*3+1;
    while (h >= 1) {
        for (int i = h; i < length; ++i) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                std::swap(arr[j], arr[j - h]);
            }
        }
        h /= 3;
    }
}

int main() {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    int arr[MAXSIZE];
    initArr(arr, MAXSIZE);
    showArr(arr, MAXSIZE);
    shellSort(arr, MAXSIZE);
    showArr(arr, MAXSIZE);
    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
希尔排序
void shellSort(int arr[], int length) {
    int h = 1;
    int t=length/3;
    while(h<t)
    	h=h*3+1;
    while (h >= 1) {
        for (int i = h; i < length; ++i) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                std::swap(arr[j], arr[j - h]);
            }
        }
        h /= 3;
    }
}

快速排序

思想

冒泡排序的优化版本。使用轴，每一轮左右递归后，把轴放到中间，使得轴的左边都比轴小，轴的右边都比轴大。当所有的递归都结束就自然排好序了。

代码

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
#include <iostream>
#include <algorithm> 
#include <cstdlib>
#include <ctime>
#define MAXSIZE 10

void initArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(int arr[], int length) {
    for (int i = 0; i < length; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left;
    int j = right;
    int pivot = arr[left]; // Choose leftmost element as pivot
    while (i < j) {
        while (i < j && arr[j] >= pivot) --j;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] <= pivot) ++i;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

int main() {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    int arr[MAXSIZE];
    initArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    quickSort(arr,0,MAXSIZE-1);
    showArr(arr,MAXSIZE);
    system("pause");
    return 0;
}

快速排序1：pivot先确定为left的值，然后i从第一个数开始遍历，j从最后一个数开始遍历，当j指向的数比pivot小时，j指向的数就覆盖pivot指向的数，然后i指向的数比pivot大时，i指向的数就覆盖j指向的位置（此时j指向的位置为空），然后继续遍历j，直到i和j同时指向一个位置时，将pivot放到该位置上。然后再给pivot重新赋值，此时要从pivot的左边序列和右边序列的第一个数重新赋给pivot，然后重复上述过程，也就是反复左右递归。直到序列完整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void quickSort(int arr[], int left, int right) {
    if (left >= right) return;
    int i = left;
    int j = right;
    int pivot = arr[left]; // Choose leftmost element as pivot
    while (i < j) {
        while (i < j && arr[j] >= pivot) --j;
        if (i < j) arr[i++] = arr[j];
        while (i < j && arr[i] <= pivot) ++i;
        if (i < j) arr[j--] = arr[i];
    }
    arr[i] = pivot;
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

快速排序2：让i、j都从第二个数开始遍历，直到j指向最后一个数，这时i的左边都比pivot小，j的左边都比pivot大，然后再把pivot放在中间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void quickSort(int arr[], int left, int right) {
    if(left>=right)
    	return;
    int pivot=arr[left];
    int i=left+1;
    int j=left+1;
    while(j<=right){
    	if(arr[j]<pivot)
    	{
    		std::swap(arr[i],arr[j]);
    		i++;
		}
		j++;
	}
	std::swap(arr[left],arr[i-1]);
	quickSort(arr,left,i-2);
	quickSort(arr,i,right);
}

快速排序的两个算法，一个是递归反复给pivot赋值且只适合顺式存储。另一个则是先让i、j都排序好后再将pivot的值放到中间，不用再反复递归，虽然时间复杂度比前一个高，但是适合链式存储。

归并排序

思想

基于分而治之的思想。拿两个已经有序的序列重新组合成一个新的有序序列。

代码

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
#include <iostream>
#include <vector>
#include <algorithm> 
#include <cstdlib>
#include <ctime>

void initVector(std::vector<int>& vec, int length) {
    for (int i = 0; i < length; i++) {
        vec.push_back(std::rand() % 20);
    }
}

void showVector(const std::vector<int>& vec) {
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

void mergeSort(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& temp) {
    int i = 0;
    int j = 0;
    int k = 0;
    int alen = a.size();
    int blen = b.size();
    while (i < alen && j < blen)
        temp[k++] = a[i] < b[j] ? a[i++] : b[j++];
    while (i < alen)
        temp[k++] = a[i++];
    while (j < blen)
        temp[k++] = b[j++];
}

int main() {
    std::vector<int> a = {1, 3, 5, 7, 9};
    std::vector<int> b = {2, 8, 10};
    std::vector<int> temp(a.size() + b.size());

    mergeSort(a, b, temp);
    showVector(temp);

    system("pause");
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
归并排序
void mergeSort(const std::vector<int>& a, const std::vector<int>& b, std::vector<int>& temp) {
    int i = 0;
    int j = 0;
    int k = 0;
    int alen = a.size();
    int blen = b.size();
    while (i < alen && j < blen)
        temp[k++] = a[i] < b[j] ? a[i++] : b[j++];
    while (i < alen)
        temp[k++] = a[i++];
    while (j < blen)
        temp[k++] = b[j++];
}

如果给的序列不是有序的序列，需要递归将该序列分成两组，然后两组再分两组，直到分到一个数组中只有一个元素，然后将数组重新组成有序序列的一个数组。

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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

#define MAXSIZE 10

void initArr(std::vector<int>& arr) {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void merge(std::vector<int>& arr, int low, int mid, int high, std::vector<int>& temp) {
    int i = low;
    int j = mid + 1;
    int k = low;
    while (i <= mid && j <= high)
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= high)
        temp[k++] = arr[j++];
    for (i = low; i <= high; i++)
        arr[i] = temp[i];
}

void merge_sort(std::vector<int>& arr, int low, int high, std::vector<int>& temp) {
    if (low >= high)
        return;
    int mid = low + (high - low) / 2;
    merge_sort(arr, low, mid, temp);
    merge_sort(arr, mid + 1, high, temp);
    merge(arr, low, mid, high, temp);
}

void mergeSort(std::vector<int>& arr) {
    std::vector<int> temp(arr.size());
    merge_sort(arr, 0, arr.size() - 1, temp);
}

int main() {
    std::vector<int> arr(MAXSIZE);
    initArr(arr);
    std::cout << "Original Array: ";
    showArr(arr);
    mergeSort(arr);
    std::cout << "Sorted Array: ";
    showArr(arr);

    return 0;
}

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
归并排序
void merge(std::vector<int>& arr, int low, int mid, int high, std::vector<int>& temp) {
    int i = low;
    int j = mid + 1;
    int k = low;
    while (i <= mid && j <= high)
        temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
    while (i <= mid)
        temp[k++] = arr[i++];
    while (j <= high)
        temp[k++] = arr[j++];
    for (i = low; i <= high; i++)
        arr[i] = temp[i];
}

void merge_sort(std::vector<int>& arr, int low, int high, std::vector<int>& temp) {
    if (low >= high)
        return;
    int mid = low + (high - low) / 2;
    merge_sort(arr, low, mid, temp);
    merge_sort(arr, mid + 1, high, temp);
    merge(arr, low, mid, high, temp);
}

void mergeSort(std::vector<int>& arr) {
    std::vector<int> temp(arr.size());
    merge_sort(arr, 0, arr.size() - 1, temp);
}

堆排序

思想

在我们去构建堆结构的时候有外堆和内堆。

  • 外堆：需要一段和原来数组长度大小的内存空间，这段内存空间是用来存储堆结构的。
  • 内堆：不需要重新申请内存，直接原来的数组上进行排序。
    堆结构：
    本质上就是一个完全二叉树。每一个节点的存储都是连续的。
  • 从0开始计数
    左子树->2current+1
    右子树->2    current+2
  • 从1开始计数
    左子树->2current
    右子树->2    current+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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cassert>

#define MAXSIZE 10

void initArr(std::vector<int>& arr) {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

struct Heap
{
    int* root;
    int length;
};

Heap* createHeap(int length)
{
    Heap* heap = new Heap;
    assert(heap != nullptr);
    heap->length = 0;
    heap->root = new int[length];
    assert(heap->root != nullptr);
    return heap;
}

void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

void pushHeap(Heap* heap, int data)
{
    int current = heap->length++;
    int parent = current / 2;
    heap->root[current] = data;
    while (parent != current)
    {
        if (heap->root[current] < heap->root[parent])
        {
            swap(heap->root[current], heap->root[parent]);
            current = parent;
            parent = current / 2;
        }
        else
            break;
    }
}

int popHeap(Heap* heap)
{
    int val = heap->root[0];
    int current = 0;
    int rchild = 2 * current + 2;
    int small;
    int n = --heap->length;
    heap->root[0] = heap->root[heap->length];
    while (rchild <= heap->length)
    {
        small = heap->root[rchild - 1] < heap->root[rchild] ? rchild - 1 : rchild;
        if (heap->root[small] < heap->root[current])
        {
            swap(heap->root[small], heap->root[current]);
            current = small;
            rchild = 2 * current + 2;
        }
        else
            break;
    }
    return val;
}

void heapSort(std::vector<int>& arr)
{
    Heap* heap = createHeap(arr.size());
    for (int i = 0; i < arr.size(); i++)
    {
        pushHeap(heap, arr[i]);
    }

    for (int i = 0; i < arr.size(); i++)
    {
        arr[i] = popHeap(heap);
    }

    delete[] heap->root;
    delete heap;
}

int main() {
    std::vector<int> arr(MAXSIZE);
    initArr(arr);
    std::cout << "原始数组: ";
    showArr(arr);
    heapSort(arr);
    std::cout << "排序后的数组: ";
    showArr(arr);
    return 0;
}

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
77
//堆结构
struct Heap
{
    int* root;
    int length;
};

Heap* createHeap(int length)
{
    Heap* heap = new Heap;
    assert(heap != nullptr);
    heap->length = 0;
    heap->root = new int[length];
    assert(heap->root != nullptr);
    return heap;
}

//入堆
void pushHeap(Heap* heap, int data)
{
    int current = heap->length++;
    int parent = current / 2;
    heap->root[current] = data;
    while (parent != current)
    {
        if (heap->root[current] < heap->root[parent])
        {
            swap(heap->root[current], heap->root[parent]);
            current = parent;
            parent = current / 2;
        }
        else
            break;
    }
}

//出堆
int popHeap(Heap* heap)
{
    int val = heap->root[0];
    int current = 0;
    int rchild = 2 * current + 2;
    int small;
    int n = --heap->length;
    heap->root[0] = heap->root[heap->length];
    while (rchild <= heap->length)
    {
        small = heap->root[rchild - 1] < heap->root[rchild] ? rchild - 1 : rchild;
        if (heap->root[small] < heap->root[current])
        {
            swap(heap->root[small], heap->root[current]);
            current = small;
            rchild = 2 * current + 2;
        }
        else
            break;
    }
    return val;
}

void heapSort(std::vector<int>& arr)
{
    Heap* heap = createHeap(arr.size());
    for (int i = 0; i < arr.size(); i++)
    {
        pushHeap(heap, arr[i]);
    }

    for (int i = 0; i < arr.size(); i++)
    {
        arr[i] = popHeap(heap);
    }

    delete[] heap->root;
    delete heap;
}

内堆实现

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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cassert>

#define MAXSIZE 10

void initArr(std::vector<int>& arr) {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = std::rand() % 20;
    }
}

void showArr(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void swap(std::vector<int>& arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void heapify(std::vector<int>& arr, int length, int current) {
    int rchild = 2 * current + 2;
    int large;
    while (rchild <= length) {
        large = (rchild == length) ? rchild - 1 : (arr[rchild - 1] > arr[rchild] ? rchild - 1 : rchild);
        if (arr[large] > arr[current]) {
            swap(arr, large, current);
            current = large;
            rchild = 2 * current + 2;
        } else
            break;
    }
}

void heapSort(std::vector<int>& arr) {
    int length = arr.size();
    int current = length / 2;
    while (current >= 0) {
        heapify(arr, length, current);
        current--;
    }
    while (length) {
        swap(arr, 0, --length);
        heapify(arr, length, 0);
    }
}

int main() {
    std::vector<int> arr(MAXSIZE);
    initArr(arr);
    std::cout << "原始数组: ";
    showArr(arr);
    heapSort(arr);
    std::cout << "排序后的数组: ";
    showArr(arr);
    return 0;
}

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
void heapify(std::vector<int>& arr, int length, int current) {
    int rchild = 2 * current + 2;
    int large;
    while (rchild <= length) {
        large = (rchild == length) ? rchild - 1 : (arr[rchild - 1] > arr[rchild] ? rchild - 1 : rchild);
        if (arr[large] > arr[current]) {
            swap(arr, large, current);
            current = large;
            rchild = 2 * current + 2;
        } else
            break;
    }
}

void heapSort(std::vector<int>& arr) {
    int length = arr.size();
    int current = length / 2;
    while (current >= 0) {
        heapify(arr, length, current);
        current--;
    }
    while (length) {
        swap(arr, 0, --length);
        heapify(arr, length, 0);
    }
}

计数排序（桶排序）

思想

统计原来数组的数据。并将数据转换成下标存储于一个临时的空间中，然后变量临时空间把对应的下标值放回原数组，当遍历临时空间完成后，原来的数组就是排好序了。

代码

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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cassert>

#define MAXSIZE 10
#define N 100

void initArr(std::vector<int>& arr) {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = std::rand() % 100;
    }
}

void showArr(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

std::vector<int> countSort(std::vector<int>& arr) {
    std::vector<int> temp(N, 0);
    for (int i = 0; i < arr.size(); i++) {
        temp[arr[i]]++;
    }
    std::vector<int> sortedArr;
    for (int i = 0; i < N; i++) {
        while (temp[i]-- > 0) {
            sortedArr.push_back(i);
        }
    }
    return sortedArr;
}

int main() {
    std::vector<int> arr(MAXSIZE);
    initArr(arr);
    std::cout << "原始数组: ";
    showArr(arr);
    std::vector<int> sortedArr = countSort(arr);
    std::cout << "排序后的数组: ";
    showArr(sortedArr);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> countSort(std::vector<int>& arr) {
    std::vector<int> temp(N, 0);
    for (int i = 0; i < arr.size(); i++) {
        temp[arr[i]]++;
    }
    std::vector<int> sortedArr;
    for (int i = 0; i < N; i++) {
        while (temp[i]-- > 0) {
            sortedArr.push_back(i);
        }
    }
    return sortedArr;
}

基数排序

思想

例如：154 423 365 251 78 92 640
第一轮（$10^0$）：640 251 92 423 154 365 78
第二轮（$10^1$）：423 640 251 154 365 78 92
第三轮（$10^2$）：78 92 154 251 365 423 640

代码

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
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <cassert>

#define MAXSIZE 10
#define N 100

void initArr(std::vector<int>& arr) {
    std::srand(static_cast<unsigned int>(std::time(nullptr)));
    for (int i = 0; i < arr.size(); i++) {
        arr[i] = std::rand() % 100;
    }
}

void showArr(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

void redixSort(std::vector<int>& arr, int length) {
    int Temp[10][N] = {0}; // 使用数组而非向量来存储临时结果
    for (int k = 10; k < 10000; k *= 10) {
        for (int i = 0; i < length; i++) {
            int j = 0;
            int pos = (arr[i] % k) / (k / 10);
            while (Temp[pos][j])
                j++;
            Temp[pos][j] = arr[i];
        }
        int pos = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < length && Temp[i][j] != 0; j++) {
                arr[pos++] = Temp[i][j];
                Temp[i][j] = 0;
            }
        }
    }
}

int main() {
    std::vector<int> arr(MAXSIZE);
    initArr(arr);
    std::cout << "原始数组: ";
    showArr(arr);
    redixSort(arr, arr.size());
    std::cout << "排序后的数组: ";
    showArr(arr);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void redixSort(std::vector<int>& arr, int length) {
    int Temp[10][N] = {0}; // 使用数组而非向量来存储临时结果
    for (int k = 10; k < 10000; k *= 10) {
        for (int i = 0; i < length; i++) {
            int j = 0;
            int pos = (arr[i] % k) / (k / 10);
            while (Temp[pos][j])
                j++;
            Temp[pos][j] = arr[i];
        }
        int pos = 0;
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < length && Temp[i][j] != 0; j++) {
                arr[pos++] = Temp[i][j];
                Temp[i][j] = 0;
            }
        }
    }
}

不同的排序算法在不同的场景中有不同的优势和适用性。以下是十大排序算法以及它们适合的场景：

冒泡排序（Bubble Sort）：
适用于小规模的数据排序或者数据基本有序的情况。
算法简单，实现容易。

选择排序（Selection Sort）：
适用于小规模数据排序，相对于冒泡排序，数据交换次数较少。
算法简单，实现容易。

插入排序（Insertion Sort）：
适用于数据规模较小或者数据基本有序的情况。
对于已经部分有序的数据，插入排序具有较好的性能。

希尔排序（Shell Sort）：
适用于中等规模的数据排序，比插入排序和选择排序性能更好。
适用于需要高效率的排序，但又不需要稳定性的场合。

归并排序（Merge Sort）：
适用于大规模数据排序，效率稳定，不受数据分布的影响。
稳定排序算法，适用于对稳定性有要求的场景。

快速排序（Quick Sort）：
适用于大规模数据排序，性能较好。
适用于对排序性能有较高要求的场景，不适合对稳定性有要求的场景。

堆排序（Heap Sort）：
适用于大规模数据排序，性能稳定。
不适用于小规模数据排序，由于其涉及到堆的构建，性能稍逊于快速排序。

计数排序（Counting Sort）：
适用于待排序元素范围较小的场景，且适用于非负整数的排序。
不适用于数据范围过大的情况，因为需要申请相应范围的空间。

桶排序（Bucket Sort）：
适用于数据均匀分布在一个范围内的情况，且数据量较大。
数据均匀分布且范围较小时性能较好。

基数排序（Radix Sort）：
适用于非负整数的排序，且适用于数据范围较大的情况。
对于非负整数，且每个数的位数相同的场景，基数排序性能较好。