精华内容
下载资源
问答
  • n 5 ( 6 " (2017 2018 c 1 ) : 6: : K n o o !JJJKKK zzzKKK2, 30 1. a.n|O ( ) (A) 'X (B) !6( (C) !a. (D) (a. 2. k: LChead, K^ ( ) (A) headNULL (B) head-nextNULL (C) head-nexthead (D) head!...
  • 本节以静态查找表的顺序存储结构为例做详细的介绍。 顺序查找的实现 静态查找表用顺序存储结构表示时,顺序查找的查找过程为:从表中的最后一个数据元素开始,逐个同记录的关键字做比较,如果匹配成功,则查找.....

    通过前面对静态查找表的介绍,静态查找表即为只做查找操作的查找表。

    静态查找表既可以使用顺序表表示,也可以使用链表结构表示。虽然一个是数组、一个链表,但两者在做查找操作时,基本上大同小异。

    本节以静态查找表的顺序存储结构为例做详细的介绍。

    顺序查找的实现

    静态查找表用顺序存储结构表示时,顺序查找的查找过程为:从表中的最后一个数据元素开始,逐个同记录的关键字做比较,如果匹配成功,则查找成功;
    反之,如果直到表中第一个关键字查找完也没有成功匹配,则查找失败。

    顺序查找的具体实现代码为:
    #include <stdio.h>
    #include <stdlib.h>
    #define keyType int
    typedef struct
    { keyType key;  
    //查找表中每个数据元素的值 //如果需要,还可以添加其他属性 }ElemType; typedef struct
    { ElemType *elem;  // 存放查找表中数据元素的数组 int length;   // 记录查找表中数据的总数量 }SSTable; // 创建查找表 void Create(SSTable **st, int length)
    { (
    *st) = (SSTable*)malloc(sizeof(SSTable)); (*st)->length = length; printf("输入表中的数据元素:\n"); // 根据查找表中数据元素的总长度,在存储时,从数组下标为 1 的空间开始存储数据 for (int i=1; i<=length; i++)
       { scanf(
    "%d", &((*st)->elem[i].key)); } }
    // 查找表查找的功能函数,其中key为关键字 int Search_seq(SSTable *st, keyType key)
    { st
    ->elem[0].key = key;  // 将关键字作为一个数据元素存放到查找表的第一个位置,起监视哨的作用 int i = st->length; // 从查找表的最后一个数据元素依次遍历,一直遍历到数组下标为0 while (st->elem[i].key != key)
      { i
    --; } //如果 i=0,说明查找失败;反之,返回的是含有关键字key的数据元素在查找表中的位置 return i; }
    int main(int argc, const char * argv[])
    { SSTable
    *st; Create(&st, 6); getchar(); printf("请输入查找数据的关键字:\n"); int key; scanf("%d", &key); int location=Search_seq(st, key); if (location == 0)
       { printf(
    "查找失败"); }
       else
       { printf("数据在查找表中的位置为:%d", location); }
    return 0; }
    可运行代码中设置了一个固定长度为
    6 的顺序表,例如在查找表为{1,2,3,4,5,6}找到关键字为 1 的数据元素的位置,则运行效果为: 输入表中的数据元素: 1 2 3 4 5 6 请输入查找数据的关键字: 2 数据在查找表中的位置为:2

     

    同时,在程序中初始化创建查找表时,由于是顺序存储,所以将所有的数据元素存储在数组中,但是把第一个位置留给了用户用于查找的关键字。例如,在顺序表{1,2,3,4,5,6}中查找数据元素值为 7 的元素,则添加后的顺序表为:

    图 1 顺序表中的监视哨

    顺序表的一端添加用户用于搜索的关键字,称作“监视哨”。
    图 1 中监视哨的位置也可放在数据元素 6 的后面(这种情况下,整个查找的顺序应有逆向查找改为顺序查找)。
    放置好监视哨之后,顺序表遍历从没有监视哨的一端依次进行,如果查找表中有用户需要的数据,则程序输出该位置;反之,程序会运行至监视哨,此时匹配成功,程序停止运行,但是结果是查找失败。

    顺序查找的性能分析

    查找操作的性能分析主要考虑其时间复杂度,而整个查找过程其实大部分时间花费在关键字和查找表中的数据进行比较上。

    所以查找算法衡量好坏的依据为:查找成功时,查找的关键字和查找表中的数据元素中进行过比较的个数的平均值,称为平均查找长度(Average Search Length,用 ASL 表示)。

    例如,对于具有 n 个数据元素的查找表,查找成功的平均查找长度的计算公式为:

    Pi 为第 i 个数据元素被查找的概率,所有元素被查找的概率的和为 1;Ci 表示在查找到第 i 个数据元素之前已进行过比较的次数。若表中有 n 个数据元素,查找第一个元素时需要比较 n 次;查找最后一个元素时需要比较 1 次,所以有 Ci = n – i + 1
    一般情况,表中各数据元素被查找的概率是未知的。假设含有 n 个数据元素的查找表中,各数据被查找的概率是相同的,则:

    换算后,得:

    如果对于查找表中各个数据元素有可能被查找的概率提前已知,就应该根据其查找概率的大小对查找表中的数据元素进行适当的调整:被查找概率越大,离查找出发点 i 越近;反之,越远。这样可以适当的减少查找操作中的比较次数。

    上边的平均查找长度是在假设查找算法每次都成功的前提下得出的。而对于查找算法来说,查找成功和查找失败的概率是相同的。所以,查找算法的平均查找长度应该为查找成功时的平均查找长度加上查找失败时的平均查找长度。

    对于含有 n 个数据的表来说,每次查找失败,比较的次数都是 n+1。所以查找算法的平均查找长度的计算公式为:

    总结

    本节主要介绍了静态查找表的顺序存储的表示和查找算法的实现,其中使用监视哨对普通的顺序表的遍历算法做了改进,在数据量大的情况下,能够有效提高算法的运行效率。

    转载于:https://www.cnblogs.com/ciyeer/p/9065772.html

    展开全文
  • 现代的设计任务大多通过计算机编程来完成,而算法起到了至关重要的作用。可以毫不夸张地说,算法是一切程序设计的灵魂和基础。选择合理的算法,可以起到事半功倍的效果。  赵志云、衡友跃编著的《Java常用算法手册...
  • 排序算法 快速排序【详细步骤图解】快速排序主要思想图解第一轮分割序列第二轮分割序列 --- 左子序列小结第三轮分割序列 --- 右子序列C++实现总结 快速排序 给定一个序列:22 33 49 47 33' 12 68 29 进行快速排序 ...

    快速排序

    给定一个序列:22 33 49 47 33' 12 68 29

    进行快速排序

    主要思想

    • 从序列中,任选一个记录k作为轴值 pivot

      选择策略:

      • 第一个元素
      • 最后一个元素
      • 中间元素
      • 随机选择
    • 将剩余的元素,分割成 左子序列 L右子序列 R

    • L 中所有元素都 < k, R 中所有元素都 > k

    • 对 L 和 R递归进行快排,直到子序列中有 0 个 或者 1 个元素,退出

    图解

    初始数组:

    选定47为轴值pivot

    image-20200522200024944

    pivot与最后一个值29进行交换(pivot放到最后面

    image-20200522200152016

    接下来,以pivot=47为界,分成左子序列 L和右子序列 R

    47大的都放在右边,比47小的都放在左边(用的交换)

    遍历数组

    • 两个指针leftright
    • left != right的时候
      • arr[left]的,小于等于pivot,且left < right的时候,left右移
        • 如果leftright未相遇,把left的值赋给right对应的值
        • arr[right] = arr[left]
        • left指针停止移动,轮到right移动
      • arr[right]的值,大于等于pivot,且right > left的时候,right左移
        • 如果leftright未相遇。把right的值赋给left对应的值
        • arr[left] = arr[right]
        • right指针停止移动,轮到left移动
    • 注意:轴值用pivot保存

    第一轮分割序列

    image-20200522213014584
    pivot=47和最后一个值互换

    image-20200522205447912

    22 <= 47left向右移动

    image-20200522205623534

    33 <= 47left向右移动

    image-20200522205648022

    49 > 47,不满足arr[left] <= pivot

    left的值赋给right

    arr[right] = arr[left]

    image-20200522210144784

    赋值过后,left不动,right向左移动

    image-20200522211704648

    68 >= 47,right向左移动

    image-20200522211823993

    12 < 47,不满足arr[right] >= pivot

    right的值赋给left

    arr[left] = arr[right]

    image-20200522211941103

    赋值过后,right不动,left向右移动

    image-20200522212237784

    29 < 47left向右移动

    image-20200522212313112

    33' < 47left向右移动

    image-20200522215707618

    向右移动后,left == right,退出循环

    pivot赋给arr[left]

    image-20200522215538138

    至此,第一轮分割序列完成

    第二轮分割序列 — 左子序列

    经过第一轮分割,47左边的是左子序列,右边是右子序列

    第二轮对左子序列分割,选择中间值作为pivot

    image-20200522223949257

    12和33'进行交换

    image-20200522220137128

    22 > 12,不满足arr[left] <= pivot

    arr[left]赋给arr[right]

    arr[right] = arr[left]

    image-20200522220327264

    赋值过后,left不动,right向左移动

    29、33'、33都比12大,所以right一直移动到下图位置

    image-20200522220446889

    33 > 12,right继续向左移动

    image-20200522220515361

    此时right == left,终止循环

    pivot赋给arr[left]

    image-20200522220557616

    至此,左子序列1也分割完成了

    小结

    快排就是一个递归的过程,分割得到左子序列

    再对左子序列进行快排分割,得到左子序列的左子序列…

    处理完左边,再去处理右边的右子序列

    第三轮分割序列 — 右子序列

    右子序列只有47、68、49,选择48作为轴值 pivot

    image-20200522220854832

    pivot和最后一个值交换

    image-20200522221012928

    47、49都比pivot=68小,left一直向右移动,直到left == right

    image-20200522221104705

    分割之后,只剩下左子序列:47、49

    47、49,选49作为轴值,得到左子序列47

    子序列只剩下一个元素47,就不必排序了,右边排序结束

    结果:47、49、68

    C++实现

    选择中间的值作为轴值

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <unordered_map>
    #include <unordered_set>
    #include <string>
    #include <stack>
    #include <cmath>
    #include <map>
    
    using namespace std;
    
    
    /**
     *
     * @param arr   待分割的序列
     * @param left  左边界
     * @param right 右边界
     * @return      分割后轴值的位置
     */
    
    template<class T>
    int PartitionArr(vector<T>& arr, int left, int right) {
        T temp = arr[right];
        while (left != right) {
            while (arr[left] <= temp && left < right) {
                left++;
            }
            if (left < right) {
                arr[right] = arr[left];
                // 赋值后,left不动,right向左移
                right--;
            }
            while (arr[right] >= temp && right > left) {
                right--;
            }
            if (left < right) {
                arr[left] = arr[right];
                // 赋值后,right不动,left向右移
                left++;
            }
        }
        // 当left == right,把轴值放回left上
        arr[left] = temp;
        return left;
    }
    
    /**
     *
     * @param arr   待排序数组
     * @param left  左边界
     * @param right 右边界
     */
    template<class T>
    void quickSort(vector<T>& arr, int left, int right) {
        // 子序列剩下0或1个元素,排序结束
        if (right <= left) {
            return;
        }
    
        //  选择数组中间作为轴值
        int pivot = (left + right) / 2;
        // 把轴值放到数组最后面
        swap(arr[right], arr[pivot]);
        // 分割后轴值的位置
        // 分割后,左边值 < 轴值 < 右边值
        pivot = PartitionArr(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
    
    
    int main() {
        vector<int> arr = { 22,33,49,47,33,12,68,29 };
        for (auto& i : arr) {
            cout << i << ' ';
        }
    
        cout << endl << endl;
    
        quickSort(arr, 0, arr.size() - 1);
    
        for (auto& i : arr) {
            cout << i << ' ';
        }
    
        cout << endl << endl;
        system("pause");
        return 0;
    }
    

    image-20200522223306345

    总结

    • 快排是不稳定的排序算法

      • 33 33'排序后可能变成33' 33
    • 时间复杂度:

      • 平均:O(NlogN)O(Nlog_N)
      • 最差:O(N2)O(N^2),退化为冒泡排序
    • 空间复杂度:

      • 递归调用消耗栈空间
      • 最优:O(logN)O(log_N)
      • 最差:O(N)O(N),退化为冒泡排序

    如有错漏不实之处,欢迎补充纠正。

    展开全文
  • 算法】排序算法

    2018-03-03 10:08:30
    下面用例子对各个排序算法进行快速回顾,算法详细的流程往下看!原始序列: [49 38 65 97 76 13 27 49]1、交换排序——冒泡排序两两交换,最小冒泡到前面。一次冒泡过程:13 [49 38 65 97 76 27 49]最好情况:正序...


    下面用例子对各个排序算法进行快速回顾,算法详细的流程往下看!


    原始序列: [49 38 65 97 76 13 27 49]


    1、交换排序——冒泡排序

    两两交换,最小冒泡到前面。一次冒泡过程:

    13 [49 38 65 97 76 27 49]

    最好情况:正序;最坏情况,倒序;平均情况:乱序。

    最好=O(n),平均=最坏=O(n2)

    不稳定


    2、交换排序——快速排序

    以第一个元素为基准,一次排序将原始序列划分为小于第一个元素和大于第一个元素的两个部分:

    [27 38 13] 49 [76 97 65 49]

        快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

    最好=平均=O(nlogn );最坏=O(n2)

    不稳定


    3、选择排序——简单选择排序

    每次选出乱序中的最小值,与第一个乱序元素进行交换,让左侧有序。一次排序过程:

    13 [38 65 97 76 49 27 49]

    由于无论是平均情况还是最好最坏情况(即乱序,正序,倒序),选择排序每次都要从右边序列中遍历一遍,得到最值。并且在

    平均=最好=最坏=O(n2 )

    稳定


    4、选择排序——堆排序

     

     

    在建树过程和输出堆顶元素过程中,会打破稳定性。

    平均=最好=最坏=O(nlogn )

    不稳定


    5、插入排序——直接插入排序

        与简单选择排序类似,直接插入排序的有序序列也是逐渐往右递增。不同的是,简单选择排序的新增的数字是右边无序序列中最小的数字,该数字放在左边有序序列的最后面就可以了;而直接插入排序,是直接将无序序列的第一个数,插入左边有序序列中,需要找插入的位置。


    由于插入排序需要将乱序第一个元素与有序每一个元素进行比较,最好情况是有序数列,从后往前比,每次都排在有序数列的后面。

    如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    最好=O(n);平均=最坏=O(n^2 )

    稳定


    6、插入排序——希尔排序

    希尔排序时效分析很难。是一个不稳定的排序方法。

    不稳定


    7、归并排序

    不稳定

    8、桶排序

    例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。


    ================================详细讲解部分================================

    1、时间复杂度 


    (1)时间频度 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。 


    (2)时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。 
           在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。 按数量级递增排列,常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。 2、空间复杂度 与时间复杂度类似,空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作: S(n)=O(f(n)) 我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似,不再赘述。 


    (3)渐进时间复杂度评价算法时间性能   主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。


    2、空间复杂度

        类似于时间复杂度的讨论,一个算法的空间复杂度(Space Complexity)S(n)定义为该算法所耗费的存储空间,它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。 
        空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的,是通过参数表由调用函数传递而来的,它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比,要压缩这方面的存储空间,就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异,有的算法只需要占用少量的临时工作单元,而且不随问题规模的大小而改变,我们称这种算法是“就地/"进行的,是节省存储的算法,如这一节介绍过的几个算法都是如此;有的算法需要占用的临时工作单元数与解决问题的规模n有关,它随着n的增大而增大,当n较大时,将占用较多的存储单元,例如将在第九章介绍的快速排序和归并排序算法就属于这种情况。

        如当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为0(10g2n);当一个算法的空I司复杂度与n成线性比例关系时,可表示为0(n).若形参为数组,则只需要为它分配一个存储由实参传送来的一个地址指针的空间,即一个机器字长空间;若形参为引用方式,则也只需要为其分配存储一个地址的空间,用它来存储对应实参变量的地址,以便由系统自动引用实参变量。

     

    常用的内部排序方法有:交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、堆排序)、插入排序(直接插入排序、希尔排序)、归并排序、基数排序(一关键字、多关键字)。


    一、冒泡排序:

    1.基本思想:

    两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。

    2.排序过程:

    设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R,凡扫描到违反本原则的轻气泡,就使其向上"漂浮",如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止。

    【示例】:

    ______________________________

    49 | 13 13 13 13 13 13 13 | 

    38 49 27 27 27 27 27 27 |

    65 38 49 38 38 38 38 38 |

    97 65 38 49 49 49 49 49 |

    76 97 65 49 49 49 49 49 |

    13 76 97 65 65 65 65 65 |

    27 27 76 97 76 76 76 76 |

    49 49 49 76 97 97 97 97 |

    ______________________________|

    二、快速排序(Quick Sort)

        1.基本思想:

    在 当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X),用此基准将当前无序区划分为左右两个较小的无序区:R[1..I-1]和 R[I+1..H],且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准X则位于最终排序的位置上,即 R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H),当R[1..I-1]和R[I+1..H]均非空时,分别对它们进行上述的划分过 程,直至所有无序子区中的数据元素均已排序为止。

        2.排序过程:

        【示例】:

        一趟排序:

        初始关键字     [49 38 65 97 76 13 27 49]

        第一次交换后 [27 38 65 97 76 13 49 49]

        第二次交换后 [27 38 49 97 76 13 65 49]

        第三次交换后 [27 38 13 97 76 49 65 49]

        第四次交换后 [27 38 13 49 76 97 65 49]

        完成            [27 38 13 49 76 97 65 49]

       

        完整过程:

        初始关键字  [49 38 65 97 76 13 27 49]

        一趟排序    [27 38 13] 49 [76 97 65 49]

        二趟排序    [13] 27 [38] 49 [49 65]76 [97]

        三趟排序      13 27 38 49 49 [65]76 97

        完成           13 27 38 49 49 65 76 97


    三、简单选择排序

        1.基本思想:

    每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。

        2.排序过程:

    【示例】:

        初始关键字    [49 38 65 97 76 13 27 49]

        第一趟排序后 13 [38 65 97 76 49 27 49]

        第二趟排序后 13 27 [65 97 76 49 38 49]

        第三趟排序后 13 27 38 [97 76 49 65 49]

        第四趟排序后 13 27 38 49 [49 97 65 76]

        第五趟排序后 13 27 38 49 49 [97 97 76]

        第六趟排序后 13 27 38 49 49  76[76 97]

        第七趟排序后 13 27 38 49 49 76 76 [97]

        完成            13 27 38 49 49 76 76 97


    四、堆排序(Heap Sort)

        1.基本思想:

        堆排序是一树形选择排序,在排序过程中,将R[1..N]看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

        2.堆的定义:堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。

    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)


    初始时把要排序的n个数的序列看作是一顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。

    因此,实现堆排序需解决两个问题:

    1. 如何将n 个待排序的数建成堆;

    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。

    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:


    再讨论对n 个元素初始建堆的过程。

    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。

    2)筛选从第个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)

                                  

                                  

     

    五、直接插入排序(Insertion Sort)

    1. 基本思想:

    每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。

    2. 排序过程:

    过程:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    【示例】:

    [初始关键字] [49] 38 65 97 76 13 27 49

         J=2(38) [38 49] 65 97 76 13 27 49

         J=3(65) [38 49 65] 97 76 13 27 49

         J=4(97) [38 49 65 97] 76 13 27 49

         J=5(76) [38 49 65 76 97] 13 27 49

         J=6(13) [13 38 49 65 76 97] 27 49

         J=7(27) [13 27 38 49 65 76 97] 49

         J=8(49) [13 27 38 49 49 65 76 97]


    六、希尔排序

    1.排序思想:

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    2.排序过程:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。
    希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。


    七、归并排序

    基本思想:
    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
    归并排序示例:
     
    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

          1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
          2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
          3. //选取r[i]和r[j]较小的存入辅助数组rf
          4. 如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
          5. 否则,rf[k]=r[j]; j++; k++; 转⑵
          6. //将尚未处理完的子表中元素存入rf
          7. 如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
          8. 如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
          9. 合并结束。

    8. 桶排序/基数排序(Radix Sort)

    说基数排序之前,我们先说桶排序:

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
             简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

     例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

      对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

      O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

            前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

            1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

            2)其次待排序的元素都要在一定的范围内等等。

           桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。


    分配排序的基本思想:说白了就是进行多次的桶式排序。

    基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

    实例:

    扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    花色: 梅花< 方块< 红心< 黑心  
    面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

    若对扑克牌按花色、面值进行升序排序,得到如下序列:


    即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

    为得到排序结果,我们讨论两种排序方法。
    方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
    方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                                   

    其中k1 称为最主位关键码,kd 称为最次位关键码     。

     

    两种多关键码排序方法:

    多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

    最高位优先(Most Significant Digit first)法,简称MSD 法

    1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

    2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

    3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

    最低位优先(Least Significant Digit first)法,简称LSD 法

    1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

    2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。


    基于LSD方法的链式基数排序的基本思想

      “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

    基数排序:

    是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。



    参考文章:

    https://www.cnblogs.com/angelye/p/7508292.html

    展开全文
  • 挑战程序竞赛系列(49):4.2 推理与动态规划算法(2) 详细代码可以fork下Github上leetcode项目,不定期更新。 练习题如下: POJ 2068: Nim POJ 2068: Nim 团体尼姆赛:传统的尼姆游戏由两名玩家进行,在一堆石头...

    挑战程序竞赛系列(49):4.2 推理与动态规划算法(2)

    详细代码可以fork下Github上leetcode项目,不定期更新。

    练习题如下:

    POJ 2068: Nim

    团体尼姆赛:传统的尼姆游戏由两名玩家进行,在一堆石头中,双方轮流取走任意合法数量块石头,取走最后一块石头的玩家落败。多人尼姆游戏将参赛人数拓展至两个队伍,每支队伍有n名队员交错入座,单次分别能最多取走Mi块石头,取走S块石头中的最后一块的队伍失败,求第一支队伍是否有必胜策略?

    动态规划题,如果单纯的两个人轮流取,直接利用数学公式直接求出,但此题多轮多人且每人取的石头数也不同,这貌似只能动规了。

    dp[i][j][k] 第i支队伍第k个人,剩余k个石子时,能否赢得当前轮
    
    注意当k = 0,表明是必胜态,而当k = 1时,一定为必输态。

    代码如下:

    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.IOException;
    import java.io.InputStream;
    import java.io.InputStreamReader;
    import java.io.PrintWriter;
    import java.util.StringTokenizer;
    
    public class Main{
    
        String INPUT = "./data/judge/201709/P2068.txt";
    
        public static void main(String[] args) throws IOException {
            new Main().run();
        }
    
        static final int MAX_S = 1 << 13;
        boolean[][][] dp; //第k只队伍 第j个队员 剩余i个石头的状态
    
        void solve() {
            while (true) {
                int n = ni();
                if (n == 0) break;
                int s = ni();
    
                dp = new boolean[2][12][MAX_S + 16];
    
                int[] team = new int[2 * n];
                for (int i = 0; i < 2 * n; ++i) {
                    team[i] = ni();
                }
    
                for (int i = 0; i < 2 * n; ++i) {
                    dp[i & 1][i / 2 + 1][0] = true;
                    dp[i & 1][i / 2 + 1][1] = false; // 必输态
                }
    
                for (int i = 2; i <= s; ++i) {
                    for (int now = 0; now < 2 * n; ++now) {
                        int nxt = (now + 1) % (2 * n);
                        for (int j = team[now]; j >= 1; --j) {
                            if (i - j >= 0) {
                                dp[now & 1][now / 2 + 1][i] |= !dp[nxt & 1][nxt / 2 + 1][i - j];
                                if (dp[now & 1][now / 2 + 1][i]) break;
                            }
                        }
                    }
                }
    
                out.println(dp[0][1][s] ? "1" : "0");
            }
        }
    
        FastScanner in;
        PrintWriter out;
    
        void run() throws IOException {
            boolean oj;
            try {
                oj = ! System.getProperty("user.dir").equals("F:\\java_workspace\\leetcode");
            } catch (Exception e) {
                oj = System.getProperty("ONLINE_JUDGE") != null;
            }
    
            InputStream is = oj ? System.in : new FileInputStream(new File(INPUT));
            in = new FastScanner(is);
            out = new PrintWriter(System.out);
            long s = System.currentTimeMillis();
            solve();
            out.flush();
            if (!oj){
                System.out.println("[" + (System.currentTimeMillis() - s) + "ms]");
            }
        }
    
        public boolean more(){
            return in.hasNext();
        }
    
        public int ni(){
            return in.nextInt();
        }
    
        public long nl(){
            return in.nextLong();
        }
    
        public double nd(){
            return in.nextDouble();
        }
    
        public String ns(){
            return in.nextString();
        }
    
        public char nc(){
            return in.nextChar();
        }
    
        class FastScanner {
            BufferedReader br;
            StringTokenizer st;
            boolean hasNext;
    
            public FastScanner(InputStream is) throws IOException {
                br = new BufferedReader(new InputStreamReader(is));
                hasNext = true;
            }
    
            public String nextToken() {
                while (st == null || !st.hasMoreTokens()) {
                    try {
                        st = new StringTokenizer(br.readLine());
                    } catch (Exception e) {
                        hasNext = false;
                        return "##";
                    }
                }
                return st.nextToken();
            }
    
            String next = null;
            public boolean hasNext(){
                next = nextToken();
                return hasNext;
            }
    
            public int nextInt() {
                if (next == null){
                    hasNext();
                }
                String more = next;
                next = null;
                return Integer.parseInt(more);
            }
    
            public long nextLong() {
                if (next == null){
                    hasNext();
                }
                String more = next;
                next = null;
                return Long.parseLong(more);
            }
    
            public double nextDouble() {
                if (next == null){
                    hasNext();
                }
                String more = next;
                next = null;
                return Double.parseDouble(more);
            }
    
            public String nextString(){
                if (next == null){
                    hasNext();
                }
                String more = next;
                next = null;
                return more;
            }
    
            public char nextChar(){
                if (next == null){
                    hasNext();
                }
                String more = next;
                next = null;
                return more.charAt(0);
            }
        }
    }

    这里写图片描述

    展开全文
  • 1.3.1 从49到85 900 12 1.3.2 世界旅行商问题 15 1.3.3 《蒙娜丽莎》一笔画 17 1.4 本书路线一览 18 第2章 历史渊源 21 2.1 数学家出场之前 21 2.1.1 商人 21 2.1.2 律师 27 2.1.3 牧师 28 2.2 ...
  • 近年来,以深度学习为代表的核心算法突破,计算机计算能力的提升以及移动互联和云计算技术的发展,AI技术的发展开始切实影响到人们的生活。现阶段,人工智能技术已经运用在智能安防、智能交通、金融服务业、医疗行业...

空空如也

空空如也

1 2 3 4 5 ... 12
收藏数 231
精华内容 92
关键字:

最详细49算法