首页 > 代码库 > 排序大总结

排序大总结

5.排序操作
5.1基础知识
对于排序操作,介绍过很多的算法,在笔记中有关于排序算法的简单总结,但是对于每一个配需算法没有详细的深入,知识对于排序的稳定性做了一下了解。下面深入的分析一下排序算法,并且使用 C++ 语言实现。
    首先介绍上一次在笔记中整理稳定排序和不稳定排序的知识: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。
     同时我们在分析一下关于排序算法的一些知识。对于排序,需要序列和关键字。关键字可能重复出现,这样排序的结果会因为排序算法的不同而产生不同的排序结果,这就是所谓的稳定排序和不稳定排序。
     当数据量比较小的时候,可以讲所有的数据完全放倒计算机的内存中进行排序;但是当数据量十分大的时候,我们的数据不可以完全放倒计算机内存中进行排序,整个排序过程要在内存和外存之间进行切换,因此排序又可以分为内部排序和外部排序。
     对于排序算法我们需要分析算法的性能,需要靠了最好的情况和最坏的情况,以及平均状况下的时间复杂度和空间复杂度。
5.2选择排序
首先介绍的是选择排序:选择排序主要是在当前排序队列中,选取关键字最小的,最为当前的第一个记录,发生交换,之后以此进行,第 i次选择及时选择第 i个最值元素,然后交换,所以该排序是不稳定的排序算法。
实现带C++代码:
template <class T >
void  ChooseSort(T Data [], int n ){
    for (int i=1;i<n;i++){
         int k=i-1; // 记录当前待排序的第一个元素,假设他是最小的,然后如果有比他小的则,更改 k
         for( int j=i;j< n;j++){
             if( Data[j]< Data[k]){
                k=j;
            }
        }
         if(k!=i-1){
             T temp= Data[k];
             Data[k]= Data[i-1];
             Data[i-1]=temp;
        }
    }
}
对于算法的复杂度进行分析:
     选择排序需要进行 n-1次选择,第 i次选择是在 n-i个元素中选择最小的元素,所以需要比较 n-i次,执行交换最多一次,最少不进行交换。所以选择排序的时间复杂度是 O( n^2) .空间复杂度是 O( 1)只需要一个临时交换变量的空间。选择排序主要是利用关键字进行比较,并没有利用地 i-1次的比较所得信息。如果可以利用上一次比较的信息,就可以减少之后每一次比较的次数。这就是堆排序
5.3堆排序
     首先堆排序也是不稳定的排序算法。堆数据结构可以被看成是一个完全二叉树,可以利用数组实现堆的存储。其中对应的二叉树的每一个节点和数组中的对应位置处的元素对应。堆有两种:最大堆和最小堆。在最大堆中,每一个节点对应的值都应该大于或者等于该节点的子节点。最小堆则相反。
     堆排序就是利用最大堆来得到最大的元素,也就是堆的根节点,具体步骤如下:
    1 )初始化待排数据为一个最大堆,初始化当前待排序列中的个数 n
    2 )将堆顶怨毒和最后一个元素进行交换, n=n-1
    3 )调整堆结构
4)如果当前待排序咧元素个数 n>1,重复 2,3
当每一次将最后一个元素和堆中的根节点进行交换之后,就应该执行一次调整。由于以根的两个子节点为根的子树任然是最大堆的性质,所以只需要调用 SiftDown操作,从堆的根节点向下进行调整即可。
这里需要使用堆的知识,首先序列生成一个堆,使用函数 BuildHeap( Data[],n) .生成对的操作需要使用到函数 Siftdown( T Data[], int i, int n)来不断的调整非叶子节点和子节点的顺序。
当构建玩一个堆的时候,将堆中的最后一个元素和第一个元素交换,这样最后一个元素是最大的元素,然后再调整堆。
template <class T >
void SiftDown(T Data [],int i ,int n ){
    int l=2*i+1,r=2*i+2,min=i;
    if(l<n && Data[min]<Data[l]){
         //和左子节点比较
        min=l;
    }
    if(l<n&& Data[min] < Data[r]){
         //和右子节点比较
        min=r;
    }
    if(min != i){
         T temp = Data[min];
         Data[min]= Data[ i];
         Data[ i]=temp;
        SiftDown( Data,min, n);
    }
}
template<class T >
void BuildHeap(T Data [],int n ){
    int p=n/2-1;//求出非叶子节点的最大下标
    for(int i=p;i>=0;i--){
        SiftDown( Data,i, n);
    }
}
template <class T >
void HeapSort(T Data [],int n ){
    BuildHeap(Data,n);
    for(int i=n-1;i>0;i--){
         T temp = Data[0];
         Data[0]= Data[i];
         Data[i]=temp;
        SiftDown( Data,0,i);
    }
}
     算法分析:对于调整堆的操作 SiftDown函数,最对执行 O(logn)次数据交换 ,初始化堆的时间复杂度是 O(n)。对排序算法中调用了 n-1次 SiftDown操作,以及一次初始化堆的操作,所以时间复杂度是 n*logn. 空间复杂度也是 O( 1)。当数据量比较大的时候会体现出很好的效果,小数据量不明显。堆排序是不稳定的排序算法。
     堆排序也是一种选择排序,只不过开始的是简单的选择排序,堆排序是基于堆的选择排序。
