点点滴滴

到底ddddd

评论

13 楼 wo327808864 2011-03-31  

改进后的快速排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;


public class ImprovedQuickSort implements SortUtil.Sort {

    private static int MAX_STACK_SIZE=4096;
    private static int THRESHOLD=10;
    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int[] stack=new int[MAX_STACK_SIZE];
        
        int top=-1;
        int pivot;
        int pivotIndex,l,r;
       
        stack[++top]=0;
        stack[++top]=data.length-1;
       
        while(top>0){
            int j=stack[top--];
            int i=stack[top--];
           
            pivotIndex=(i+j)/2;
            pivot=data[pivotIndex];
           
            SortUtil.swap(data,pivotIndex,j);
           
            //partition
            l=i-1;
            r=j;
            do{
                while(data[++l]<pivot);
                while((r!=0)&&(data[--r]>pivot));
                SortUtil.swap(data,l,r);
            }
            while(l<r);
            SortUtil.swap(data,l,r);
            SortUtil.swap(data,l,j);
           
            if((l-i)>THRESHOLD){
                stack[++top]=i;
                stack[++top]=l-1;
            }
            if((j-l)>THRESHOLD){
                stack[++top]=l+1;
                stack[++top]=j;
            }
           
        }
        //new InsertSort().sort(data);
        insertSort(data);
    }
    /**
     * @param data
     */
    private void insertSort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }      
    }

}

12 楼 wo327808864 2011-03-31  

快速排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;


public class QuickSort implements SortUtil.Sort{

    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        quickSort(data,0,data.length-1);       
    }
    private void quickSort(int[] data,int i,int j){
        int pivotIndex=(i+j)/2;
        //swap
        SortUtil.swap(data,pivotIndex,j);
        
        int k=partition(data,i-1,j,data[j]);
        SortUtil.swap(data,k,j);
        if((k-i)>1) quickSort(data,i,k-1);
        if((j-k)>1) quickSort(data,k+1,j);
        
    }
    /**
     * @param data
     * @param i
     * @param j
     * @return
     */
    private int partition(int[] data, int l, int r,int pivot) {
        do{
           while(data[++l]<pivot);
           while((r!=0)&&data[--r]>pivot);
           SortUtil.swap(data,l,r);
        }
        while(l<r);
        SortUtil.swap(data,l,r);       
        return l;
    }

}

11 楼 wo327808864 2011-03-31  

冒泡排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;


public class BubbleSort implements SortUtil.Sort{

    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for(int i=0;i<data.length;i++){
            for(int j=data.length-1;j>i;j--){
                if(data[j]<data[j-1]){
                    SortUtil.swap(data,j,j-1);
                }
            }
        }
    }

}

选择排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;


public class SelectionSort implements SortUtil.Sort {

    /*
     * (non-Javadoc)
     *
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for (int i = 0; i < data.length; i++) {
            int lowIndex = i;
            for (int j = data.length - 1; j > i; j--) {
                if (data[j] < data[lowIndex]) {
                    lowIndex = j;
                }
            }
            SortUtil.swap(data,i,lowIndex);
        }
    }

}

10 楼 wo327808864 2011-03-31  

用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。
插入排序：

package org.rut.util.algorithm.support;

import org.rut.util.algorithm.SortUtil;

public class InsertSort implements SortUtil.Sort{

    /* (non-Javadoc)
     * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
     */
    public void sort(int[] data) {
        int temp;
        for(int i=1;i<data.length;i++){
            for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
                SortUtil.swap(data,j,j-1);
            }
        }       
    }
}

9 楼 wo327808864 2011-03-31  

1.快速排序：
#include <iostream.h>

void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
j--;
if(i<=j)//找到了一对值
{
//交换
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）

//当左边部分有值(left<j)，递归左半边
if(left<j)
run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}

void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

    这里我没有给出行为的分析，因为这个很简单，我们直接来分析算法：首先我们考虑最理想的情况：
1.数组的大小是2的幂，这样分下去始终可以被2整除。假设为2的k次方，即k=log2(n)。
2.每次我们选择的值刚好是中间值，这样，数组才可以被等分。
第一层递归，循环n次，第二层循环2*(n/2)......所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n所以算法复杂度为O(log2(n)*n)其他的情况只会比这种情况差，最差的情况是每次选择到的middle都是最小值或最大值，那么他将变成交换法（由于使用了递归，情况更糟）。但是你认为这种情况发生的几率有多大？你完全不必担心这个问题。实践证明，大多数的情况，快速排序总是最好的。如果你担心这个问题，你可以使用堆排序，这是一种稳定的O(log2(n)*n)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。

8 楼 wo327808864 2011-03-31  

