題目大意是求解快排最壞情況下的交換次數，我們知道，快速排序在最壞情況下會退化為冒泡排序，因此快排最壞情況下的交換次數也就是冒泡排序對應的交換次數。很容易想到這一題用冒泡排序，并記錄交換次數就行了。
這樣做看似可行，其實是行不通的，數據量是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://m.shnenglu.com/hoolee/archive/2012/07/18/184029.html
posted @
2012-07-18 17:46 小鼠標 閱讀(264) |
評論 (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 小鼠標 閱讀(919) |
評論 (0) |
編輯 收藏
摘要: 快速排序是運用了分治思想的排序方式，具有O(NlogN)的平均時間復雜度，極端情況下時間復雜度為O(N^2)，跟冒泡排序一樣，但是快排的實際效率遠比最壞情況好很多。它的關鍵部分是一輪選擇（由Partition()函數完成）……所謂線性時間就是在平均O(N)的時間內找出無序序列中第k大的元素。它是以Partition()函數的劃分為依據的……
閱讀全文
posted @
2012-07-17 16:46 小鼠標 閱讀(3696) |
評論 (1) |
編輯 收藏
摘要: 奇數個數尋找中位數，有O(N)復雜度的算法，這里采用的方式是先排序，然后找出中間那一個，等寫到快排時在寫線性時間的算法吧。以下采用的方式分別是冒泡排序和堆排序：
Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1#include<...
閱讀全文
posted @
2012-07-16 15:52 小鼠標 閱讀(569) |
評論 (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 小鼠標 閱讀(220) |
評論 (0) |
編輯 收藏
摘要: 堆排序是一種比較常用的排序方式，具有O(NlogN)的時間復雜度，它只需要一個記錄大小的空間，算法的核心是“篩選”。
堆的存儲方式是一維數組，因為它是一棵完全二叉樹，孩子與雙親下標有簡單直接的計算方式……
閱讀全文
posted @
2012-07-16 11:18 小鼠標 閱讀(1171) |
評論 (0) |
編輯 收藏
摘要: Java中的基本數據類型使用"=="可以判斷操作數是否相等，對于對象則判斷這兩個對象的內存地址是否相同。Java虛擬機為了提高字符串應用效率，提供了字符串池來保存字符串常量，str1創建字符串常量"abc"時，虛擬機會先檢測字符串池中是否包含該字符串……
閱讀全文
posted @
2012-06-05 21:43 小鼠標 閱讀(2638) |
評論 (3) |
編輯 收藏
摘要: http://poj.org/problem?id=2251一道三維的迷宮題，要求求出最短路徑。廣度優先搜索的框架是很清晰的，就是在code的時候一些細節注意不到，就只好調啊，調啊，就這樣兩個小時就過去了%>_<%說一下代碼思路吧：1.讀入數據2.預處理迷宮，主要是給迷宮周圍加一道墻，便于統一處理3.找到起點'S'，和終點'E'的坐標分別記錄在p0、p1中4.從起點開始進行廣搜，直到隊...
閱讀全文
posted @
2012-06-05 12:55 小鼠標 閱讀(230) |
評論 (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 小鼠標 閱讀(269) |
評論 (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 小鼠標 閱讀(217) |
評論 (0) |
編輯 收藏