首页 > 编程语言 >43. 排序算法

43. 排序算法

时间：2023-07-09 20:11:07浏览次数：39  
标签：temp int 43 param 算法 数组 排序 left

一、什么是排序

  排序 也称 排序算法，排序 是将一组数组，依指定的顺序进行排列的过程。排序 分为 内部排序 和 外部排序 两种。内部排序 是指将需要处理的所有数据都加载到内部存储器中进行排序。外部排序 是指数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。

img

二、冒泡排序

  冒泡排序（Bubble Sorting）的 基本思想 是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序对则交换，使值较大的元素逐渐从前一项后部，就像水底的气泡一样逐渐向上冒。一共进行 数组大小-1 次排序，每一趟排序的次数在逐渐的减少。

  因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下去没有进行过交换，则说明序列有序，因此要在排序的过程中设置一个标志 flag 判断元素是否进行过交换，从而减少不必要的比较。

/**
 * @brief 冒泡排序
 * 
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void BulletSort(int A[],int N)
{
    int i = 0, j = 0;
    int temp = 0;
    int flag = 0;                               // 标识变量，表示是否进行交换

  
    for(i = 0; i < N-1; i++)                    // 进行N-1趟排序
    {
        for(j = 0; j < N-1-i; j++)
        {

            if (A[j] > A[j + 1])                // 如果前面的数比后面的数大，则交换
            {
                flag = 1;
                temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
            }
        }

        if(!flag)                               // 在一趟排序中，一次交换都没有发生过
        {
            break;
        }
        else                                    // 重置flag，进行下次判断
        {
            flag = 0;
        }
    }
}

三、选择排序

  选择排序（Select Sorting）也属于内部排序，是从待排序的数据中，按指定的规则选出某一个元素，再依照规定交换位置后达到排序的目的。

  选择排序 也是一种简单的排序方法。它的 基本思想 是：第一次从 array[0]~array[n-1] 中选取最小值，与 array[0] 交换，第二次从 array[1]~array[n-1] 中选取最小值，与 array[1] 交换，……，第 i 次从 array[i-1]~array[n-1] 中选取最小值，与 array[i-1] 交换，……，第 n-1 次从 array[n-2]~array[n-1] 中选取最小值，与 array[n-2] 交换，总共通过 n-1 次，得到一个按排序码从小到大排列的有序序列。

  选择排序 一共有 数组大小-1 轮循环，每一轮循环，又是一个循环，循环的规则如下：先假定当前这个数是最小数，然后和后面的每个数进行比较，如果发现有比当前树更小的树，就重新确定最小数，并得到下标。当遍历到数组的最后时，就得到本轮的最小数和下标，然后就交换。

/**
 * @brief 选择排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void SelectSort(int A[],int N)
{
    int i = 0, j = 0;
    int minIndex = 0;
    int min = 0;

    for (i = 0; i < N - 1; i++)                 // 进行N-1趟排序
    {
        minIndex = i;
        min = A[i];
        for (j = i + 1; j < N; j++)
        {
            if (min > A[j])                     // 说明假定的最小值，并不是最小的
            {
                min = A[j];                     // 重置min
                minIndex = j;                   // 重置minIndex
            }
        }

        if (minIndex != i)                      // 将最小值进行交换
        {
            A[minIndex] = A[i];
            A[i] = min;
        }
    }
}

四、插入排序

  插入排序 属于内部排序，是对待排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

  插入排序（Insertion Sorting）的 基本思想 是：把 n 个待排序的元素看成为一个有序表和无序表，开始时有序表中只包含一个元素，无序表中包含 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表的排序吗进行比较，将它插入到有序表中适当位置，使之成为新的有序表。

/**
 * @brief 插入排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void InsertSort(int A[],int N)
{
    int i = 0, j = 0;
    int insertVal = 0;                          // 定义待插入的数
    int insertIndex = 0;                        // 定义待插入数的的前面这个数的下标

    for (i = 1; i < N; i++)                     // 进行N-1趟排序
    {
        insertVal = A[i];                       // 定义待插入的数
        insertIndex = i - 1;                    // 待插入数的的前面这个数的下标
        // 给 insertVal 找到插入的位置
        // insertIndex >= 0 保证在给 insertVal 找到插入位置，不越界
        // insertVal < A[insertIndex] 待插入的数，还没有找到插入位置
        // 就需要将 A[insertIndex] 后移
        while(insertIndex >= 0 && insertVal < A[insertIndex])
        {
            A[insertIndex + 1] = A[insertIndex];
            insertIndex--;
        }

        // 当退出while循环时，说明插入的位置找到，indexIndex + 1
        if(insertIndex + 1 != i)                // 判断是否需要赋值
        {
            A[insertIndex + 1] = insertVal;
        }
    }
}

当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响；

五、希尔排序

  希尔排序 是 希尔（Donald Shell）于 1959 年提出的一种排序算法。希尔排序 也是一种 插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称 缩小增量排序。

  希尔排序 的 基本思想 是：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的不断减少，每组包含的关键词越来越多，当增量减少至 1 时，整个文件恰好被分成一组，算法边终止。

  定义增量序列 \(D_{M} > D_{M-1} > ... > D_{1} = 1\)，对每个 \(D_{K}\) 进行 “\(D_{K} - 间隔\)” 排序（k = M,M-1,...1）。“\(D_{K} - 间隔\)”有序的序列，在执行“\(D_{K-1}间隔\)”排序后，仍然是“\(D_{K} - 间隔\)”有序的；

image

/**
 * @brief 希尔排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void ShellSort(int A[],int N)
{
    int gap = 0;
    int temp = 0;
    int i = 0, j = 0;

    for (gap = N / 2; gap > 0; gap /= 2)                    // 每次循环的增量，并逐渐缩小增量
    {
        for(i = gap; i < N; i++)                            // 从第gap个元素，逐个对其所在的组进行直接插入排序
        {
            j = i;                                          // 待插入元素的下标
            temp = A[j];                                    // 待插入的元素
            if(A[j] < A[j - gap])
            {
                while(j - gap >= 0 && temp < A[j-gap])      // 还没有找到位置
                {
                    A[j] = A[j - gap];                      // 元素依次后移
                    j -= gap;                               // 下标向前移动
                }

                // 当退出while循环后，就给temp找到了插入的位置
                A[j] = temp;
            }
        }
    }
}

六、快速排序

  快速排序（Quick Sort）是对 冒泡排序 的一种改进。其 基本思想 是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

img

/**
 * @brief 快速排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void QuickSort(int A[],int N)
{
    Quick(A,0,N-1);
}

  这里采用的是中间的值作为基准，代码实现起来比较复杂。

/**
 * @brief 快速排序的核心算法
 * 
 * @param A 待排序的数组
 * @param left 递归的左边的索引
 * @param right 递归的右边的索引
 */
