算法分析

一般而言，需要考虑的因素有以下四点： 
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）， 此时数组为：10，40，50，10，60，        

left和right指针分别为前后的10。

 

第三步：从数组的left位置向后找，一直找到比（base）大的数，如果找到，将此数赋给right的位置（也就是40赋给10），此时数组为：10，40，50，40，60，

left和right指针分别为前后的40。

 

第四步：重复“第二,第三“步骤，直到left和right指针重合，最后将（base）插入到40的位置，此时数组值为： 10，20，50，40，60，至此完成一次排序。

 

第五步：此时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）和如何对归并段进行归并。