欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法分析

程序员文章站 2022-03-04 21:08:22
...

算法分析

一般而言,需要考虑的因素有以下四点: 
1.待排序的记录数目n的大小; 
2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小; 
3.关键字的结构及其分布情况; 
4.对排序稳定性的要求。

 

 

 

设待排序元素的个数为n
1)当n量级为万到十万级:若内存有限,不要求稳定性:快速排序。若内存空间允许,且要求稳定性:归并排序

2)当n量级为1000以下,采用直接插入排序

3)当n量级为1000以上,5000以下,采用希尔排序。

4)当n量级为百万级别,使用堆排序。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。

 

 

 

 

插入排序:

具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

 

算法分析

void InsertionSort(int A[], int n)

{

    for (int i = 1; i < n; i++)         // 类似抓扑克牌排序

    {

        int get = A[i];                 // 右手抓到一张扑克牌

        int j = i - 1;                  // 拿在左手上的牌总是排序好的

        while (j >= 0 && A[j] > get)    // 将抓到的牌与手牌从右向左进行比较

        {

            A[j + 1] = A[j];            // 如果该手牌比抓到的牌大,就将其右移

            j--;

        }

        A[j + 1] = get; // 直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)

    }

}

 

 

 

 

快速排序:

算法分析

第一步:首先我们从数组的left位置取出该数(20)作为基准(base)参照物。

 

第二步:从数组的right位置向前找,一直找到比(base)小的数,如果找到,将此数赋给left位置(也就是将10赋给20), 此时数组为:1040501060        

leftright指针分别为前后的10

 

第三步:从数组的left位置向后找,一直找到比(base)大的数,如果找到,将此数赋给right的位置(也就是40赋给10),此时数组为:1040504060

leftright指针分别为前后的40

 

第四步:重复“第二,第三“步骤,直到leftright指针重合,最后将(base)插入到40的位置,此时数组值为: 1020504060,至此完成一次排序。

 

第五步:此时20已经潜入到数组的内部,20的左侧一组数都比20小,20的右侧作为一组数都比20大,以20为切入点对左右两边数按照"第一,第二,第三,第四"步骤进行,最终快排大功告成。

 

#include <stdio.h>

int a[101],n;//定义全局变量,这两个变量需要在子函数中使用

void quicksort(int left,int right)

{

    int i,j,t,temp;

    if(left>right)

       return;

                               

    temp=a[left]; //temp中存的就是基准数

    i=left;

    j=right;

    while(i!=j)

    {

         //顺序很重要,要先从右边开始找

         while(a[j]>=temp && i<j)

                  j--;

         //再找右边的

         while(a[i]<=temp && i<j)

                  i++;

         //交换两个数在数组中的位置

         if(i<j)

         {

                  t=a[i];

                  a[i]=a[j];

                  a[j]=t;

         }

    }

    //最终将基准数归位

    a[left]=a[i];

    a[i]=temp;

                            

    quicksort(left,i-1);//继续处理左边的,这里是一个递归的过程

    quicksort(i+1,right);//继续处理右边的 ,这里是一个递归的过程

}



 

 

 

 

堆排序:

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了

void Swap(int A[], int i, int j)

{

    int temp = A[i];

    A[i] = A[j];

    A[j] = temp;

}



void Heapify(int A[], int i, int size)  // 从A[i]向下进行堆调整

{

    int left_child = 2 * i + 1;         // 左孩子索引

    int right_child = 2 * i + 2;        // 右孩子索引

    int max = i;                        // 选出当前结点与其左右孩子三者之中的最大值

    if (left_child < size && A[left_child] > A[max])

        max = left_child;

    if (right_child < size && A[right_child] > A[max])

        max = right_child;

    if (max != i)

    {

        Swap(A, i, max);                // 把当前结点和它的最大(直接)子节点进行交换

        Heapify(A, max, size);          // 递归调用,继续从当前结点向下进行堆调整

    }

}



int BuildHeap(int A[], int n)           // 建堆,时间复杂度O(n)

{

    int heap_size = n;

    for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每一个非叶结点开始向下进行堆调整

        Heapify(A, i, heap_size);

    return heap_size;

}