4.插入法：
    插入法较为复杂，它的基本工作原理是抽出牌，在前面的牌中寻找相应的位置插入，然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
iTemp = pData[i];
iPos = i-1;
while((iPos>=0) && (iTemp<pData[iPos]))
{
pData[iPos+1] = pData[iPos];
iPos--;
}
pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮：9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮：8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数：6次
交换次数：3次

其他：
第一轮：8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮：8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数：4次
交换次数：2次

    上面结尾的行为分析事实上造成了一种假象，让我们认为这种算法是简单算法中最好的，其实不是，因为其循环次数虽然并不固定，我们仍可以使用O方法。从上面的结果可以看出，循环的次数f(n)<= 1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)（这里说明一下，其实如果不是为了展示这些简单排序的不同，交换次数仍然可以这样推导）。现在看交换，从外观上看，交换次数是O(n)（推导类似选择法），但我们每次要进行与内层循环相同次数的‘='操作。正常的一次交换我们需要三次‘=' 而这里显然多了一些，所以我们浪费了时间。

    最终，我个人认为，在简单排序算法中，选择法是最好的。

7 楼 wo327808864 2011-03-31  

3.选择法：
    现在我们终于可以看到一点希望：选择法，这种方法提高了一点性能（某些情况下）这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从剩下的部分中 选择最小的与第二个交换，这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i<Count-1;i++)
{
iTemp = pData[i];
iPos = i;
for(int j=i+1;j<Count;j++)
{ a[j];
iPos = j;
if(pData[j]<iTemp)
{
iTemp = pDat
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}

}

void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮：7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮：7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数：6次
交换次数：2次

其他：
第一轮：8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮：7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮：7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数：6次
交换次数：3次
    遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。我们来看他的交换。由于每次外层循环只产生一次交换（只有一个最小值）。所以f(n)<=n所以我们有f(n)=O(n)。所以，在数据较乱的时候，可以减少一定的交换次数。

6 楼 wo327808864 2011-03-31  

2.交换法：
   交换法的程序最清晰简单，每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
for(int j=i+1;j<Count;j++)
{
if(pData[j]<pData[i])
{
iTemp = pData[i];
pData[i] = pData[j];
pData[j] = iTemp;
}
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮：10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次

其他：
第一轮：8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮：7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次


    从运行的表格来看，交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样也是1/2*(n-1)*n，所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况，所以只能直接告诉大家他们在交换上面也是一样的糟糕（在某些情况下稍好，在某些情况下稍差）。

5 楼 wo327808864 2011-03-31  

1.冒泡法：
    这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include <iostream.h>

void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情况)
第一轮：10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮：7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：6次

其他：
第一轮：8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮：7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮：7,8,10,9->7,8,9,10(交换1次)
循环次数：6次
交换次数：3次

    上面我们给出了程序段，现在我们分析它：这里，影响我们算法性能的主要部分是循环和交换，显然，次数越多，性能就越差。从上面的程序我们可以看出循环的次数是固定的，为1+2+...+n-1。写成公式就是1/2*(n-1)*n。现在注意，我们给出O方法的定义：
    若存在一常量K和起点n0，使当n>=n0时，有f(n)<=K*g(n),则f(n) = O(g(n))。
现在我们来看1/2*(n-1)*n，当K=1/2，n0=1，g(n)=n*n时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。再看交换。从程序后面所跟的表可以看到，两种情况的循环相同，交换不同。其实交换本身同数据源的有序程度有极大的关系，当数据处于倒序的情况时，交换次数同循环一样（每次循环判断都会交换），复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的原因，我们通常都是通过循环次数来对比算法。

4 楼 wo327808864 2011-03-29  

　　　　如果我总缠着你，请不要说我不乖！请不要对我生气！因为我真的很珍惜和你的每分每秒！哪怕明明相隔两地`哪怕只是在电话中相聚！因为在乎每一次小小意义上的分离！
　　如果我不会总缠着你，请不要以为我舍得和你说再见了！你不懂我那一瞬间的失落，是多么想伸出手去抓住你！你要明白正是为了爱，才悄悄的收起对你的依赖！
　　也许有一天我们都会埋怨！
也许有一天我们都会犯错！
　　也许有一天我们都会忽视今天的诺言！
　　也许有一天我们也会吵架！
　　……
　　所以我们来做个约定好吗？
　　约好即使吵架也不可以不接听彼此的电话！
　　约好即使吵架也不可以不好好照顾自己！
　　约好即使吵架也不可以轻易说分手！
　　约好即使吵架也不可以伤害自己！
　　约好即使吵架也不可以错过了……
　　约好，吵架的时候告诉自己：
　　错误是短暂的，错过却是永远遗憾的……
　　爱情`有时候很脆弱！
　　脆弱到容不下一点点沙！
　　爱情`有时候很顽强！
　　顽强到什么也分不开相爱的人！
　　如果有一天，我们不再任性的不理会一切！
　　如果有一天，我们不再要求时时都粘在一起！
　　如果有一天，我们不再傻傻的看着对方微笑！
　　如果有一天，我们不再不理会柴米油盐！
　　如果有一天，我们不再是任性的两个小孩！
　　如果有一天，我们习惯了彼此埋怨……
　　请不要说“分手吧，祝你快乐！”
　　因为这一天更应该说“我们结婚吧！让我照顾你一辈子！”

3 楼 wo327808864 2011-03-22  

女人好像都不喜欢男人打游戏，我感觉其实真还好，
玩游戏比出去玩强多了，得从自身也找找原因，为什么不喜欢他玩？是因为玩起来没时间陪自己了？
还是自己无聊，看到他玩的爽，自己没人陪就更恼火？等等，
建议LZ可以自己也找点事情做做，充实一下，强行不让玩这个不推荐，任何人都有反感情绪
你自己充实了就好了，游戏玩玩也就没意思了，就那一阵，比如新开资料片了，更新牛X装备了等等，总是会腻的，
腻了自然就好了，
我一哥们现在天天和他老婆吵架，就为了打游戏这事，相当的郁闷，
保证书什么的，真犯不上，两个人沟通好了，该怎么样就怎么样了

2 楼 wo327808864 2011-03-22  

没结婚前是经过长期潜伏终于找机会把老婆勾引进WOW了，后来她比我玩的还疯，为RAID为装备哭了好多次，不过最大的好处就是自从她玩WOW以后我游戏里就完全变大款了，草啊矿啊从来都是她去拼命刷，我教她开个头就可以了^_^。印象最深的就是以前开荒需要火抗药的时候虽然我是炼金但买不起火抗药配方，正在纠结的时候被老婆果断鄙视了，刷了一个通宵的钱AH拍了个配方给我，然后我们就改卖药水赚钱了@_@。



虽然现在她也很想重新玩，但为了宝宝和将来，已经改成不玩，然后我少玩，她帮我冲卡了=。=



话说，正道就是先陪他玩，先获得他的认同而不是逆反，然后就慢慢开始限制，不玩是不可能的也不安全，毕竟玩游戏是比较安全且经济的娱乐，比泡吧唱K打牌强多了。

你自己也要把持住啊，当年我老婆玩游戏那架势是把我吓到了- -b

1 楼 wo327808864 2011-03-22  

自我剖析一下,我如何被老婆拖离游戏的把.

主要阶段: P1疯玩->P2多玩->P3少玩->P4不玩(要到P4比较难)

P1:疯玩的时候,俺还是单身,略过不表

P2,P3通用方法

我老婆制定了一系列原则:(写保证书,掐网线这种方法不可取,只会搞的越来越僵),要来消耗掉我的时间

1. 吃饭完才可以玩(身体是革命的本钱,不管是工作还是干活),吃完大概19:00了

2. 所有分配给我的粗重家务活,必须做完,而且饭后必须陪她散步完才能玩(除非她不想散步,外面下雨等)

   粗重活包括:晾衣服,倒掉当日的厨房垃圾,饭后刷碗筷,刷马桶

   这些弄完大概20:00了

3. 散步完回来必须洗澡才可以玩,也可以晚点洗,但是如果发现不洗澡,第二天就不能玩

   这些弄完大概21:00了

4. 工作日晚上,不得超过12点,否则影响第二天上班的精神.

5. 周末必须有一天是family day,完全属于老婆的,包括白天和晚上



奖励原则:

1. 如果一周工作日, 每天都和老婆同时觉觉, 则周五,周六,周日晚上奖励玩到最多凌晨1点

2. 如果一周内连续三天不玩, 则奖励剩下的两个晚上可以玩到最多凌晨1点

3. 如果一周内五天不玩, 则奖励周五或者周六的晚上可以通宵(第二天不上班的才行)

4. 加工资额度超过2k以上的,当月奖励一天游戏时间,哪一天可协商



惩罚原则:

1. 不吃饭就玩,家务活没干完就玩的,不陪老婆散步,当天不洗澡被发现的,第二天不准玩游戏(除非老婆特批)

2. family day除了公事之外,不陪好好老婆的, 直接次周不能玩游戏



这样最后的结果就是:

我除了周五可以和大家打打活动,每天就只能21:00上线玩玩类似单机游戏一样的模式了,也就是平均每天2个小时不到了

她也happy,我觉得也还好,从多玩直接变成少玩了,但是不玩是不可能的



仅供参考,你们可以根据你们家的情况制定适应的规则,大家都遵守就好了