排序算法 | 青石板街 回眸一笑你婉约
Cobb 609 1

冒泡排序

排序算法 | 青石板街 回眸一笑你婉约

/*
* 函数功能: 冒泡排序
* 实现思路: 处理总趟数和每趟处理的元素,元素交换即可
* 时间复杂度:平均:O(n2), 最差:O(n2), 最优O(n)
* 空间复杂度:O(1)
* 稳定性:稳定
* 缺点: 交换次数多,效率低
* 优化: 加标志位,如果一组数据中没有产生交换,就退出。
*/
void BubbleSort(int arr[], int size)
{
    // 要处理的趟数,不处理最后一个
    for (int i = 0; i < size - 1; i++)
    {
        // 优化
        bool flag = false;

        // 每趟要处理的元素个数
        for (int j = 0; j < size - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        if (!flag)
        {
            return;
        }
    }
}

选择排序


/*
* 函数功能: 选择排序
* 实现思路: 全局遍历=>(设定第一个元素是最小值,遍历后面 找比设定值还小的值,进行交换)
* 时间复杂度:平均:O(n2), 最差:O(n2), 最好O(n2)
* 空间复杂度:O(1)
* 稳定性:不稳定
* 缺点:
* 优化: 过程中,如果设定的是最小值,加上条件限定,省去交换步骤
*/
void ChoiceSort(int arr[], int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        // 记录下设定的最小值和最小值下标
        int k = i;

        // 找到比设定值还小的值
        for (int j = i + 1; j < size; j++)
        {
            if (arr[k]  > arr[j])
            {
                k = j;
            }
        }

        // 优化:刚开始的min如果是最小值,就不用交换了,减少操作步骤,
        if (k != i)
        {
            int temp = arr[k];
            arr[k] = arr[i];
            arr[i] = temp;
        }

    }
}


插入排序