void HeapSort(int A[], int n)

{

    int heap_size = BuildHeap(A, n);    // 建立一个最大堆

    while (heap_size > 1)           // 堆(无序区)元素个数大于1,未完成排序

    {

        // 将堆顶元素与堆的最后一个元素互换,并从堆中去掉最后一个元素

        // 此处交换操作很有可能把后面元素的稳定性打乱,所以堆排序是不稳定的排序算法

        Swap(A, 0, --heap_size);

        Heapify(A, 0, heap_size);     // 从新的堆顶元素开始向下进行堆调整,时间复杂度O(logn)

    }

}



 

 

 

 

 

归并:

 归并排序的实现分为递归实现非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用,我们将一个大问题分割成小问题分别解决,然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并,然后四四归并,然后是八八归并,一直下去直到归并了整个数组。

  归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作,归并操作步骤如下:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾
void Merge(int A[], int left, int mid, int right)// 合并两个已排好序的数组A[left...mid]和A[mid+1...right]

{

    int len = right - left + 1;

    int *temp = new int[len];       // 辅助空间O(n)

    int index = 0;

    int i = left;                   // 前一数组的起始元素

    int j = mid + 1;                // 后一数组的起始元素

    while (i <= mid && j <= right)

    {

        temp[index++] = A[i] <= A[j] ? A[i++] : A[j++];  // 带等号保证归并排序的稳定性

    }

    while (i <= mid)

    {

        temp[index++] = A[i++];

    }

    while (j <= right)

    {

        temp[index++] = A[j++];

    }

    for (int k = 0; k < len; k++)

    {

        A[left++] = temp[k];

    }

}



void MergeSortRecursion(int A[], int left, int right)    // 递归实现的归并排序(自顶向下)

{

    if (left == right)    // 当待排序的序列长度为1时,递归开始回溯,进行merge操作

        return;

    int mid = (left + right) / 2;

    MergeSortRecursion(A, left, mid);

    MergeSortRecursion(A, mid + 1, right);

    Merge(A, left, mid, right);

}



void MergeSortIteration(int A[], int len)    // 非递归(迭代)实现的归并排序(自底向上)

{

    int left, mid, right;// 子数组索引,前一个为A[left...mid],后一个子数组为A[mid+1...right]

    for (int i = 1; i < len; i *= 2)        // 子数组的大小i初始为1,每轮翻倍

    {

        left = 0;

        while (left + i < len)              // 后一个子数组存在(需要归并)

        {

            mid = left + i - 1;

            right = mid + i < len ? mid + i : len - 1;// 后一个子数组大小可能不够

            Merge(A, left, mid, right);

            left = right + 1;               // 前一个子数组索引向后移动

        }

    }

}

 

 

 

 

 

桶排序: 这个算法就好比有11个桶,编号从0~10。每出现一个数,就将对应编号的桶中的放一个小旗子,最后只要数数每个桶中有几个小旗子就OK了。此处的每一个桶的作用其实就是标记每个数出现的次数,

 

算法分析

 

#include <stdio.h>

int main()

{

    int book[1001],i,j,t,n;

    for(i=0;i<=1000;i++)

        book[i]=0;

    scanf("%d",&n);//输入一个数n,表示接下来有n个数

    for(i=1;i<=n;i++)//循环读入n个数,并进行桶排序

    {

        scanf("%d",&t);  //把每一个数读到变量t中

        book[t]++;  //进行计数,对编号为t的桶放一个小旗子

    }

    for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶

        for(j=1;j<=book[i];j++)  //出现了几次就将桶的编号打印几次

             printf("%d ",i);

    getchar();getchar();

    return 0;

}



 

 

 

 

排序之外部排序

有时,待排序的文件很大,计算机内存不能容纳整个文件,这时候对文件就不能使用内部排序了(这里做一下说明,其实所有的排序都是在内存中做的,这里说的内部排序是指待排序的内容在内存中就可以完成,而外部排序是指待排序的内容不能在内存中一下子完成,它需要做内外存的内容交换),外部排序常采用的排序方法也是归并排序,这种归并方法由两个不同的阶段组成:

