Algorithm

排序算法

桶排序，冒泡排序，快速排序

Posted by LuminousHao on 2023-10-05
Estimated Reading Time 5 Minutes
Words 1.4k In Total
Viewed Times

一、桶排序(bucketSort)

原理

1.确定桶的数量：首先确定桶的数量，可以根据输入数据的范围和分布情况来选择。桶的数量越多，排序越精确，但也更消耗内存。

2.将元素分配到桶中：遍历待排序的元素，根据元素的值将其分配到对应的桶中。这个过程可以通过简单的映射函数实现。

3.对每个桶中的元素进行排序：对每个非空的桶中的元素进行排序。可以使用任何一种排序算法，通常选择快速排序或者插入排序。

4.合并桶中的元素：按照桶的顺序，将所有桶中的元素依次合并起来，得到最终的有序序列。

示例

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

int main() {
    int a[100], i, j, t;
    cout << "请输入数字个数：";
    cin >> t;
    // 初始化数组,生成桶
    for (i = 0; i < 100; i++) {
        a[i] = 0;
    }
    // 输入数字并统计频次，将元素存入桶中
    cout << "请输入数字：";
    for (i = 0; i < t; i++) {
        cin >> t;
        a[t]++;
    }
    // 输出排序后的数组，在桶中查找元素并输出
    cout << "排序后的数组：";
    for (i = 0; i < 100; i++) {
        for (j = 1; a[i] >= j; j++) {
            cout << i << " ";
        }
    }
    // 暂停以查看结果
    system("pause");

    return 0;
}

二、冒泡排序(bubbleSort)

原理

  1. 从第一个元素开始，依次比较相邻的两个元素，如果左边的元素大于右边的元素，则交换它们的位置。

  2. 继续遍历序列，执行相同的比较和交换操作，直到最大的元素被交换到最右侧。

  3. 在第一轮遍历完成后，最右侧的元素已经是最大的，接下来进行第二轮遍历，但这次不包括最后一个元素。

  4. 重复上述操作，直到所有元素都有序。

示例

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
#include <iostream>
using namespace std;
int main() {
    // 输入数组大小
    int size, t, tmp;
    cout << "输入数组大小: ";
    cin >> size;
    // 动态分配数组
    int* array = new int[size];
    // 初始化数组元素（此处为示例，你可以根据需要进行初始化）
    for (int i = 0; i < size; ++i) {
        array[i] = 0;  // 这里使用了一个简单的初始化方式，你可以根据需要修改
    }
    // 输入数组元素
    cout << "输入数组元素: ";
    for (int i = 0; i < size; i++) {
        cin >> t;
        array[i] = t;
    }
    // 冒泡排序,注意只需要排列size-1个数字
    for (int i = 0; i < size - 1; i++) {
    // 减去已经排列的数字
        for (int j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // 从小到大排序,始终将更小的元素放到序列左边
                tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
    // 输出排序后的数组
    cout << "排序后的数组: ";
    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    // 释放动态分配的数组内存
    delete[] array;

    system("pause");
    return 0;
}

三、快速排序(quickSort)

原理

  1. 选择一个基准元素（通常是数组的第一个元素）。
  2. 将数组分成两个子数组，小于基准元素的放在左边，大于基准元素的放在右边。
  3. 对左右子数组分别递归应用快速排序。
  4. 重复以上步骤，直到每个子数组只有一个元素或为空。

示例

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

int a[101], n;
// 快速排序函数
void quicksort(int left, int right) {
    // 如果左边索引小于右边索引，说明还可以继续划分
    if (left < right) {
        // 定义左右指针和基准值
        int i = left, j = right, pivot = a[left];
        // 开始划分
        while (i < j) {
            // 注意方向为:从右往左找第一个小于基准值的元素
            while (i < j && a[j] >= pivot) {
                j--;
            }
            if (i < j) {
                // 将小于基准值的元素放到左边
                a[i++] = a[j];
            }
            // 从左往右找第一个大于基准值的元素
            while (i < j && a[i] <= pivot) {
                i++;
            }
            if (i < j) {
                // 将大于基准值的元素放到右边
                a[j--] = a[i];
            }
        }
        // 将基准值放到正确的位置
        a[i] = pivot;
        // 对基准值左右两侧的子数组进行递归排序
        quicksort(left, i - 1);
        quicksort(i + 1, right);
    }
}
int main() {
    // 输入数组大小
    cin >> n;
    // 输入数组元素
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    // 调用快速排序函数
    quicksort(0, n - 1);
    // 输出排序后的数组
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }

    system("pause");
    return 0;
}

四、总结

算法的核心思想是我们需要牢记的，但除此之外的一些细节对算法的正确实现却相当重要例如:

数组是否越界，数组下标是否从0开始检查

1
2
3
4
5
int n= 10;
for(int i = 0; i < 10; i++){} //刚好循环10次
for(int i = 1; i < 10; i++){} //循环9次
for(int i = 0; i <= 10; i++){} //循环11次
for(int i = 1; i<=10; i++){} //循环10次

运行完成后是否及时释放栈空间

1
2
int* array = new int[size];
delete[] array;

涉及递归的函数

1
2
3
4
5
void quicksort(int left, int right) {
...
quicksort(left, i - 1);
quicksort(i + 1, right);
}

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。 也欢迎您共享此博客，以便更多人可以参与。 如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。 谢谢 ！

特色标签
Algorithm
实用工具
ESC