排序算法

浏览数：15 / 时间：2015年06月08日

排序算法应该也是面试中会经常问到的问题。 /汗现在就只会快速排序和归并排序。前两天看《算法导论》的堆排序，自己没能写出，代码都写出来了，就是通过不了测试，等过两天再写堆排序吧，今天先把快速排序和归并写了。嗯，而且要开始学 STL了，要不然笔试的时候算法都自己写，太耗时间了。

快速排序时间复杂度平均为O(nlogn) 最差为O(n^2) 采用随机快速排序来避免这种情况

 1 int Partition(int arr[],int lo,int hi)
 2 {
 3     //随机化的快速排序，避免O(n^2)
 4     swap(arr[lo],arr[lo+rand()%(hi-lo+1)]);
 5     int t = arr[lo];
 6     while(lo<hi)
 7     {
 8         while(lo<hi && arr[hi]>=t)
 9             --hi;
10         arr[lo] = arr[hi];
11 
12         while(lo<hi && arr[lo]<=t)
13             ++lo;
14         arr[hi] = arr[lo];
15     }
16     arr[lo] = t;
17     return t;
18 }
19 
20 void QuickSort(int arr[],int lo,int hi)
21 {
22     if (hi-lo<2)  return;
23     while(lo<hi)
24     {
25         int mi = Partition(arr,lo,hi);
26         QuickSort(arr,lo,mi);
27         QuickSort(arr,mi+1,hi);
28     }
29 }

归并排序时间复杂度稳定在O(logn)

 1 void MergeSort(int arr[],int lo,int hi)
 2 {
 3     if (hi-lo<2)  return;
 4     int mi = (lo+hi)>>1;
 5     //以中点为界分别排序
 6     MergeSort(arr,lo,mi);  
 7     MergeSort(arr,mi,hi);
 8     Merge(arr,lo,mi,hi);
 9 }
10 
11 void Merge(int arr[],int lo,int mi,int hi)
12 {
13     int *A = arr + lo; 
14     int lb = mi-lo;
15     int *B = new int [lb];   //前子向量
16     for (int i=0;i<lb;B[i++]=A[i++]); //复制前子向量
17     int lc = hi-mi;
18     int *C = arr + mi;      //后子向量
19     for (int i=0,j=0,k=0;(j<lb) || (k<lc))
20     {
21         //加B
22         if ((j<lb) && (!(k<lc)||B[j]<=C[k]))  A[i++] = B[j++];
23         //加C
24         if ((k<lc) && (!(j<lb)||B[j]> C[k]))  A[i++] = C[k++];        
25     }
26     delete []B;
27 }