webdancer's Blog

排序算法

我的算法可以说应该是很烂，归结起来：(1)不善总结，无法融汇贯通，与性格有关。(2)经常忘记，无法应用的好，与智商有关。我觉得：智商不高，还可以在计算机世界里混，但是若是性格不好，不能坚持，我觉得难有成绩。现在，该录正题了。

排序到底有什么用呢？对于我来说，我以前没有认真思考过这个问题，在Tao里，作者总结了一下,这里记录一下：

(1)解决“一起性”问题，把具有相同标志的项目连在一起。其实，sort在英文中就有分类的意思。把相同的东西归到一起，排序实在是好呀！

(2)匹配在两个文件或更多的文件中的项。排好序就可以顺序的扫描，而不用跳来跳去。

(3)通过键码查询信息。很多的检索算法用得到排序，向我们熟悉的二分查找，不就是对已经排好序的序列。

排序分为：内部排序和外部排序。所有的数据都可以放入主存中时，采用内部排序；当不能完全的放入主区，则只能采用外部排序。我还是先学习一下内部排序。

(1)直接插入排序。这种排序思想简单，就是在已经排好序的序列中，插入元素。

/*直接插入*/
void chsort(int a[],int n){
    int j,k;
    for(j=1;j<n;j++){
        k=a[j];
        int i=j-1;
        while(a[i]>k){
            a[i+1]=a[i];
            i--;
        }
        a[i+1]=k;
    }
}

(2)通过交换排序。

冒泡排序：

/*冒泡排序*/
void bsort(int a[],int n){
     int isch=1 , i,j;
     for(i=n-1;i>0&&isch;i--){
         isch=0;
         for(j=0;j<=i;j++){
             if(a[j]>a[j+1]){
                 int t;
                 t=a[j];
                 a[j]=a[j+1];
                 a[j+1]=t;
                 isch=1;
             }
         }
     }
}

快速排序：

/*快速排序的划分方式,a[r] 有最大的值。*/
void sortone(int a[],int l,int r){
    if(l>=r) return;
    int i=l+1,j=r;
    int base=a[l];
    while(i<j){
    while(a[i]<base)
        i++;
    while(a[j]>base)
        j--;
    if(i<j){
    int t=a[i];
    a[i]=a[j];
    a[j]=t;
    }
    }
    a[l]=a[j];
    a[j]=base;
    /*递归的调用sortone*/
    sortone(a,l,j-1);//  First, the wrong is: sortone(a,l,j).
    sortone(a,j+1,r);
}
/*为了排序的接口统一*/
void qusort(int a[],int n){
    sortone(a,0,n-1);
}

快速排序分析：

//使用快排对a[0...n-1]进行排序。

从a[0...n-1]中选择支点，把剩下的分为两段：left ，right；左边的都小于支点，右边的都大于支点。然后，递归的来对left，right进行排序，最后的结果为：left ,支点，right。

如何选择支点进行划分left,right会严重的影响快排的效率，我选择了教科书上的给出支点a[0]。但是，不是很好呀！快排对已经有序的序列进行排序，时间复杂度会上升的O(n2)，偏爱无序的序列。

不知道C函数库中的:

1	`void` `qsort(` `void` `buf,` `size_t` `num,` `size_t` `size,` `int` `(compare)(const` `void` `,` `const` `void` `) );`

如何实现的。

(3)选择排序。

/*直接选择排序*/
void xzsort(int a[],int n){
    int j;
    for(j=n-1;j>0;j--){
        int maxIndex=0,i;
        for(i=1;i<=j;i++)
            if(a[i]>a[maxIndex])
                maxIndex=i;
        int t;
        t=a[maxIndex];
        a[maxIndex]=a[j];
        a[j]=t;
    }
}

利用MAXHEAP来实现选择排序应该是一种很好的方法。MaxHeap数据结构的构建还是比较复杂的，涉及到构建堆，插入，删除MAX等。感觉在构建复杂的数据类型时，c++/java等引入了类的语言还是简单呀！