算法入门第一篇
1、给定一组“无序”记录序列｛25, 30, 11, 7, 22, 16, 18, 33, 40, 55｝，采用冒泡排序、堆排序、直接选择排序以及直接插入排序方法，将该序列排成非递减序列，完成以下问题：
1）写出冒泡排序、堆排序、直接选择排序和直接插入排序方法的Java实现代码。
2）采用上述4种方法进行排序时，都要执行的两种基本操作是什么？
3）写出冒泡排序第二趟排序后的结果。
4)画出采用堆排序方法第一次抽取堆顶元素后得到的最小堆。
5）采用直接选择法排序时，第5次交换和选择后，未排序记录是什么？
6）采用直接插入法排序把第6个记录16插入有序表时，为寻找插入位置，需要比较多少次？
7）试比较上述4种排序算法的性能（时间复杂度）。
2、问题提出：公元前5世纪末，中国古代数学家张丘建在他的《算经》中提出了著名的 “百钱买百鸡问题”：鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？即一百个铜钱买了一百只鸡，其中公鸡一只5钱、母鸡一只3钱，雏鸡一钱3只，问一百只鸡中公鸡、母鸡、雏鸡各多少? 算法的伪代码如下：
for x = 0 to 100
for y = 0 to 100
for z = 0 to 100
if (x+y+z=100) and (5*x + 3*y + z/3 = 100) then
System.out.println(" "+x+" "+y+" "+z)
end if
实验要求：对上述算法做出改进以提高算法的效率，要求将算法的时间复杂性由Ο(n3)降为 Ο(n2)，并将改进的算法编程实现。
3、硬件厂商XYZ公司宣称他们研制的微处理器的运行速度是其竞争对手ABC公司同类产品的1000倍。对于计算复杂性分别为,,的各类算法，若用ABC公司的计算机能在1小时内解决输入规模为
的问题，则用XYZ公司的计算机在1小时内能解决多大输入规模的问题？
4、假设某算法在输入规模为n时的计算时间为。在某台计算机上，于t秒内实现并完成该算法。现有另一台计算机，其运行速度为第一台的128倍，那么在这台新机器上用同一算法在t秒内能解决多大输入规模的问题?
1)
int num[] = new int[] { 25, 30, 11, 7, 22, 16, 18, 33, 40, 55 };
int len = num.length;
// 冒泡排序
public void bubbleSort() {
for (int i = 1; i < len; i++) {// n-1趟
int temp;
for (int j = 0; j < len - i; j++) {
if (num[j] > num[j + 1]) {
temp = num[j];
num[j] = num[j + 1];
num[j + 1] = temp;
}
}
}
}
// 堆排序
int leng = num.length;
List<Object> list = new ArrayList<Object>();
public void heapSort() {
for(int j = 0; j < leng; j++) {
for (int i = len / 2 - 1 ; i >= 0; i--) {// 创建堆
siftSmall(i, len);
}
list.add(num[0]);
num = remove(num,0);
len--;
}
for (Object n : list) {
System.out.print(n + " ");
}
}
private static int[] remove(int[] arr, int num) {
int[] tmp = new int[arr.length - 1];
int idx = 0;
boolean hasRemove = false;
for (int i = 0; i < arr.length; i++) {
if (!hasRemove && i == num) {
hasRemove = true;
continue;
}
tmp[idx++] = arr[i];
}
return tmp;
}
// 创建最小堆
public void siftSmall(int low, int high) {
int i = low;// 子树的根结点
int j = 2 * i + 1; // j为i结点的左孩子
int temp = num[i];
while (j < high) { // 沿着较小值孩子结点向下筛选
if (j < high - 1 && num[j] > num[j + 1]) {
j++;// 记录比较，j为左右孩子的较小者
}
if (temp > num[j]) {// 若父结点较大
num[i] = num[j];// 孩子结点中较小者上移
i = j;
j = 2 * i + 1;
} else {
j = high + 1;
}
}
num[i] = temp;
}
// 直接选择排序
public void selectSort() {
int temp;
for (int i = 0; i < len; i++) {// n-1趟
int min = i;
for (int j = i + 1; j < len; j++) {
if (num[j] < num[min]) {
min = j;
}
}
if (min != i) {
temp = num[i];
num[i] = num[min];
num[min] = temp;
}
}
}
// 直接插入排序
public void insertSort() {// 将比较后较大数放在后一位
for (int i = 1; i < len; i++) {
// 准备插入的数
int temp = num[i];
int j = i - 1;
for (; j >= 0 && temp < num[j]; j--) {
num[j + 1] = num[j];
}
num[j + 1] = temp;// 将数组后一位数赋值，插入排序
}
}
2)比较数值大小、元素交换
3) 11 25 30 7 22 16 18 33 40 55
4)
5)16、18、33、40、55
6) 3次
7)冒泡排序O(n^2)、堆排序O(nlog2n)、直接选择排序O(n^2)、直接插入排序O(n^2)
2.
public void test() {
for (int x = 0; x <= 20; x++) {
for (int y = 0; y <= 33; y++) {
if (5 * x + 3 * y + (100 - x - y) / 3 == 100 && (100 - x - y) % 3 == 0) {
System.out.println(x + " " + y + " " + (100 - x - y) + " ");
}
}
}
}
实现代码运行效果如下图
3.
时间复杂度为n时，输入规模1000n
时间复杂度为时，输入规模 ²√1000 ≈31.623
时间复杂度为时，输入规模10n
4.
某台机器t秒内完成算法的计算时间
新机器t秒内完成算法的计算时间=128*3*2^n=2^7*3*2^n=3*2^(n+7)
T=T(n)=3*2^n
n=log2(T/3)
设新机器输入规模为n1,则：
n1=log2(3*2^(n+7)/3)=n+7