5.4插入排序(直接插入排序)
     该算法比较简单,时间复杂度瑟吉欧 O(N^2)但是该算法是稳定的排序。
template<class T >
void InsertSort(T Data [],int n ){
    int p,i;
    for(p=1;p<n;p++){
         T temp= Data[p];
         for(i=p-1; i>=0 && Data[i]>temp;i--){
             Data[i+1]= Data[i];
        }
         Data[i+1]=temp;
    }
}
5.5折半插入排序
     直接插入排序是利用有序表的插入操作实现对数据的排序。在进行 p+1插入的时候 ,需要在前面的元素中找到合适的位置,因为他是排好序的,所以我们使用二分查找确定该元素的位置。分析复杂度:
     空间复杂度还是一样,但是时间复杂度上,比较次数与直接插入排序算法要好,最好的情况下时间复杂度是 O( n*logn) ,但是移动的此时还是一样的。
template<class T >
void BinaryInsertSort(T Data [],int n ){
    int left,mid,right,p;
    for(p=1;p>n;p++){
         T temp= Data[p]; //保存待插入元素
        left=0,right=p-1;
         while(left<=right){
            mid=(left+right)/2;
             if( Data[mid]>temp){
                right=mid-1;
            }
             else{
                left=mid+1;
            }
        }
         for( int i=p-1;i>=left;i--){
             Data[i+1]= Data[i];
        }
         Data[left]=temp;
    }
}
5.6希尔排序
     折半插入排序改进类直接插入排序中确定插入元素位置的位置,希尔排序则是利用直接插入排序中的一些特定进行的改进。
     如果待排序列是有序的,最好的时间复杂度是 O(N),另外对于短排序来说,插入排序也是比较有效地排序算法。希尔排序正是利用直接插入排序的这两个性质进行的改进。
     希尔排序的基本思想是:现将待排序的数据划分成若干个子序列分别进行直接插入排序,待整个序列中的数据基本有序之后,在对全部的数据进行一次直接插入排序。对于子排序的算法可以使用直接插入排序算法。 希尔排序复杂度依赖于增量序列的选择,分析过程比较复杂。但是 Shell排序时间复杂度在 O(N^2)~ O(n*logn)之间。但是本算法也是不稳定的排序算法。
template <class T >
void ShellSort(T Data [],int n ){
    int d=n/2;
    while(d>=1){
         for( int k=0;k<d;k++){
             for( int i=k+d;i< n;i+=d){
                 T temp= Data[i];
                 int j=i-d;
                 while(j>=k && Data[j]>temp){
                     Data[j+d]= Data[j];
                    j-=d;
                }
                 Data[j+d]=temp;
            }
        }
        d=d/2;
    }
}
5.7交换排序冒泡排序
     通过不断比较相邻两个元素的值,然后决定是否对这两个元素进行交换。从而达到排序的目的。每一次排序,最后一个元素之最值元素。最坏的情况下,复杂度是 O(N^2),是一种稳定的排序算法。
template <class T >
void BubbleSort(T Data [],int n ){
    int flag=0;
    for(int i=0;i<n;i++){
       
         for( int j=1;j< n-i;j++){
             if( Data[j]< Data[j-1]){
               
                 T temp = Data[j];
                 Data[j]= Data[j-1];
                 Data[j-1]=temp;
            }
        }
    }
}
5.8快速排序
    快速排序分为三步,主要采用的是分值算法的思想:
    分割:取出序列中的一个元为轴元素,利用这个轴元素将数据分成三段,一部分大于在右边,一部分小于在左边。
    分治:对左边和右边的元素递归调用 1,分别实现对左边和右边的排序
    合并:每一个元素已经被正确放置了。
    分割策略:分别从待排序列两边相向遍历,即从左边遍历确定第一个大于轴元素的元素,从右往左遍历确定第一个不大于轴元素的元素,然后交换二者。
