排序算法

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

各种排序算法的比较:

随机化快速排序: 时间复杂度O(nlogn) 递归树的高度logn 不稳定排序

堆排序: 时间复杂度O(nlogn) 不稳定排序，可以用来实现优先队列 top K 数据的问题

归并排序：时间复杂度O(nlogn) 稳定排序

基于比较模型的排序算法的时间复杂度的下届 O(nlogn)

线性时间的排序算法O(n) 基数排序和桶排序，还没看，抽时间看一下

快速排序时间复杂度平均为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 pivot = arr[lo];
 6     while(lo<hi)
 7     {
 8         while(lo<hi && arr[hi]>=pivot) 
 9             --hi;
10         arr[lo] = arr[hi];
11         
12         while(lo<hi && arr[lo]<=pivot)
13             ++lo;
14         arr[hi] = arr[lo];
15     }
16     arr[lo] = pivot;
17     return lo;
18 }
19 
20 void QuickSort(int *arr,int lo,int hi)
21 {
22     if (!arr) return ;
23     if (hi-lo <2)  return ;
24     int mi = partition(arr,lo,hi-1);
25     QuickSort(arr,lo,mi);
26     QuickSort(arr,mi+1,hi);    
27 }
28 
29 int main()
30 {
31     int arr[] = {3,4,6,-1,0};
32     int n = sizeof(arr)/sizeof(int);
33     QuickSort(arr,0,n);
34     for (int i=0;i<n;i++)
35     {
36         cout<<arr[i]<<endl;
37     }
38     return 0;
39 }

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

 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 }

先给堆排序留个坑，最大堆，最小堆，优先队列

好吧，今天下午把堆排序写了，上代码

 1 #include <IOSTREAM>
 2 using namespace  std;
 3 
 4 //从0开始计算 left=2*i+1  right=2*i+2  parent=(i-1)/2
 5 //最开始考虑到运行效率，写成了(i-1)>>1,i<<1+2,i<<1+1 
 6 //忽略了"+"的优先级比"<<" 和 ">>"要高 ,结果一直出不来
 7 #define PARENT(i)    (i-1)>>1        //(i-1)/2   // (i-1)>>1
 8 #define RIGHT(i)     (i<<1)+2        //(i*2)+2   // i<<1+2
 9 #define LEFT(i)      (i<<1)+1        //(i*2)+1   // i<<1+1
10 
11 //使结点i 维持最大堆的性质，length 
12 void maxHeapInfy(int arr[],int i,int heapsize)
13 {
14     int left = LEFT(i);
15     int right = RIGHT(i);
16     int largest = i;
17     if (left<=heapsize && arr[left]>arr[largest])
18         largest = left;
19     
20     if (right<=heapsize && arr[right]>arr[largest])
21         largest = right;
22 
23     if (i!=largest)
24     {
25         swap(arr[i],arr[largest]);
26         maxHeapInfy(arr,largest,heapsize);
27     }    
28 }
29 
30 void buildMaxHeap(int arr[],int heapsize)
31 {
32     //数组元素下标为[0...n],
33     //则从n/2到n都为叶结点，单个元素符合MaxHeap性质
34     int i=0;
35     for (i=heapsize>>1;i>=0;i--)
36         maxHeapInfy(arr,i,heapsize);    
37 }
38 
39 void maxHeapSort(int arr[],int length)
40 {
41     /*构建MaxHeap以后arr[0]的元素始终都是最大值
42     将arr[0] 和 arr[n] 交换，接着将heapsize减一
43     然后arr[0...n-1]维持最大堆
44     */
45     buildMaxHeap(arr,--length);
46     for (int i=length;i>0;i--)
47     {
48         swap(arr[0],arr[i]);
49         length--;
50         maxHeapInfy(arr,0,length);
51     }
52 }
53 
54 int main()
55 {
56     int arr[] = {2,6,1,0,4};
57     int length = sizeof(arr)/sizeof(int);
58     maxHeapSort(arr,length);
59     for (int i=0;i<length;i++)
60     {
61         cout<<arr[i]<<endl;
62     }
63     return 0;
64 }