题目大意是求解快排最坏情况下的交换次数，我们知道，快速排序在最坏情况下会退化为冒泡排序，因此快排最坏情况下的交换次数也就是冒泡排序对应的交换次数。很容易想到这一题用冒泡排序，并记录交换次数就行了。
这样做看似可行，其实是行不通的，数据量是500000，由于冒泡排序的时间复杂度是O(N^2)，所以问题的规模就是500000^2=2.5 * E11，一般我们认为计算机每秒的计算量是E9，因此用冒泡排序是行不通的。
联想有关排序的算法，我们希望这一题的时间复杂度能够降为O(NlogN)，快排、堆排序、合并排序满足这样的要求，可是前两种排序方式的交换方式毫无规律可循，只剩下归并排序。
我们来看归并排序，它的核心是归并（由Merge()函数实现），就是将两个有序序列合并为一个有序序列。由冒泡排序我们知道，交换的总次数就是初始序列中每个元素交换次数的总和，每个元素的交换次数等于该元素后面比自己小的元素的个数（因为最终比自己小的元素都在自己前面）。
下图是一次Merge()过程：
可以看出，元素“1”没有移动，元素“4”向后移动了1位，元素“10”向后移动了3位，所以本次合并共移动了4次。统计合并排序过程中所有的移动次数即可。
本题代码如下
#include<stdio.h>
#include<stdlib.h>
#define LEN 500010
long long count;
void Copy(int *a, int *b, int f, int r)
{
for(int i = 0; i <= r - f; i++)
a[i + f] = b[i];
}
void Merge(int *a, int f, int m, int r)
{
int *b = (int *)malloc(sizeof(int) * ( r - f + 1));
int i = f;
int j = m + 1;
int k = 0;
while(i <= m && j <= r)
{
if(a[i] > a[j])
b[k++] = a[j++];
else
{
b[k++] = a[i++];
if(k + f > i)
count += k + f - i;
}
}
while(i <= m)
{
b[k++] = a[i++];
if(k + f > i)
count += k + f - i;
}
while(j <= r)
b[k++] = a[j++];
Copy(a, b, f, r);
free(b);
}
void MergeSort(int *a, int f, int r)
{
if(f < r)
{
int i = (r + f) / 2;
MergeSort(a, f, i);//ÅÅÐò×ó°ë²¿·Ö
MergeSort(a, i + 1, r);//ÅÅÐòÓҰ벿·Ö
Merge(a, f, i, r);//ºÏ²¢
}
}
int main()
{
int i, j;
int N;
int a[LEN];
scanf("%d", &N);
while(N != 0)
{
for(i = 1; i <= N; i++)
scanf("%d", &a[i]);
count = 0;
MergeSort(a, 1, N);
printf("%lld\n", count);
scanf("%d", &N);
}
//system("pause");
}
有关合并排序请参阅：
http://www.cppblog.com/hoolee/archive/2012/07/18/184029.html
posted @
2012-07-18 17:46 小鼠标 阅读(243) |
评论 (0) |
编辑 收藏是利用了分治思想的排序方式，具有O(NlogN)的时间复杂度，与快速排序、堆排序相比，它需要N的辅助空间。它的核心部分是将两个有序序列合并（由Merge()函数实现）。
合并排序的基本思想是：单个元素是有序的，两个较小的有序序列可被合并为一个较大的有序序列。
算法描述如下：
void MergeSort(int *a, int f, int r)
{
if(f < r)
{
int i = (r + f) / 2;
MergeSort(a, f, i);//排序左半部分
MergeSort(a, i + 1, r);//排序右半部分
Merge(a, f, i, r);//合并
}
}
void Merge(int *a, int f, int m, int r)
{
int *b = (int *)malloc(sizeof(int) * ( r - f + 1));
int i = f;
int j = m + 1;
int k = 0;
while(i <= m && j <= r)
{
if(a[i] > a[j])
b[k++] = a[j++];
else
b[k++] = a[i++];
}
while(i <= m)
b[k++] = a[i++];
while(j <= r)
b[k++] = a[j++];
Copy(a, b, f, r);
free(b);
}
void Copy(int *a, int *b, int f, int r)
{
for(int i = 0; i <= r - f; i++)
a[i + f] = b[i];
}，时间复杂度O(N^2)，基本操作是将一个元素插入到有序序列中。当待排序元素个数为n时，因为第一个元素是有序的，因此只需经过n - 1次插入，就能完成排序。
单次插入的过程为：
1.找到要插入元素在已排序部分中的位置j。
2.将有序序列中j后面的所有元素向后移动一位，为待插入元素空出位置。
3.将待排序元素插入j位置，保持序列有序。
算法描述为：
void InsertSort(int *a, int n)
{//数组下标从0开始，0号元素是有序的
int i, j, k;
for(i = 1; i < n; i++)
{
j = -1;
int t = a[i];
while(a[++j] < t);//找到要插入的位置
for(k = i; k > j; k--)//向后移动元素
a[k] = a[k - 1];
a[j] = t;//插入
}
}posted @
2012-07-18 11:12 小鼠标 阅读(894) |
评论 (0) |
编辑 收藏
摘要: 快速排序是运用了分治思想的排序方式，具有O(NlogN)的平均时间复杂度，极端情况下时间复杂度为O(N^2)，跟冒泡排序一样，但是快排的实际效率远比最坏情况好很多。它的关键部分是一轮选择（由Partition()函数完成）……所谓线性时间就是在平均O(N)的时间内找出无序序列中第k大的元素。它是以Partition()函数的划分为依据的……
阅读全文
posted @
2012-07-17 16:46 小鼠标 阅读(3570) |
评论 (1) |
编辑 收藏
摘要: 奇数个数寻找中位数，有O(N)复杂度的算法，这里采用的方式是先排序，然后找出中间那一个，等写到快排时在写线性时间的算法吧。以下采用的方式分别是冒泡排序和堆排序：
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include<...
阅读全文
posted @
2012-07-16 15:52 小鼠标 阅读(538) |
评论 (0) |
编辑 收藏冒泡排序是最基本的排序方式，很简单，容易理解，但算法的时间复杂度为O(N^2)，适合于基数不大的排序。
下面的代码中bsort函数完成冒泡排序，数组下标从1开始。
1#include<stdio.h>
2#include<stdlib.h>
3#define LEN
4void swap(int *a, int *b)
5{
6 int t = *a;
7 *a = *b;
8 *b = t;
9}
10void bsort(int *a, int n)
11{
12 int i, j;
13 for(j = n; j > 1; j--)
14 for(i = 1; i < j; i++)
15 {
16 if(a[i] > a[i + 1])
17 swap(&a[i], &a[i + 1]);
18 }
19}
20int main()
21{
22 int i, j;
23 int a[LEN] = {0, 1, 5, 95, 7, 3, 8, 0, 90, 25, 13};
24 int n = 10;
25 bsort(a, n);
26
27 for(i = 1; i <= n; i++)
28 printf("%3d", a[i]);
29 putchar(10);
30 system("pause");
31}
32
posted @
2012-07-16 15:22 小鼠标 阅读(186) |
评论 (0) |
编辑 收藏
摘要: 堆排序是一种比较常用的排序方式，具有O(NlogN)的时间复杂度，它只需要一个记录大小的空间，算法的核心是“筛选”。
堆的存储方式是一维数组，因为它是一棵完全二叉树，孩子与双亲下标有简单直接的计算方式……
阅读全文
posted @
2012-07-16 11:18 小鼠标 阅读(1150) |
评论 (0) |
编辑 收藏
摘要: Java中的基本数据类型使用"=="可以判断操作数是否相等，对于对象则判断这两个对象的内存地址是否相同。Java虚拟机为了提高字符串应用效率，提供了字符串池来保存字符串常量，str1创建字符串常量"abc"时，虚拟机会先检测字符串池中是否包含该字符串……
阅读全文
posted @
2012-06-05 21:43 小鼠标 阅读(2559) |
评论 (3) |
编辑 收藏
摘要: http://poj.org/problem?id=2251一道三维的迷宫题，要求求出最短路径。广度优先搜索的框架是很清晰的，就是在code的时候一些细节注意不到，就只好调啊，调啊，就这样两个小时就过去了%>_<%说一下代码思路吧：1.读入数据2.预处理迷宫，主要是给迷宫周围加一道墙，便于统一处理3.找到起点'S'，和终点'E'的坐标分别记录在p0、p1中4.从起点开始进行广搜，直到队...
阅读全文
posted @
2012-06-05 12:55 小鼠标 阅读(216) |
评论 (0) |
编辑 收藏
与排列相比，组合是不区分元素顺序的，为了消去相同元素不同顺序的干扰项，在
选取每一个组合项的元素时使该元素的位序大于已选好元素的位序即可。如果题目要求所有组合项按升序输出，只需事先将所有元素排序即可。
#include<stdio.h>
#include<stdlib.h>
#define LENL 6
#define LEN 15
int K;
int S[LEN];
int S1[LEN];
int cmp(const void *a, const void *b)
{
int *a0 = (int*)a;
int *b0 = (int*)b;
return *a0 - *b0;
}
void Arrange(int now, int last)
{
int i, j;
if(now == LENL)
{
for(i = 0; i < LENL - 1; i++)
printf("%d ", S1[i]);
printf("%d\n", S1[i]);
}
else
for(i = last; now + K - i >= LENL; i++)
{
S1[now] = S[i];
Arrange(now + 1, i + 1);
}
}
int main()
{
int i, j;
scanf("%d", &K);
int gard = 0;
while(K != 0)
{
for(i = 0; i < K; i++)
scanf("%d", &S[i]);
qsort(S, K, sizeof(int), cmp);
if(gard != 0)
putchar(10);
Arrange(0, 0);
gard++;
scanf("%d", &K);
}
}
posted @
2012-05-27 10:03 小鼠标 阅读(246) |
评论 (0) |
编辑 收藏这是省赛的第二题。
题意：把一个整数拆分成若干份，每一份相加的和为这个数，求这些数最大的积。
如果能够分析出应把原数拆为3+3+3+3+3……，接下来需要的就是大数运算了（悲剧的是我们当时没有分析出来):）。java中有BigInteger类来处理里大整数，比用C语言模拟大数运算方便的多。
这是我的第一道java大数题，感觉写的还有待改进，用的不熟练。
import java.util.*;
import java.math.*;
public class Main
{
public static void main(String[] args)
{
int N;
int Ti;
Scanner s = new Scanner(System.in);
N = s.nextInt();
while(N != 0)
{
N--;
BigInteger big = new BigInteger("0");
BigInteger base = new BigInteger("3");
BigInteger bt4 = new BigInteger("4");
BigInteger bt2 = new BigInteger("2");
Ti = s.nextInt();
if(Ti % 3 == 0)
{
big = base.pow(Ti / 3);
System.out.println(big);
}
else if(Ti % 3 == 1)
{
big = base.pow(Ti / 3 - 1);
big = big.multiply(bt4);
System.out.println(big);
}
else
{
big = base.pow(Ti / 3);
big = big.multiply(bt2);
System.out.println(big);
}
}
}
}posted @
2012-05-24 00:13 小鼠标 阅读(202) |
评论 (0) |
编辑 收藏