void Quick(int A[],int left,int right)
{
    int l = left;                               // 左下标
    int r = right;                              // 右边的下标
    int pivot = A[(right - left) / 2 + left];   // 中轴值
    int temp = 0;

    // while循环的目的是让比pivot值小的放到左边，比pivot大的放在右边
    while(l < r)
    {
        // 从左边开始找，找到大于等于pivot值，才退出
        while(A[l] < pivot)
        {
            l++;
        }
        // 从右边开始找，找到小于等于pivot值，才退出
        while(A[r] > pivot)
        {
            r--;
        }

        // 如果 l >= r 成立，说明 pivot 的左右两边的值，
        // 已经按照左边全部是小于等于 pivot 值，右边全部是大于等于 pivot 的值
        if(l >= r)
        {
            break;
        }

        // 如果程序执行到这步，说明 A[l] >= pivot 并且 A[r] <= pivot，则交换
        temp = A[l];
        A[l] = A[r];
        A[r] = temp;

        // 如果交换完后，发现这个 A[l] == pivot，则 r-- 前移
        // 如果交换后 A[l] == pivot == A[r]，此时左右索引都不移动，
        // 则下次循环是还是这两个值进行交换，会陷入死循环中
        // 如果交换后 A[l] == pivot，A[r] > pivot，此时左右索引都不移动
        // 下次循环会正常运行，会进入 while(A[r] > pivot) 循环，r--
        // 综合比较下来，我们采用右索引前移的方式 r--
        // 这种方式也会让等于 pivot 的值向 pivot 靠近
        if(A[l] == pivot)
        {
            r--;
        }

        // 原理如上
        if(A[r] == pivot)
        {
            l++;
        }
    }

    // 程序执行到此处，l >= r
    // 如果 l==r，必须 l++,r--，否则会栈溢出
    if(l == r)
    {
        l++;
        r--;
    }

    // 向左递归
    if(left < r)
    {
        Quick(A,left,r);
    }

    // 向右递归
    if(right > l)
    {
        Quick(A,l,right);
    }
}

  为了简化代码，我们可以采用第一个值或最后一个值作为基准，下面的代码采用第一个值作为基准。

