• 问题
  • 输入
  • 输出
  • 约束
• 解决思路
• 程序代码

问题

输入

一个最多包含n个正整数的文件，每个数都小于n，其中n=107。如果在输入文件中有任何正数重复出现就是致命错误。没有其他数据与该正数相关联。

输出

按升序排列的输入正数的列表。

约束

最多有1MB的内存空间可用，有充足的磁盘存储空间可用。运行时间最多几分钟，运行时间为10秒就不需要进一步优化。

解决思路

应用位图或位向量表示集合。可用一个32位长的字符串来表示一个简单的非负整数，例如，可以用如下字符串表示集合{1,2,4,5,8}。

1

01101100100

32位字符串位表示：0 1 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
32位字符串位下标：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
数值的位都置为1，其他所有的位置为0。编程珠玑当中建议一个具有1000万个位的字符串来表示这个文件，那么这个文件的所占容量为10000000 bit= $10^7$bit，不到1MB的大小。
分三个阶段来编写程序。

• 第一阶段：将所有的位都置为0，从而将集合初始化为空。
• 第二阶段：将每个对应的位置都置为1。
• 第三阶段：检验每一位，如果该为为1，就输出对应的整数，有此产生有序的输出文件。（通过&运算来比较是否为1）

int数组的存储位置：位置=数据/32(采用位运算即右移5位)
int数组元素的位位置：位位置=数据%32(采用位运算即跟0X1F进行与操作)
int数组如下所示，int大小：32位，从0开始。数组中每一个元素就是一个int，所以有长度是32位。

• 问题
• 解决思路
  • 方法1
  • 方法2
• 程序代码
  • 方法2的代码

问题

请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8,i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？

解决思路

方法1

将向量x中的前i个元素复制到一个临时数组中，接着将余下的n-i个元素左移i个位置，然后再将前i个元素从临时数组中复制回x中的后面位置。
该方案使用i个额外的位置，如i足够大，过于浪费空间。

方法2

将这个问题看作是把数组ab转换成数组ba吧，但同时也假定我们具有在数组中转置指定部分元素的函数。我们先从ab开始，转置a得到$a^rb$，再转置b得到$a^rb^r$，然后再转置整个$a^rb^r$得到$(a^rb^r)^r$，实际上就是ba。

• reverse(0, i-1)
• reverse(i, n-1)
• reverse(0, n-1)

该转置代码在时间和空间上都很有效，并且是这么简短和简单，想出错都很难。

• 排序
  • 稳定性的定义
  • 稳定性的意义
  • 稳定排序
  • 不稳定排序
• 直接插入排序
  • 基本思想
  • 时间复杂度
  • 空间复杂度
  • 稳定性
    • Java
    • C++
• 希尔排序
  • 类型
  • 基本思想
  • 时间复杂度
  • 空间复杂度
  • 稳定性
  • 规模大小
    • java
    • C++
• 简单选择排序
  • 基本思想
  • 时间复杂度
  • 空间复杂度
  • 稳定性
    • Java
      • 例1
      • 例2
      • 例3
• 堆排序
  • 基本思想
    • 构建堆
    • 排序
  • 时间复杂度
  • 空间复杂度
  • 稳定性
    • Java
      • 例1
      • 例2
• 冒泡排序
  • 基本思想
  • 时间复杂度
  • 空间复杂度
  • 稳定性
    • Java
      • 例1
      • 例2
    • C++
• 快速排序
  • 基本思想
    • 步骤
  • 时间复杂度
  • 空间复杂度
  • 稳定性
  • 规模大小
  • 优化
    • Java
      • 例1
      • 例2
    • C++
• 两路合并排序
  • 基本思想
  • 时间复杂度
  • 空间复杂度
  • 稳定性
    • Java
      • 例1
      • 例2
    • C++
• 基数排序
  • 基本思想
  • 时间复杂度
  • 空间复杂度
  • 稳定排序
    • Java
      • 例1
      • 例2

排序

内部排序：待排序的元素总数相对于内存而言较小，整个排序过程可以在内存中进行。
外部排序：待排序的元素总数较多，不能全部放入内存，排序过程中需要访问外存。
内部排序算法有很多，各有其优缺点和适合的场合。
排序的稳定性：如果在排序的序列中，存在前后相同的两个元素的话，排序前和排序后他们的相对位置不发生变化。

稳定性的定义

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，$r_i$=$r_j$，且$r_i$在$r_j$之前，而在排序后的序列中，$r_i$仍在$r_j$之前，则称这种排序算法是稳定的；否则称为不稳定的。
对于不稳定的排序算法，只要举出一个实例，即可说明它的不稳定性；而对于稳定的排序算法，必须对算法进行分析从而得到稳定的特性。需要注意的是，排序算法是否为稳定的是由具体算法决定的，不稳定的算法在某种条件下可以变为稳定的算法，而稳定的算法在某种条件下也可以变为不稳定的算法。

稳定性的意义

• 如果只是简单的进行数字的排序，那么稳定性将毫无意义。
• 如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义。
• 如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
• 除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。

  稳定排序

  基数排序、冒泡排序、直接插入排序、两两插入排序、归并排序。

  不稳定排序

  堆排序、快速排序、希尔排序、简单选择排序。

  直接插入排序

  基本思想

  将数组中第1个元素作为有序序列，然后将剩下的n-1数组元素，按照顺序插入第1个元素的序列中。
  插入第1个元素后，第1个元素的序列保持有序。
  将待插入有序序列的元素存入临时变量temp中，在有序序列从后往前比较大小，查找插入的位置。
  当temp小于有序序列的元素时，该有序序列元素往后移1位，temp元素继续比较。
  直到有序序列中有元素比temp小、或者到有序序列第1个元素时结束，这时将temp插入有序序列元素的位置。
  插入排序会优于选择排序，理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势，有效地减少一些比较的次数，当然这种优势得看数组的初始顺序如何，最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ，这种极端情况下，插入排序的效率甚至比选择排序更差。

  时间复杂度

  最好情况比较次数是O(n)(有序)，最坏情况比较次数O(n*n)无序。

  空间复杂度

  O(1)每次都交换一个元素

  稳定性

  插入排序是稳定排序，如果碰到相等的元素，就把新元素插入相等元素的后面，即他们原来的顺序没有变化。（插入排序在全部元素插入完毕之前，都不能确定最终一个元素的位置）temp < A[j - 1]，如果改成temp <= A[j - 1]，则是不稳定排序。

  Java