算法导论的快排(未验证) 深入理解

为什么快速排序能更快呢？

如果每次参考值都是再子数组取得最大最小值，那么跟选择排序有什么差别?

极端的情形有所有的数据都是一样的

如果每次都取得是中间值,最后都分成两个元素的数组

在有序的情况下，快排性能很差，但是插入排序在数据基本排好的情况下是非常快的。所以我们在用快排之后，等待基本有序就可以用插入排序。

同时递归的时候，使用太多的调用栈会消费太多资源，是的程序运行得很慢，我们《算法导论》使用一种编译程序的优化方法来处理，尾递归。但是我们手动写的尾递归实际效率是差不多的。

算法导论快速排序的主要不同点在与partition，分成三个区间，B有可能不存在，而这个用两个指针，一个A指向小于中间值的子数组里，一个C指向还没有比较处理的值，一经发现符合要求，就马上把他放入的已经确定是小于中间值的数组A后面一个数值交换，实际就是跟biggerArray里面的第一个元素交换，（如果biggerArray不存在，那么A后面第一个元素就是B指向的自己）

smallerArray (pointer A)

biggerArray B

unSorted (pointer C)

到最后，也是重复一个动作来交换A数组后面的第一个元素

 1 View Code 
 2  #include <stdio.h>
 3  
 4  int partition ( int * a , int start , int end )
 5  {
 6         int smallerInx = start ;
 7         int sortedInx     = start - 1;
 8         int pvot             =  a[end];
 9          for ( ; unSortedInx  < end;  unSortedInx ++)
10        {
11                 if ( a[unSortedInx ] < pvot )
12                 {
13                            smallerInx ++;
14                           swap( a[smallerInx ] , a[unSortedInx]);
15                 }
16        }
17        swap( a[smallerInx + 1], a[end]);
18       return smallerInx + 1;
19  }
20  void quickSort ( int * a , int start ,int  end )
21  {
22        int pvot ;
23        if ( start < end )
24       {
25              quickSort ( a , start, pvot -1);
26              quickSort ( a , pvot+1, start);
27       } 
28  }
29  
30  int main()
31  {
32     
33  }

  1  
  2 
  3 size_t partition( void *base , size_t size , size_t start , size_t end ,(int *(compare(void * ,void *)))
  4 
  5 {
  6
  7     size_t sortedInx = start -1;
  8 
  9     size_t unSortedInx = start;
 10 
 11     void * pvot   = base + end * size ;
 12 
 13     for ( ; unSortedInx < end ; unSortedInx ++)
 14 
 15   {
 16 
 17 　　    if( compare(( base + size * unSortedInx ) , pvot) < 0  ) 
 18 
 19         {
 20 
 21 　　　　　　　　sortedInx ++;
 22 
 23                       swap( base + size* unSortedInx , pvot);
 24 
 25         }
 26 
 27    
 28 
 29 }
 30 
 31       swap ( base + size*(unSortedInx + 1) , pvot);
 32 
 33       return unSortedInx + 1;
 34 
 35 }
 36 
 37  
 38 
 39  
 40 
 41 int quickSort(void *base , size_t nr , size_t size , (int *(compare(void * ,void *)))
 42 
 43  
 44 
 45  
 46 
 47  
 48 
 49 {
 50 
 51  
 52 
 53     _quickSort(base,size, 0, nr-1 , compare);
 54 
 55    return 0;
 56 
 57  
 58 
 59  
 60 
 61  
 62 
 63  
 64 
 65  
 66 
 67 }
 68 
 69  
 70 
 71 void _quickSort(void *base, size_t size , size_t start , size_t end , compare)
 72 
 73  
 74 
 75  
 76 
 77 {
 78 
 79  
 80 
 81 　　size_t pvot ;
 82 
 83  
 84 
 85      if ( start < end)
 86 
 87  
 88 
 89  
 90 
 91    {
 92 
 93 　　　　pvot = partition ( base , size, start , end , compare);
 94 
 95            _quickSort ( base, size, start, pvot-1);
 96 
 97            _quickSort ( base, size, pvot+1 , end);
 98 
 99  
100 
101    }
102 
103  
104 
105  
106 
107  
108 
109  
110 
111 }
112 
113  
114 
115  
116 
117  
118 
119  
120 
121  
122 
123  
124 
125  
126 
127  
128 
129  
130 
131  
132
133