/**
 * @brief 快速排序的核心算法
 * 
 * @param A 待排序的数组
 * @param left 递归的左边的索引
 * @param right 递归的右边的索引
 */
void Quick(int A[],int left,int right)
{
    int l = left;                                   // 左下标
    int r = right;                                  // 右边的下标
    int standard = A[left];                         // 将第一个值作为标准值
    int temp = 0;

    if(left < right)
    {
        while(l < r)                                // 循环找比标准值大的数和比标准值小的数
        {
            while(l < r && standard <= A[r])        // 如果右边的数字大于等于标准值，则 r--
            {
                r--;
            }
            // 程序执行到这，l > r 或 standard > A[r]
            // 第一次循环时，左边的数等于标准值
            A[l] = A[r];                            // 使用右边的数字替换左边的数

            while(l < r && A[l] <= standard)        // 如果左边的数字小于等于标准值，则 l++
            {
                l++;
            }
            // 程序执行到这，l > r 或者 A[l] > standard
            A[r] = A[l];                            // 使用左边的数替换右边的数
        }

        // 把标准数赋值给左边所在的位置的元素
        A[l] = standard;

        Quick(A,left,l);                            // 处理左边的数字
        Quick(A,l+1,right);                         // 处理右边的数字
    } 
}

七、归并排序

  归并排序（Merge Sorting）是利用 归并 的思想实现的排序方法。该算法采用经典的 分治（Divide and Conquer）策略（分治法将问题 分（divide）成一些小的问题然后递归求解，而 治（conquer）的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）。

img

  这个算法中基本操作是合并两个已排序的表。基本的合并算法是取两个输入数组 A 和 B，一个输出数组 C，以及三个计数器 Aptr、Bptr、Cptr，它们初始置于对应数组的开始端。A[Aptr] 和 B[Bptr] 中较小者被拷贝到 C 中的下一个位置，相关的计数器向前移动一步。当两个输入表有一个用完的时候，则将另一个表中剩余部分拷贝到 C 中。合并两个已排序的表的时间是线性的，因为最多进行了 N-1 次比较，其中 N 是元素的总数。如果 N =1，那么只有一个元素需要排序。否则，递归地将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用上述描述的算法再将这两部分合并在一起。

/**
 * @brief 归并排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void MergeSort(int A[],int N)
{
    int temp[N];                                    // 归并排序需要一个额外的空间
    Divide(A,0,N-1,temp);

}

/**
 * @brief 分解的方法，每分解一次就合并
 * 
 * @param A 待排序的数组
 * @param left 左边有序序列的初始索引
 * @param right 右边有序序列的最后一个索引
 * @param temp 用作中转的数组
 */
void Divide(int A[],int left,int right,int temp[])
{
    int middle = 0;

    if(left < right)
    {
        middle = (right - left)  / 2 + left;        // 中间索引
        Divide(A,left,middle,temp);                 // 向左递归分解
        Divide(A,middle+1,right,temp);              // 向右递归分解
        Merge(A,left,middle,right,temp);            // 合并
    }
}

/**
 * @brief 合并的方法
 * 
 * @param A 排序的原始数组
 * @param left 左边有序序列的初始索引
 * @param middle 中间索引
 * @param right 右边有序序列的最后一个索引
 * @param temp 用作中转的数组
 */
