抓歌的土地

Dragle Earth

 

内部排序算法(转载)

 

  1#include <iostream>
  2#include <windows.h>
  3
  4using namespace std;
  5
  6/*
  7冒泡排序
  8算法：
  9核心思想是扫描数据清单，寻找出现乱序的两个相邻的项目。当找到这两个项目后
 10交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好
 11时间复杂度n*n  (n-1)*n/2
 12*/
 13template <class type>
 14void BubbleSortData(type SortData[], int Length)
 15{
 16    type tmpData = 0;
 17    bool swapFlag = true;
 18    int move = 0;
 19    int compare = 0;
 20    
 21    for(int i=Length-1; i>0 && swapFlag; i--)
 22    {
 23        swapFlag =false;
 24        for(int j=0; j<i; j++)
 25        {
 26            if( SortData[j] > SortData[j+1])
 27            {
 28                tmpData =SortData[j];
 29                SortData[j] =SortData[j+1];
 30                SortData[j+1] =tmpData;
 31                swapFlag =true;
 32                
 33                move +=3;
 34            }
 35            compare++;
 36        }
 37    }
 38    
 39    cout<<"冒泡排序::比较次数="<<compare<<"  移动次数="<<move<<endl;
 40    
 41    return;
 42}
 43
 44/*/////////////////////////////////////////////////////////////////////////
 45以下为快速排序
 46/////////////////////////////////////////////////////////////////////////*/
 47/*
 48快速排序是对起泡排序的一种改进，通过一趟排序将待排序记录分割成独立的两部分，其中
 49一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分继续进行排序，以
 50达到整个序列有序.交换顺序表L中子表L.r[low..high]的记录，使枢轴记录到位，并返回其
 51所在位置，此时在它之前(后)的记录均不大(小)于它时间复杂度为 n*logn,其平均性能最好，
 52若初始记录序列按关键字有序或基本有序，快速排序将锐化为起泡排序
 53*/
 54template<class type>
 55int  Partition(type SortData[], int low, int high)
 56{
 57    type tmpData = SortData[low];//用于子表的第一个记录作枢轴记录
 58    
 59    while( low<high )
 60    {
 61        //从表的两端交替的向中间扫描
 62        while(low<high && SortData[high]>=tmpData)
 63        {
 64            high--;
 65        }
 66        //将比枢轴记录小的记录移到低端
 67        SortData[low] = SortData[high];
 68        
 69        while(low<high && SortData[low]<=tmpData)
 70        {
 71            low++;
 72        }
 73        //将比枢轴记录大的记录移到高端
 74        SortData[high] =SortData[low];
 75    }
 76    //枢轴记录到位
 77    SortData[low] =tmpData;
 78    
 79    return low;//返回枢轴所在位置
 80}
 81
 82template<class type>
 83void QuickSortData(type SortData[], int low, int high)
 84{
 85    int offset;
 86    
 87    if( low<high )
 88    {
 89        offset = Partition(SortData, low, high);
 90        QuickSortData(SortData, low, offset-1);
 91        QuickSortData(SortData, offset+1, high);
 92    }
 93}
 94
 95/*/////////////////////////////////////////////////////////////////////////
 96以下为插入排序
 97/////////////////////////////////////////////////////////////////////////*/
 98/*
 99直接插入排序
100算法：经过i-1遍处理后，L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，
101使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。
102首先比较L[i]和L[i-1]，如果L[i-1]<=L[i]，则L[1..i]已排好序，第i遍处理就结束了;
103否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，
104使得L[j] ≤L[j+1]时为止
105优点:移动元素次数少，只需要一个辅助空间
106时间复杂度n*n
107当待排序记录的数量n很小时，这是一种很好的排序方法。但是n很大时，则不适合
108*/
109template<class type>
110void InsertSortData(type SortData[], int Length)
111{
112    type tmpData =0;
113    int i=0;
114    int j=0;
115    
116    for(i=1; i<Length; i++)
117    {
118        if( SortData[i] <SortData[i-1])
119        {
120            tmpData =SortData[i];
121            //数据往后移动
122            for(j=i-1; j>=0 && tmpData<SortData[j]; j--)
123            {
124                SortData[j+1] =SortData[j];
125            }
126            //将数据插入到j+1位置
127            SortData[j+1] =tmpData;
128        }
129    }
130    
131    return;
132}
133
134/*
135拆半插入排序所需要的辅助空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，
136而记录的移动次数不变。因为时间复杂度仍为n*n
137*/
138template<class type>
139void BInsertSortData(type SortData[], int Length)
140{
141    type tmpData =0;
142    int i=0;
143    int j=0;
144    int low;
145    int high;
146    int middle;
147    
148    for(i=1; i<Length; i++)
149    {
150        tmpData = SortData[i];
151        low = 0;
152        high = i-1;
153        //在r[low..high]中折半查找有序插入的位置
154        while( low<=high )
155        {
156            middle = (low+high)/2;
157            if( tmpData <SortData[middle] )
158            {
159                high = middle-1;
160            }
161            else
162            {
163                low =middle+1;
164            }
165        }
166        //记录后移
167        for(j=i-1; j>=high+1; j--)
168        {
169            SortData[j+1] = SortData[j];
170        }
171        SortData[high+1] = tmpData;
172    }
173    
174    return;
175}
176
177
178//////////////////////////////////////////////////////////////////////////
179
180/*
181简单选择排序
182算法：首先找到数据清单中的最小的数据，然后将这个数据同第一个数据交换位置；接下来
183找第二小的数据，再将其同第二个数据交换位置，以此类推。所需移动的操作次数最少为0,
184最大为3(n-1)然而无论记录的初始排列如何，需要比较的次数相同n(n-1)/2 复杂度为n*n
185*/
186template <class type>
187void SelectSortData(type SortData[], int Length)
188{
189    type tmpData;
190    int offset =0;
191    int j=0;
192    
193    for(int i=0; i<Length-1; i++)
194    {
195        offset =0;
196        tmpData =SortData[i];
197        for(j=i+1; j<Length; j++)
198        {
199            if( tmpData>SortData[j] )
200            {
201                tmpData =SortData[j];
202                offset =j;
203            }
204        }
205        
206        if( offset >i)
207        {
208            SortData[offset] =SortData[i];
209            SortData[i] =tmpData;
210        }
211    }
212    
213    return;
214}
215
216/*
217堆排序
218(1)用大根堆排序的基本思想
219① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区
220② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，
221由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
222③ 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。
223然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，
224由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n- 2].
225keys≤R[n-1..n].keys，
226同样要将R[1..n-2]调整为堆。
227……
228直到无序区只有一个元素为止。
229(2)大根堆排序算法的基本操作：
230① 初始化操作：将R[1..n]构造为初始堆；
231② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，
232然后将新的无序区调整为堆(亦称重建堆)。
233注意：
234①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
235②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。
236堆排序和直接选择排序相反：在任何时刻，堆排序中无序区总是在有序区之前，
237且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。 
238*/
239
240//生成大根堆
241template <class type>
242void HeapAdjust(type SortData[],int start, int Length)
243{
244    while( 2*start+1<Length )
245    {
246        int minchild = 2 * start + 1;
247        
248        if( 2*start+2<Length )
249        {
250            //比较左子树和右子树，记录最大值的Index
251            if( SortData[2*start+1]<SortData[2*start+2] )
252            {
253                minchild = 2*start + 2;
254            }
255        }
256        
257        if( SortData[start]<SortData[minchild] )
258        {
259            //交换i与minchild的数据
260            type tmpData =SortData[start];
261            
262            SortData[start] =SortData[minchild];
263            SortData[minchild] =tmpData;
264            //堆被破坏，需要重新调整
265            
266            start = minchild ;
267        }
268        else
269        {
270            //比较左右孩子均大则堆未破坏，不再需要调整
271            break;
272        }
273    }
274    
275    return;
276}
277
278//堆排序
279template<class type>
280void HeapSortData(type SortData[], int Length)
281{
282    int i = 0;
283    
284    //将Hr[0,Lenght-1]建成大根堆
285    for(i=Length/2-1; i>=0; i--)
286    {
287        HeapAdjust(SortData, i, Length);
288    }
289    
290    for(i=Length-1; i>0; i--)
291    {
292        //与最后一个记录交换
293        type tmpData =SortData[0];
294        SortData[0] =SortData[i];
295        SortData[i] =tmpData;
296        //将H.r[0..i]重新调整为大根堆
297        HeapAdjust(SortData, 0, i);
298    }
299    
300    return;
301}
302
303/*
304    归并排序算法以O（nlogn）最坏情形运行时间运行，而所使用的比较次数几乎是最优的。
305    它可以用递归的形式实现，形式简洁易懂。但是需要注意的是当用递归形式时，如果数
306    据较多，则开销很大，实用性很差，所以我们一般采用非递归的形式。我这里两种形式
307    都给出。不管是递归还是非递归，归并排序算法中基本的操作是合并两个已经排序的数组。
308递归形式：
309*/
310
311template<class type>
312void Merge(type SortData[], int left, int mid, int right, int n)
313{
314    type * t = new type[n];//存放被排序的元素
315    int i = left;
316    int j = mid + 1;
317    int k = 0;
318    
319    while( i<=mid&&j<=right )
320    {
321        if( SortData[i]<=SortData[j] )
322            t[k++] = SortData[i++];
323        else
324            t[k++] = SortData[j++];
325    }
326    
327    if( i==mid+1 )
328    {
329        while( j<=right )
330            t[k++] = SortData[j++];
331    }
332    else
333    {
334        while( i<=mid )
335            t[k++] = SortData[i++];
336    }
337
338    //把t[]的元素复制回a[]
339    for(i=left,k=0; i<=right; i++,k++)
340        SortData[i] = t[k];
341    
342    delete [] t;
343}
344
345template <class type>
346void MergeSort(type SortData[], int left, int right)
347{
348    if(left < right)
349    {
350        int mid = (left + right) / 2;
351        MergeSort(SortData, left, mid);
352        MergeSort(SortData, mid+1, right);
353        Merge(SortData, left, mid, right, right-left+1);
354    }
355}
356
357template <class type>
358void MergeSortData(type SortData[], int Length)
359{
360    MergeSort(SortData, 0, Length - 1);
361}
362
363int main()
364{
365    //int Buffer[] ={1,2,3,4,5,6};
366    //    int Buffer[] ={6,5,4,3,2,1};
367    
368    //    QuickSortData(Buffer,0, 5);
369    
370    char Buffer[] = {5, 9, 7, 8, 3, 1, 10, 6};
371    //    QuickSortData(Buffer, 0, 7);
372    MergeSortData(Buffer, 8);
373    /*
374    int nLen = 50000;
375    
376    char * buffer = new char[nLen];
377      
378    int i = 0;
379        
380    for( i=0; i<nLen; i++ )
381    {
382        buffer[i] = nLen - i;
383    }
384          
385    int nStart = GetTickCount();
386            
387    BubbleSortData(buffer, nLen);
388              
389    int nEnd = GetTickCount();
390                
391    printf("Bubble: %d\n", nEnd - nStart);
392                  
393    for( i=0; i<nLen; i++ )
394    {
395        buffer[i] = nLen - i;
396    }
397                    
398    nStart = GetTickCount();
399                      
400    HeapSortData(buffer, nLen);
401                        
402    nEnd = GetTickCount();
403                          
404    printf("Heap: %d\n", nEnd - nStart);
405    */
406    //     for(int i=0; i<6; i++)
407    //     {
408    //         cout<<Buffer[i]<<" ";
409    //     }
410    //cout<<endl;
411    
412    return 0;
413}
414

posted on 2008-10-28 17:56 松松 阅读(384) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理


导航

统计

常用链接

留言簿(1)

随笔档案

map

搜索

最新评论

阅读排行榜

评论排行榜