template <class T >
int Partion(T Data [],int start ,int end ){
    T privot=Data[start];
    int left=start,right=end;
    while(left<=right){
         while(left<=right && Data[left]<=privot){
            left++;
        }
         while(left<=right && Data[right]>privot){
            right--;
        }
         if(left<right){
            swap( Data[right], Data[left]);
            left++;right--;
        }
    }
    swap(Data[start],Data[right]);
    return right;
}
 
template <class T >
void QuickSort(T Data [],int left ,int right ){
    if (left<right){
         int p =Partion( Data, left, right);
        QuickSort( Data, left,p-1);
        QuickSort( Data,p+1, right);
    }
}
比较的次数 n*logn + n = O(n*logn)
时间复杂度: O(n*logn)
空间复杂度 最好是 O( logn) 最坏是 O(N)
不是稳定的排序
5.9归并排序 是一种稳定的排序算法
template <class T >
void  Merge(T Data [],int start ,int mid ,int end ){
    int len1 = mid -start+1,len2=end-mid;
    int i,j,k;
    T * left = new T[len1];
    T * right = new T[len2];
    for(i=0;i<len1;i++){
        left[i]= Data[i+ start];
    }
    for(i=0;i<len2;i++){
        right[i]= Data[ mid+i+1];
    }
    i=0;j=0;
    for(k=start;k<end;k++){
         if(i==len1 || j==len2){
             break;
        }
         if(left[i]<=right[j]){
             Data[k++]=left[i++];
        }
         else{
             Data[k++]=right[j++];
        }
    }
    while(i<len1){
         Data[k++]=left[i++];
    }
    while(j<len2){
         Data[k++]=right[j++];
    }
    delete [] left;
    delete[] right;
}
 
template <class T >
void MergeSort(T Data [], int start ,int end ){
    if(start<end){
         int mid=( start+ end)/2;
        MergeSort( Data, start,mid);
        MergeSort( Data,mid+1, end);
        Merge( Data, start,mid, end);
    }
}
归并排序时间复杂度也是 O(n*logn)但是他是稳定的排序,相对于快速排序,需呀使用一些空间,需要二外使用 O(N)的空间。
  

 

各种排序算法的稳定性和时间复杂度小结 - hkx1n的专栏 - 博客频道 - CSDN.NET

来源网址: http://blog.csdn.net/hkx1n/article/details/3922249

各种排序算法的稳定性和时间复杂度小结

分类: C/C++2009-02-22 16:03 32610人阅读 评论(21) 收藏 举报
算法shelln2null数据结构class

目录(?)[+]

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

 

冒泡法: 
这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:  复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。

直接插入排序:O(n*n)

选择排序:O(n*n)

快速排序:平均时间复杂度log2(n)*n,所有内部排序方法中最高好的,大多数情况下总是最好的。

归并排序:log2(n)*n

堆排序:log2(n)*n

希尔排序:算法的复杂度为n的1.2次幂

 

这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:

首先我们考虑最理想的情况
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)算法,但是通常情况下速度要慢 于快速排序(因为要重组堆)。

 

 

这几天笔试了好几次了,连续碰到一个关于常见排序算法稳定性判别的问题,往往还是多选,对于我以及和我一样拿不准的同学可不是一个能轻易下结论的题目,当然如果你笔试之前已经记住了数据结构书上哪些是稳定的,哪些不是稳定的,做起来应该可以轻松搞定。

本文是针对老是记不住这个或者想真正明白到底为什么是稳定或者不稳定的人准备的。

      首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj, Ai原来在位置前,排序后Ai还是要在Aj位置前。

     其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。

     回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。

   (1)冒泡排序

        冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

(2)选择排序

      选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n-1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9, 我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

(3)插入排序
     插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

(4)快速排序
    快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j, 交换a[i]和a[j],重复上面的过程,直到i>j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11, 现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j]交换的时刻。

(5)归并排序
    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

(6)基数排序
   基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

(7)希尔排序(shell)
    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的。

(8)堆排序
   我们知道堆的结构是节点i的孩子为2*i和2*i+1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列,堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时,就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了,而第n/2-1个父节点把后面一个相同的元素没有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法

 

1 快速排序(QuickSort)

快速排序是一个就地排序,分而治之,大规模递归的算法。从本质上来说,它是归并排序的就地版本。快速排序可以由下面四步组成。

(1) 如果不多于1个数据,直接返回。
(2) 一般选择序列最左边的值作为支点数据。
(3) 将序列分成2部分,一部分都大于支点数据,另外一部分都小于支点数据。
(4) 对两边利用递归排序数列。

快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法,但是就通常情况而言,没有比它更快的了。快速排序是递归的,对于内存非常有限的机器来说,它不是一个好的选择。