void Merge(int A[],int left,int middle,int right,int temp[])
{
    int i = left;                                   // 初始化i，左边有序序列的初始索引
    int j = middle + 1;                             // 初始化hj，右边有序序列的初始索引
    int t = 0;                                      // 指向temp数组的当前索引
    int tempLeft = 0;

    // 先把左右两边（有序）的数据按照规则填充到tenmp数组
    // 直到左右两边的有序序列，有一边处理完毕为止
    while(i <= middle && j <= right)
    {
        if(A[i] <= A[j])                            // 如果左边有序序列的当前元素小于等于右边的有序序列的当前元素
        {
            temp[t] = A[i];                         // 将左边的当前元素拷贝到temp数字
            t++;
            i++;
        }
        else                                        // 反之，将右边有序序列的当前元素拷贝到temp数组中
        {
            temp[t] = A[j];
            t++;
            j++;
        }
    }

    // 把有剩余的数据的一边的数据全部填充到temp
    while(i <= middle)                              // 说明左边的有序序列还有剩余的元素
    {
        temp[t] = A[i];                             // 全部拷贝到temp数组中
        t++;
        i++;
    }

    while(j <= right)                               // 说明右边的有序序列还有剩余的元素
    {
        temp[t] = A[j];                             // 全部拷贝到temp数组中
        t++;
        j++;
    }

    // 将temp数组重新拷贝到A
    // 并不是每次都拷贝所有的数据
    // 第一次合并 tempLeft = 0,right = 1
    // 第二次合并 tempLeft = 2,right = 3
    // 第三次合并 tempLeft = 3,right = 5
    // ……
    // 最后一次合并 tempLeft = 0,right = right
    t = 0;
    tempLeft = left;
    while(tempLeft <= right)
    {
        A[tempLeft] = temp[t];
        t++;
        tempLeft++;
    }
}

八、基数排序

  基数排序（Radix Sort）属于“分配式排序”（Distributin Sort）,又称“桶子法”（Bucket Sort 或 Bin Sort），它是桶排序的扩展。顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用 。基数排序是属于稳定性的排序，它是效率高稳定性排序法。基数排序是这样实现的：将整数按位数割成不同的数字，然后按每个位数分别比较。

  基数排序 的 基本思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行依次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

  • 第一轮排序：将每个元素的个数取出，然后看这个数应该放在哪个对应的桶（桶就是一个一维数组）；
  • 按照这个桶的顺序（一维数组的下标）依次取出数据，放入原来数组；
  • 第二轮排序：将每个元素的十位数取出，然后看这个应该放在哪个对应的桶（桶就是一个一维数组）；
  • 按照这个桶的顺序（一维数组的下标）依次取出数据，放入原来数组；
  • 第三轮排序：将每个元素的百位数取出，然后看这个应该放在哪个对应的桶（桶就是一个一维数组）；
  • 按照这个桶的顺序（一维数组的下标）依次取出数据，放入原来数组；

img

#define BucketNum   10                                              // 桶的个数

