【算法导论笔记】插入排序 && 归并排序-蒲公英云

【算法导论笔记】插入排序 && 归并排序

小灰灰 2022-05-08 10:06 295阅读 0赞

插入排序时间复杂度 O(n^2)

#include "pch.h"
#include <iostream>
void insectionSort();
int origin[] = { 12, 15, 3, 2, 31, 34, 18, 9, 99, 121, 56 };
int main()
{
    insectionSort();
    for (int i = 0; i < sizeof(origin) / sizeof(origin[0]); i++)
    {
        std::cout << origin[i] << std::endl;
    }
}
void insectionSort()
{
    for (int i = 1; i < sizeof(origin) / sizeof(origin[0]); i++)
    {
        // 标记第 i 个做插入排序的元素，0 - i-1 已经是有序序列 
        int temp = origin[i];
        // 从 i-1 开始和前面排序序列比较，看在哪里插入
        int j = i - 1;
        for (; j >= 0 && origin[j] > temp; j--)
        {
            origin[j + 1] = origin[j];
        }
        // 最终的 j 标识插入的前一个位置
        origin[j + 1] = temp;
    }
}

归并排序时间复杂度 O(nlogn)

#include "pch.h"
#include <iostream>
void mergeSort(int * A, int number);
void merge(int * A, int * L, int lIndex, int * R, int rIndex);
int main()
{
    int sequence[] = { 12, 15, 3, 2, 31, 34, 18, 9, 99, 121, 56 };
    int sizeOfElements = sizeof(sequence) / sizeof(sequence[0]);
    mergeSort(sequence, sizeOfElements);
    for (int i = 0; i < sizeOfElements; i++)
    {
        std::cout << sequence[i] << std::endl;
    }
}
/* 归并排序主代码 */
void mergeSort(int * A, int size)
{
    if (size < 2) return;
    int mid = size / 2;
    int *L, *R;
    L = new int[mid];
    R = new int[size - mid];
    for (int i = 0; i < mid; i++) L[i] = A[i];
    for (int i = mid; i < size; i++) R[i - mid] = A[i];
    mergeSort(L, mid);
    mergeSort(R, size - mid);
    merge(A, L, mid, R, size - mid);
    delete[] L;
    delete[] R;
}
/* 合并两个已排序的数组，最终返回给 A */
void merge(int * A, int * L, int lSize, int * R, int rSize)
{
    int lIndex = 0, rIndex = 0;
    for (int i = 0; i < lSize + rSize; i++)
    {
        if (lIndex >= lSize)
        {
            A[i] = R[rIndex++];
            continue;
        }
        if (rIndex >= rSize)
        {
            A[i] = L[lIndex++];
            continue;
        }
        if (L[lIndex] < R[rIndex]) 
        {
            A[i] = L[lIndex++];
        }
        else if (L[lIndex] == R[rIndex])
        {
            A[i] = L[lIndex++];
        }
        else if (L[lIndex] > R[rIndex])
        {
            A[i] = R[rIndex++];
        }
    }
}