Github仓库

冒泡排序(Bubble)

思想

代码实现

快速排序(Quick)

思想

快速排序引入的pivot的概念,每次遍历序列时,从这个序列中选一个数(一般可以选择序列中的第一个数),遍历完一遍序列之后能够找到被选中数在这个序列中的位置,将该位置标记为pivot,交换pivot左侧大于pivotValue的数和右侧小于pivotValue的数,最终交换index为pivot和被选中数所在index位置,接着以该pivot为界将序列拆分成两个子序列,重复上面的操作,直到序列的长度为1.

时间复杂度

快速排序不是一个稳定的算法,原因是pivot的取值会导致pivot两侧序列长度不是相等的,最坏的情况是,pivot每次取值取得都是数组中最大的那个值,这样他的分治递归层数就是n,在每一层中都需要遍历完所数组中所有的元素,因此每一层中的时间复杂度是n,所以最坏情况下快速排序的时间复杂度是O(n^2).

平均情况下,快速排序的分治递归层数为logn,时间复杂度是O(nlogn).

注意

分区结束时：
left 指向第一个大于或等于 pivotValue 的元素。
right 指向最后一个小于 pivotValue 的元素。
因此pivot要和right交换.

代码实现

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

void Swap(int *arr, int x, int y)
{
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

void InnerQuickSort(int *arr, int beginIndex, int endIndex)
{
    if (beginIndex >= endIndex)
    {
        return;
    }

    int left = beginIndex + 1;
    int right = endIndex;
    int pivotValue = arr[beginIndex]; // 选择起始位置的元素作为枢轴

    while (left <= right)
    {
        // 找到左侧第一个大于等于 pivot 的元素
        while (left <= right && arr[left] < pivotValue)
        {
            left++;
        }

        // 找到右侧第一个小于 pivot 的元素
        while (left <= right && arr[right] >= pivotValue)
        {
            right--;
        }

        // 如果左指针和右指针没有交错，交换它们
        if (left < right)
        {
            Swap(arr, left, right);
        }
    }

    // 将枢轴放到正确的位置
    Swap(arr, beginIndex, right);

    // 递归地对左右子数组排序
    InnerQuickSort(arr, beginIndex, right - 1);
    InnerQuickSort(arr, right + 1, endIndex);
}

void QuickSort(int *arr, int size)
{
    // 选择pivot
    // 能够标记两个子序列
    InnerQuickSort(arr, 0, size - 1);
}

int main()
{
    int arr[10] = {26, 99, 10, 77, 55, 89, 44, 32, 17, 18};

    QuickSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

插入排序(Insert)

思想

插入排序认为一个数组会被分成已排序部分和未排序部分,已排序部分长度默认是1.每次遍历的时候都从未排序数组中拿取第一个元素,插入到已经排序数组中.重复该步骤直到未排序部分长度为0.

时间复杂度

外层是n
内层是T(n)=(n−1)+(n−2)+(n−3)+⋯+1= $\frac{n(n−1)}{2}$

所以时间复杂度O($n^{2}$)

代码实现

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 InsertionSort(int *arr, int size)
{
    for (int i = 1; i < size; i++)
    {
        int preIndex = i - 1;
        int current = arr[i];
        // 从
        while (preIndex >= 0 && arr[preIndex] > current)
        {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
}

int main()
{
    int arr[10] = {26, 99, 10, 77, 55, 89, 44, 32, 17, 18};
    InsertionSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

选择排序(Selection)

思想

选择排序认为一个数组会被分成已排序部分和未排序部分,遍历整个数组,每次遍历的时候从未排序部分里面遍历出最小的值,将其与未排序部分的第一个元素交换,将未排序部分的第一个元素添加到已排序部分的末尾,重复该操作直到未排序部分长度为0

时间复杂度

外层是n
内层是T(n)=(n−1)+(n−2)+(n−3)+⋯+1= $\frac{n(n−1)}{2}$

所以时间复杂度O($n^{2}$)

代码实现

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

// 遍历整个数组,每次遍历的时候从未排序的数组里面遍历出最小的值,将其与未排序部分的第一个元素交换,重复该操作直到未排序数组长度为0

void Swap(int *arr, int x, int y)
{
    int temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
}

void SelectionSort(int *arr, int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        int tempMinIndex = i;
        for (int j = i + 1; j < size; j++)
        {
            // 找到最小的
            if (arr[tempMinIndex] > arr[j])
            {
                tempMinIndex = j;
            }
        }
        Swap(arr, tempMinIndex, i);
    }
}

int main()
{
    int arr[10] = {26, 99, 10, 77, 55, 89, 44, 32, 17, 18};
    SelectionSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

归并排序(Merge)

思想

归并排序采用分治的思想,先让局部有序,然后将多个有序的局部排序成一个更大的有序局部.

实现思路

  1. 传入一个数组,数组长度为size
  2. 分治,将数组分成size个长度为1的子数组,这些数组默认是有序的.
  3. 合并,将这size个长度为1的子数组合并成$\frac{size}{2}$个长度为2的子数组.注意,如果size为奇数,就要分成$\frac{size - 1}{2}$个长度为2的子数组和一个长度为1的子数组
  4. 重复第2、3步操作,直到子数组的长度变为size.

时间复杂度

外层循环时间复杂度是log(n),内层循环复杂度n,总复杂度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
#include <iostream>
#include <vector>
using namespace std;

// 1. 传入一个数组, 数组长度为size
// 2. 分治, 将数组分成size个长度为1的子数组, 这些数组默认是有序的.
// 3. 合并, 将这size个长度为1的子数组合并成$\frac{size} {2} $个长度为2的子数组.注意, 如果size为奇数, 就要分成$\frac{size - 1} {2} $个长度为2的子数组和一个长度为1的子数组
// 4. 重复第2、3步操作, 直到子数组的长度变为`size`.

void MergeSort(int *arr, int size);
void Merge(int *arr, int size, int begin, int mid, int end);

void MergeSort(int *arr, int size)
{
    for (int curSize = 1; curSize < size; curSize *= 2)
    {
        // 此处对边界值的判定
        for (int index = 0; index < size - curSize; index += 2 * curSize)
        {
            Merge(arr, size, index, index + curSize, index + 2 * curSize - 1 > size - 1 ? size - 1 : index + 2 * curSize - 1);
        }
    }
}

void Merge(int *arr, int size, int begin, int mid, int end)
{
    int *temp = new int[size];
    for (int i = 0; i < size; i++)
    {
        temp[i] = arr[i];
    }

    int index = begin;
    int left = begin;
    int right = mid;

    while (left <= mid - 1 && right <= end)
    {
        // 左边大于右边
        if (temp[left] > temp[right])
        {
            arr[index++] = temp[right++];
        }
        else // 右边大于左边
        {
            arr[index++] = temp[left++];
        }
    }

    while (left <= mid - 1)
        arr[index++] = temp[left++];
    while (right <= end)
        arr[index++] = temp[right++];

    delete[] temp;
}

int main()
{
    int arr[10] = {26, 99, 10, 77, 55, 89, 44, 32, 17, 18};
    MergeSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

经过ChatGPT优化过的代码

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
#include <iostream>
#include <algorithm> // 为了使用 std::min
using namespace std;

void MergeSort(int *arr, int size);
void Merge(int *arr, int begin, int mid, int end);

void MergeSort(int *arr, int size)
{
    for (int curSize = 1; curSize < size; curSize *= 2)
    {
        for (int index = 0; index < size; index += 2 * curSize)
        {
            int mid = index + curSize; // 中间位置
            int end = std::min(index + 2 * curSize - 1, size - 1); // 右边界
            if (mid < size) // 确保中间位置在数组范围内
            {
                Merge(arr, index, mid, end);
            }
        }
    }
}

void Merge(int *arr, int begin, int mid, int end)
{
    int *temp = new int[end - begin + 1];
    for (int i = begin; i <= end; i++)
    {
        temp[i - begin] = arr[i];
    }

    int index = begin;
    int left = 0; // temp 的左半部分起始位置
    int right = mid - begin; // temp 的右半部分起始位置

    while (left < mid - begin && right < end - begin + 1)
    {
        if (temp[left] > temp[right])
        {
            arr[index++] = temp[right++];
        }
        else
        {
            arr[index++] = temp[left++];
        }
    }

    while (left < mid - begin)
        arr[index++] = temp[left++];
    while (right < end - begin + 1)
        arr[index++] = temp[right++];

    delete[] temp;
}

int main()
{
    int arr[10] = {26, 99, 10, 77, 55, 89, 44, 32, 17, 18};
    MergeSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

希尔排序

思想

代码实现

基数排序

思想

代码实现

计数排序

思想

代码实现

桶排序

思想

代码实现

堆排序

思想

代码实现