/*
* 函数功能: 插入排序
* 实现思路: 记录一个元素的值val = arr[i],通过数组i前面的数据对比,通过移位,完成排序。
* 时间复杂度:平均:O(n2), 最差:O(n2), 最好O(n)
* 空间复杂度:O(1)
* 稳定性:稳定
* 特点:在数据趋近有序的情况下, 插入排序效率最高
* 优化:
*/
void InsertSort(int arr[], int size)
{
     // 默认第一个是排序好的,从第2个数开始
    for (int i = 1; i < size; i++)  // O(n)
    {
        // 记录下第二个元素的值,从第二个比较开始
        int val = arr[i];

        // 找到val的合适位置
        int j = i - 1;
        for (; j >= 0; j--)  // O(n)
        {
            // 错误用法: arr[j] < arr[i] , arr[i] 这个值被覆盖掉了
            if (val >= arr[j]) // 保持稳定性
            {
                break;
            }
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = val;
    }
}

希尔(Shell)排序

排序算法 | 青石板街 回眸一笑你婉约


/*
* 函数功能: 希尔(Shell)排序
* 实现思路: 先实现插入排序,外加循环改间隙gap,每次都除以2
* 时间复杂度:平均(选择合适的gap):O(n1.3), 最差:O(n2), 最好O(n)
* 空间复杂度:O(1)
* 稳定性:不稳定(因为相同元素分到了不同的组)
* 特点:适用数量较大的排序操作。
* 优化:希尔排序到趋于有序的时候,用插入操作效率更高
*/
void ShellSort(int arr[], int size)
{
    // 每次 /2 ,进行分组,间隔每次都缩小一半
    for (int gap = size / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < size; i++)
        {
            int val = arr[i];

            int j = i - gap;
            for (; j >= 0; j -= gap)
            {
                if (val > arr[j])
                    break;
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = val;
        }

    }

}



快排 / 快排分割


/*
* 函数功能: 快排分割
* 实现思路: 找个基准数(L),从右往左比,移动R, 从左往右比,移动L.
*             右边找小的往左移,左边找大的往右移
* 分析: 一次分割时间复杂度是O(n),后面继续分割的次数为二叉树的层数,因此,平均时间复杂度为O(nlog2^n)
*        空间复杂度为O(log2^n),递归会开辟额外的栈空间,开辟的空间个数为二叉树层数
* 时间复杂度:平均:O(nlogn),  最好O(nlogn),   最差:O(n2) =》 最差情况下是一叉数,层高n,个数为n, 例:12345678,只处理右边,左边没元素可处理,所以快排需要优化
* 空间复杂度:O(log2n) =》 主要是递归,函数调用栈开销
* 稳定性: 不稳定 =》 和基准值比较,比较完之后都发生了交换。
* 特点:数据越混乱,排序效率越高,数据越有序,排序效率越低。所以,快速排序越执行越慢
* 
*       插入排序数据越有序,效率越高(希尔排序是让数据先趋于有序,再进行插入排序)
* 优化1:越排越有序,有序的情况下采取插入排序效率最高,所以可以规定一个小的范围采用insertsort
*       例: if (j - i < 50){InsertSort(); return;}
* 优化2:基数选取,三数取中法  =》 三个数中选中间大小的arr[i],当做首次取的基准值val。
*        也可将数字扩展到更大(例如5数取中,7数取中等)。
         这种方式能很好的解决待排数组基本有序的情况,而且选取的基准没有随机性。
*/
int partation(int arr[], int L, int R)
{
    // 选基准数
    int val = arr[L];

    while (L < R)
    {
        // 从右往左和 val 对比,移动R,直到找到比基准数小的,放到下标为L的位置
        while ((L < R) && (val <= arr[R]))
        {
            R--;
        }
        if (L < R)
        {
            // R对应的值给L对应, L前进一步
            arr[L] = arr[R];
            L++;
        }


        // 从左往右遍历,直到找到比val 大的数字,放到R指向的位置
        while ((L < R) && (val > arr[L]))
        {
            L++;
        }
        if (L < R)
        {
            // L对应的值给R对应, R后退一步
            arr[R] = arr[L];
            R--;
        }
    }

    // 直到L=R, 把基准数放到L/R所指向的位置, 返回val的下标(下一次的分割线)
    arr[L] = val;
    return L;

}


/*
*函数功能: 快速排序的实现
*实现思路: 通过递归,区域划分,实现快速排序。
*/
void QuickSort2(int arr[], int i, int j)
{
    // 递归进行区域划分
    if (i < j)
    {
        int m = partation(arr, i, j);
        QuickSort2(arr, i, m - 1);
        QuickSort2(arr, m + 1, j);
    }
}

/*
* 函数功能: 快速排序
* 内部: 封装可进行快速分割的接口
*/
void QuickSort(int arr[], int size)
{
    QuickSort2(arr, 0, size - 1);
}

归并排序

/*

  • 函数功能: 归并排序
  • 实现思路: 先划分范围直到一个数字一个范围 =》每次除以2(拆解),分割,写二叉树,然后再排序合并
  • 时间复杂度:平均:O(nlogn), 最差:O(nlogn), 最好O(nlogn)
  • 空间复杂度:O(nlogn) =》合并两个有序段的时候,开辟了额外空间
  • 稳定性:稳定 =》 两个有序小段合并,相等的话就优先放前面的。
  • 问题: 如何把10G大小的文件src.txt在1G的内存里排序?
  • 分析:
  • 每次加载1G来排序,排好序后分别输出到对应的10个小文件中,
  • 然后从10个小文件的第一个数据开始
  • 采用外排序和归并思想(小段有序变成大段有序)逐个排序,输出到src.txt中。
  • /
// 合并两个有序的数据段 [l,m] [m+1,r]
void Merge(int arr[], int l, int m, int r)
{
    int* p = new int[r - l + 1];  // 空间复杂度 O(n)
    int idx = 0;
    int i = l;
    int j = m + 1;
    // 合并两小段
    while (i <= m && j <= r)
    {
        if (arr[i] < arr[j])
        {
            p[idx++] = arr[i++];
        }
        else
        {
            p[idx++] = arr[j++];
        }
    }

    // 两小段中,哪个有剩余就放到p数组中
    while (i <= m)
    {
        p[idx++] = arr[i++];
    }

    while (j <= r)
    {
        p[idx++] = arr[j++];
    }

    // 拷贝到原数组
    for (i = l, j = 0; i <= r; i++, j++)
    {
        arr[i] = p[j];
    }

    delete[]p;
}
// 归并排序 O(n*logn)  空间复杂度O(n*logn)    稳定的
void MergeSort(int arr[], int start, int end)
{
    if (start >= end)
        return;

    int mid = (start + end) / 2;
    // 先归类
    MergeSort(arr, start, mid);
    MergeSort(arr, mid+1, end);
    // 再合并   [start,mid] [mid+1,end]
    Merge(arr, start, mid, end);
}
int main()
{
    int arr[10] = { 86,7,23,68,73,24,61,80,6,64 };
    srand(time(0));
    for (int i = 0; i < 10; i++)
    {
        arr[i] = rand() % 100;
    }

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

    MergeSort(arr, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

堆排序

/*

  • 函数功能: 堆排序
  • 实现思路:小根堆,大根堆,下沉上浮找最小或最大放到根节点。
          堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:
          即子结点的键值或索引总是小于(或者大于)它的父节点。
  • 时间复杂度:平均:O(nlog2n), 最差:O(nlog2n), 最好O(nlog2n)
  • 空间复杂度:O(1)
  • 稳定性: 不稳定 =》因为一次只操作一个分支,相同的两个数可能分到不同的分支里,从而打乱顺序。 在不需要全部排序的情况下得到最大或者最小的部分数据,使用堆排序最快
  • /

排序算法 | 青石板街 回眸一笑你婉约

// 下沉函数
void SiftDown(int arr[], int i, int size)
{
    int val = arr[i];
    while (i < (size / 2))
    {
        // 左孩子
        int child = 2 * i + 1;
        // 右孩子判断存在,且右孩子 > 左孩子, 给child替换为右孩子,下文只需要比较child就行
        if ((child + 1) < size && arr[child + 1] > arr[child])
        {
            child += 1;
        }

        // 和孩子进行比较,孩子比父亲大,进行替换
        if (val < arr[child])
        {
            arr[i] = arr[child];
            i = child;
        }
        else
        {
            break;
        }
    }
    arr[i] = val;
}

// 堆排序,调整n个,一个的时间是logn, O(n*logn)
// 不稳定 , 例:父5,左子5,右子8
void HeapSort(int arr[], int size)
{
    // 调整成大根堆结构
    // 从第一个非叶子节点开始
    for (int i = (size - 1) / 2; i >= 0; i--)
    {
        SiftDown(arr, i, size);
    }


    for (int i = size - 1; i > 0; i--) 
    {
        // 交换堆顶元素和最后元素
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;

        // 从根节点开始,继续调整堆。调整size - 1次
        SiftDown(arr, 0, i);
    }
}

测试代码


int main1()
{  
    long start, end;
    int idx;
    srand(time(0));
    int* arr = (int*)malloc(1000000 * sizeof(int));
    int* brr = (int*)malloc(1000000 * sizeof(int));
    int* crr = (int*)malloc(1000000 * sizeof(int));
    int* drr = (int*)malloc(1000000 * sizeof(int));
    int* err = (int*)malloc(1000000 * sizeof(int));

    for (int i = 0; i < 1000000; i++)
    {
        arr[i] = rand();
        brr[i] = rand();
        crr[i] = rand();
        drr[i] = rand();
        err[i] = rand();

    }

    //start = clock();
    //BubbleSort(arr, 100000);
    //end = clock();
    //printf("BubbleSort time:%dms\n", end - start);

    //start = clock();
    //ChoiceSort(brr, 100000);
    //end = clock();
    //printf("ChoiceSort time:%dms\n", end - start);

    //start = clock();
    //InsertSort(crr, 100000);
    //end = clock();
    //printf("InsertSort time:%dms\n", end - start);

    start = clock();
    InsertSort1(drr, 1000000);
    end = clock();
    printf("希尔InsertSort1 time:%dms\n", end - start);

    start = clock();
    QuickSort(err, 1000000);
    end = clock();
    printf("QuickSort time:%dms\n", end - start);

    return 0;

}

评论区

索引目录