/**
 * @brief 基数排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void RadixSort(int A[],int N)
{
    int i = 0, j = 0, k = 0, l = 0, n = 0;
    int digitOfElement = 0;
    int index = 0;

    // 定义一个二维数组表示10个桶，每个桶就是一个一维数组
    // 为了防止在放数的时候，数据溢出，则每个一维数组（桶）的大小定义为N
    // 基数排序是使用空间换时间的经典算法
    int bucket[BucketNum][N];

    // 为了记录每个桶中，实际放了多少个数据，
    // 我们定义一个一维数组来记录各个桶的每次放入的数据个数
    // bucketElementCounts[0]记录的就是bucket[0]桶的放入数据个数
    int bucketElementCounts[BucketNum] = {0};

    // 得到数组中最大数的位数
    int max = A[0];                                                 // 假定一个数是最大的
    int maxLength = 0;                                              // 最大数的位数

    for(i = 0; i < N; i++)
    {
        if(A[i] > max)
        {
            max = A[i];
        }
    }

    // 得到最大数是几位数
    do
    {
        maxLength++;
    }while(max /= 10);

    for(i = 0, n = 1; i < maxLength; i++, n *= 10)
    {
        // 针对每个数对应的进行排序，第一次是个数，第二次是十位，第三次是百位，……
        for(j = 0; j < N; j++)
        {
            digitOfElement = A[j] / n % 10;                         // 取出每个元素的对应位的值
            // bucket[digitOfElement]表示对应的桶
            // bucketElementCounts[digitOfElement]表示对应桶存放元素的个数
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] =  A[j];
            bucketElementCounts[digitOfElement]++;
        }

        // 按照这个桶的顺序（一维数组的表表依次取出数据，放入原来的数组）
        index = 0;
  
        for(k = 0; k < BucketNum; k++)                              // 遍历每一个桶，并将桶中的数据，放入到原数组中
        {
            if(bucketElementCounts[k] != 0)                         // 如果桶中有数据，才放入到原数组
            {
                for(l = 0; l < bucketElementCounts[k]; l++)         // 循环该桶即第k个桶（第k个一维数组）
                {
                    A[index] = bucket[k][l];                        // 取出元素放入到原数组
                    index++;
                }
            }
            // 每轮结束后，需要将每个bucketElementCounts[k]清零
            bucketElementCounts[k] = 0;
        }
    }
}

如果有负数的情况，可以单独处理负数，采用绝对的方式来处理，最后再把数组反过来；

九、堆排序

  堆排序是利用 堆 这种数据结构而设计的一种排序算法，堆排序是一种 选择排序，它的最坏、最好、平均时间复杂度均为 O(logN)，它是一种不稳定的排序。

  堆排序的基本思想是：

  1. 将待排序序列构造成一个大顶堆；
  2. 此时，这个序列的最大值就是堆顶的根节点；
  3. 将其与末尾元素进行交换，此时末尾元素就为最大值；
  4. 然后将剩下的 n-1 个元素重新构造一个堆，这样会得到 n 个元素的次小值。如此反复执行，便得到一个有序序列了；

img

/**
 * @brief 堆排序
 *
 * @param A 待排序的数组
 * @param N 待排序的数据的元素的个数
 */
void HeapSort(int A[],int N)
{
    int i = 0, j = 0;
    int temp = 0;

    for(i = N/2-1; i >= 0; i--)
    {
        AdjustHeap(A,i,N);
    }

    for(j = N-1; j >0 ; j--)
    {
        // 交换
        temp = A[j];
        A[j] = A[0];
        A[0] = temp;
        AdjustHeap(A,0,j);
    }
}

/**
 * @brief 将以i对应的非叶子节点的树调整为大顶堆
 * 
 * @param array 待调整的数组
 * @param i 表示非叶子节点在数组中的索引
 * @param n 待调整的数据的元素的个数
 */
void AdjustHeap(int array[],int i,int n)
{
    int temp = array[i];
    int k = 0;
    // k=i*2+1，k是i节点的左子节点
    for(k = i*2+1; k < n; k = k*2+1)
    {
        if(k+1 < n && array[k] < array[k+1])            // 左子节点的值小于右子节点的值
        {
            k++;                                        // k指向右子节点
        }
        if(array[k] > temp)                             // 如果子节点大于父节点
        {
            array[i] = array[k];                        // 把较大的值赋值给当前节点
            i = k;                                      // i指向k，继续循环比较
        }
        else
        {
            break;
        }
    }
    // 当for循环结束后，已经将以i为父节点的树的最大值，放在了最顶上，即局部大顶堆
    array[i] = temp;                                    //将temp放在调整后的位置
}

一般升序采用大顶堆，降序采用小顶堆；

十、排序算法的比较

排序方法 平均时间复杂度 最坏情况下时间复杂度 额外空间复杂度 稳定性
冒泡排序 \(O(N^{2})\) \(O(N^{2})\) \(O(1)\) 稳定
简单选择排序 \(O(N^{2})\) \(O(N^{2})\) \(O(1)\) 不稳定
直接插入排序 \(O(N^{2})\) \(O(N^{2})\) \(O(1)\) 稳定
希尔排序 \(O(N^{d})(1<d<2)\) \(O(N^{2})\) \(O(1)\) 不稳定
快速排序 \(O(NlogN)\) \(O(N^{2})\) \(O(logN)\) 不稳定
归并排序 \(O(NlogN)\) \(O(NlogN)\) \(O(N)\) 稳定
堆排序 \(O(NlogN)\) \(O(NlogN)\) \(O(1)\) 不稳定
桶排序 \(O(N+K)\) \(O(N^{2})\) \(O(N+K)\) 稳定
基数排序 \(O(N*K)\) \(O(N*K)\) \(O(N+K)\) 稳定
  • 稳定：如果 a 原本在 b 前面，而 a = b，排序之后 a 仍然在 b 的前面；
  • 不稳定：如果 a 原本在 b 前面，而 a = b，排序之后 a 可能会出现在 b 的后面；
  • 内排序：所有排序操作都在内存中完成；
  • 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存 的数据传输才能进行；
  • N：数据规模
  • K：桶的个数