2 归并排序(MergeSort)

归并排序先分解要排序的序列,从1分成2,2分成4,依次分解,当分解到只有1个一组的时候,就可以排序这些分组,然后依次合并回原来的序列中,这样就可以排序所有数据。合并排序比堆排序稍微快一点,但是需要比堆排序多一倍的内存空间,因为它需要一个额外的数组。

3 堆排序(HeapSort)

堆排序适合于数据量非常大的场合(百万数据)。

堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录,因为快速排序,归并排序都使用递归来设计算法,在数据量非常大的时候,可能会发生堆栈溢出错误。

堆排序会将所有的数据建成一个堆,最大的数据在堆顶,然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆,交换数据,依次下去,就可以排序所有的数据。

4 Shell排序(ShellSort)

Shell排序通过将数据分成不同的组,先对每一组进行排序,然后再对所有的元素进行一次插入排序,以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。

Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。

5 插入排序(InsertSort)

插入排序通过把序列中的值插入一个已经排序好的序列中,直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序,或者重复排序超过200数据项的序列。

6 冒泡排序(BubbleSort)

冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素,使较大的数据下沉,较小的数据上升。它是O(n^2)的算法。

7 交换排序(ExchangeSort)和选择排序(SelectSort)

这两种排序方法都是交换方法的排序算法,效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段,在实际中使用较少。

8 基数排序(RadixSort)

基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法,但是它只能用于整数的排序,如果我们要把同样的办法运用到浮点数上,我们必须了解浮点数的存储格式,并通过特殊的方式将浮点数映射到整数上,然后再映射回去,这是非常麻烦的事情,因此,它的使用同样也不多。而且,最重要的是,这样算法也需要较多的存储空间。

9 总结

下面是一个总的表格,大致总结了我们常见的所有的排序算法的特点。

排序法平均时间最差情形稳定度额外空间备注
冒泡O(n2)    O(n2)稳定O(1)n小时较好
交换    O(n2)    O(n2)不稳定O(1)n小时较好
选择O(n2)O(n2)不稳定O(1)n小时较好
插入O(n2)O(n2)稳定O(1)大部分已排序时较好
基数O(logRB)O(logRB)稳定O(n)

B是真数(0-9),

R是基数(个十百)

ShellO(nlogn)O(ns) 1<s<2不稳定O(1)s是所选分组
快速O(nlogn)O(n2)不稳定O(nlogn)n大时较好
归并O(nlogn)O(nlogn)稳定O(1)n大时较好
O(nlogn)O(nlogn)不稳定O(1)n大时较好

以下是一个基于模板的通用排序:
这个程序我想就没有分析的必要了,大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
    CMyData(int Index,char* strData);
    CMyData();
    virtual ~CMyData();

    int m_iIndex;
    int GetDataSize(){ return m_iDataSize; };
    const char* GetData(){ return m_strDatamember; };
    //这里重载了操作符:
    CMyData& operator =(CMyData &SrcData);
    bool operator <(CMyData& data );
    bool operator >(CMyData& data );

private:
    char* m_strDatamember;
    int m_iDataSize;
};
////////////////////////////////////////////////////////

MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}

CMyData::~CMyData()
{
    if(m_strDatamember != NULL)
      delete[] m_strDatamember;
    m_strDatamember = NULL;
}

CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
    m_iDataSize = strlen(strData);
    m_strDatamember = new char[m_iDataSize+1];
    strcpy(m_strDatamember,strData);
}

CMyData& CMyData::operator =(CMyData &SrcData)
{
    m_iIndex = SrcData.m_iIndex;
    m_iDataSize = SrcData.GetDataSize();
    m_strDatamember = new char[m_iDataSize+1];
    strcpy(m_strDatamember,SrcData.GetData());
    return *this;
}

bool CMyData::operator <(CMyData& data )
{
    return m_iIndex<data.m_iIndex;
}

bool CMyData::operator >(CMyData& data )
{
    return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"

template <class T>
void run(T* pData,int left,int right)
{
    int i,j;
    T 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);
}

template <class T>
void QuickSort(T* pData,int Count)
{
    run(pData,0,Count-1);
}

void main()
{
    CMyData data[] = {
      CMyData(8,"xulion"),
      CMyData(7,"sanzoo"),
      CMyData(6,"wangjun"),
      CMyData(5,"VCKBASE"),
      CMyData(4,"jacky2000"),
      CMyData(3,"cwally"),
      CMyData(2,"VCUSER"),
      CMyData(1,"isdong")
    };
    QuickSort(data,8);
    for (int i=0;i<8;i++)
      cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"/n";
    cout<<"/n";
}