1、采用适当的内部排序方法对输入文件的每个片段进行排序,将排好序的片段(成为归并段)写到外部存储器中(通常由一个可用的磁盘作为临时缓冲区),这样临时缓冲区中的每个归并段的内容是有序的。

2、利用归并算法,归并第一阶段生成的归并段,直到只剩下一个归并段为止。

例如要对外存中4500个记录进行归并,而内存大小只能容纳750个记录,在第一阶段,我们可以每次读取750个记录进行排序,这样可以分六次读取,进行排序,可以得到六个有序的归并段,如下图:

算法分析

每个归并段的大小是750个记录,记住,这些归并段已经全部写到临时缓冲区(由一个可用的磁盘充当)内了,这是第一步的排序结果。

完成第二步该怎么做呢?这时候归并算法就有用处了,算法描述如下:

1、将内存空间划分为三份,每份大小250个记录,其中两个用作输入缓冲区,另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并,先从每个归并段中读取250个记录到输入缓冲区,对其归并,归并结果放到输出缓冲区,当输出缓冲区满后,将其写道临时缓冲区内,如果某个输入缓冲区空了,则从相应的归并段中再读取250个记录进行继续归并,反复以上步骤,直至Segment_1和Segment_2全都排好序,形成一个大小为1500的记录,然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。

2、对归并好的大小为1500的记录进行如同步骤1一样的操作,进行继续排序,直至最后形成大小为4500的归并段,至此,排序结束。

排序之外部排序

有时,待排序的文件很大,计算机内存不能容纳整个文件,这时候对文件就不能使用内部排序了(这里做一下说明,其实所有的排序都是在内存中做的,这里说的内部排序是指待排序的内容在内存中就可以完成,而外部排序是指待排序的内容不能在内存中一下子完成,它需要做内外存的内容交换),外部排序常采用的排序方法也是归并排序,这种归并方法由两个不同的阶段组成:

1、采用适当的内部排序方法对输入文件的每个片段进行排序,将排好序的片段(成为归并段)写到外部存储器中(通常由一个可用的磁盘作为临时缓冲区),这样临时缓冲区中的每个归并段的内容是有序的。

2、利用归并算法,归并第一阶段生成的归并段,直到只剩下一个归并段为止。

例如要对外存中4500个记录进行归并,而内存大小只能容纳750个记录,在第一阶段,我们可以每次读取750个记录进行排序,这样可以分六次读取,进行排序,可以得到六个有序的归并段,如下图:

算法分析

每个归并段的大小是750个记录,记住,这些归并段已经全部写到临时缓冲区(由一个可用的磁盘充当)内了,这是第一步的排序结果。

完成第二步该怎么做呢?这时候归并算法就有用处了,算法描述如下:

1、将内存空间划分为三份,每份大小250个记录,其中两个用作输入缓冲区,另外一个用作输出缓冲区。首先对Segment_1和Segment_2进行归并,先从每个归并段中读取250个记录到输入缓冲区,对其归并,归并结果放到输出缓冲区,当输出缓冲区满后,将其写道临时缓冲区内,如果某个输入缓冲区空了,则从相应的归并段中再读取250个记录进行继续归并,反复以上步骤,直至Segment_1和Segment_2全都排好序,形成一个大小为1500的记录,然后对Segment_3和Segment_4、Segment_5和Segment_6进行同样的操作。

2、对归并好的大小为1500的记录进行如同步骤1一样的操作,进行继续排序,直至最后形成大小为4500的归并段,至此,排序结束。

可以用一个图示表示上述算法的归并效果:算法分析

以上对外部排序如何使用归并算法进行排序进行了简要总结,提高外部排序需要考虑以下问题:

1、如何减少排序所需的归并趟数。

2、如果高效利用程序缓冲区,使得输入、输出和CPU运行尽可能地重叠。

3、如何生成初始归并段(Segment)和如何对归并段进行归并。

 

提高外部排序需要考虑以下问题:

1、如何减少排序所需的归并趟数。

2、如果高效利用程序缓冲区,使得输入、输出和CPU运行尽可能地重叠。

3、如何生成初始归并段(Segment)和如何对归并段进行归并。

 

相关标签: 算法