标签：temp,int,43,param,算法,数组,排序,left
From： https://www.cnblogs.com/kurome/p/17539294.html

相关文章

  • 堆排序之前篇：关于堆
      1. 堆的定义和性质堆是一种特殊的数据结构，它是一颗完全二叉树，且满足以下性质：堆中某个节点的值总是不大于或不小于其父节点的值。如果父节点的值不大于其子节点的值，这样的堆称为最小堆；如果父节点的值不小于其子节点的值，这样的堆称为最大堆。堆可以用数组来存储，因为......
  • 算法题-生成窗口最大值数组
    https://leetcode.cn/problems/sliding-window-maximum/ classSolution{publicint[]maxSlidingWindow(int[]nums,intk){if(nums==null||nums.length==0||k<0){returnnull;}int[]result=newint[nums.length-k+1];......
  • 记录拖动排序
    最近项目中要做一个拖动排序功能，首先想到的是之前项目中用过的antd自带的tree和table的拖动排序，但是只能在对应的组建里使用。这里用的是自定义组件，随意拖动排序，所以记录一下实现流程react-dndantd组件的拖动排序都是用的这个库，使用比较灵活，但是要配置的东西比较多，需求复杂时使......
  • 四种语言刷算法之子集 II
    力扣90. 子集II1、C/***Returnanarrayofarraysofsize*returnSize.*Thesizesofthearraysarereturnedas*returnColumnSizesarray.*Note:Bothreturnedarrayand*columnSizesarraymustbemalloced,assumecallercallsfree().*/voidbacktr......
  • Java版归并排序 演示代码（带注释）
    Code：importjava.util.Arrays;/***归并排序*/publicclassMergeSort{/***私有化*/privateMergeSort(){}/***归并排序的sort方法*@paramarr待排序数组*@param<E>可比较的元素*/publicstatic<Eex......
  • 哨兵 查找算法_右手 深度
    1importnumpyasnp23#生成一个10*10全为0的array45maze=np.zeros((10,10),dtype=int)6#给array使用数字9包围7#添加行8maze=np.insert(maze,0,np.full(10,9,dtype=int),axis=0)9maze=np.insert(maze,len(maze),np.full(10,9,dt......
  • 排序 sorted
    l=sorted([36,5,-12,9,-21])print(l)'''[-21,-12,5,9,36]'''l=sorted([36,5,-12,9,-21],key=abs)print(l)'''[5,9,-12,-21,36]''' #按照元祖里的key的name首字母lis=[('Bob',......
  • Miller_Rabin算法快速判断大数是否为素数
    Miller_Rabin算法快速判断大数是否为素数并不是绝对，这只是一种判断大概率为素数的方法首先根据费马小定理有：\(a^{p-1}=1\pmodp(a不为p的倍数且p不是素数)\)又因为\(p\)为素奇数，所以\(p-1\)为偶数，表示为\(p-1=2^dm\)所以有\(a^{p-1}-1=0\pmodp\)\(a^{2^dm}-1=0\pmodp\)\((......
  • js 对文字排序和对数字排序
    1、对文字排序 <html><body><scripttype="text/javascript">vararr=newArray(6)arr[0]="George"arr[1]="John"arr[2]="Thomas"arr[3]="James"arr[4]="Adrew"arr......
  • KMP算法
    一.引入(洛谷P3375)给出两个字符串\(s_1\)和\(s_2\)，若\(s_1\)的区间\([l,r]\)子串与\(s_2\)完全相同，则称\(s_2\)在\(s_1\)中出现了，其出现位置为\(l\)。现在请你求出\(s_2\)在\(s_1\)中所有出现的位置。\(s1\)称为文本串，\(s2\)称为模板链二.简陋版本不难......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99