sort &&qsort

小鱼儿 2022-08-11 03:27 144阅读 0赞

两个关于快排的函数，但是刚开始不会用，因此记录一下。

当在pascal里埋头苦干的前辈们还在为快排和堆排哪个效率更高争吵不休时，我们拥有了qsort。  
  
当我还在为qsort里最后一个参数愁眉苦脸时，STL的工程师们发明了sort。  
  
——Crux.D

**qosrt：**

源自于C，但C标准未对其作出规定。有时算法会发生退化，效率较sort可能差一些。其包含在stdlib.h

函数原型：

void qsort ( void \* base, size\_t num, size\_t size, int ( \* comparator ) ( const void \*, const void \* ) );

Sort elements of array

Sorts the  num elements of the array pointed by  base, each element  size bytes long, using the  compar function to determine the order.  
  
The sorting algorithm used by this function compares pairs of elements by calling the specified  compar function with pointers to them as argument.  
  
The function does not return any value, but modifies the content of the array pointed by  base reordering its elements as defined by  compar.  
  
The order of equivalent elements is undefined.  
  
给基底指向的数组进行排序，每个元素长度为1byte，用compare函数决定排列顺序。该函数无返回值，但会以compare确定的顺序修改base指向的数组的元素的顺序。

### Parameters ###

base

Pointer to the first object of the array to be sorted, converted to a  `void*`.

num

Number of elements in the array pointed by  base.  
[size\_t][size_t] is an unsigned integral type.

size

Size in bytes of each element in the array.  
[size\_t][size_t] is an unsigned integral type.

compar

Pointer to a function that compares two elements.  
This function is called repeatedly by  qsort to compare two elements. It shall follow the following prototype:

<table style="font-size:12px"> 
 <tbody> 
  <tr> 
   <td style="text-align:right; vertical-align:top; min-width:20px"> <pre style="margin-top:0px; margin-bottom:0px"><code>&nbsp;</code></pre> </td> 
   <td style="background-color:rgb(239,239,255); border:1px solid rgb(192,192,208); vertical-align:top"> <pre style="margin-top:0px; margin-bottom:0px"><code>int compar (const void* p1, const void* p2);</code></pre> </td> 
   <td style="vertical-align:top; padding:0px">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

Taking two pointers as arguments (both converted to  const void\*). The function defines the order of the elements by returning (in a stable and transitive manner):

<table style="font-size:12px; border-collapse:collapse"> 
 <tbody> 
  <tr> 
   <th style="background-color:rgb(240,240,240); border:1px solid black">return value</th> 
   <th style="background-color:rgb(240,240,240); border:1px solid black">meaning</th> 
  </tr> 
  <tr> 
   <td style="border:1px solid black"><code>&lt;0</code></td> 
   <td style="border:1px solid black">The element pointed by&nbsp;p1&nbsp;goes before the element pointed by&nbsp;p2</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid black"><code>0</code></td> 
   <td style="border:1px solid black">The element pointed by&nbsp;p1&nbsp;is equivalent to the element pointed by&nbsp;p2</td> 
  </tr> 
  <tr> 
   <td style="border:1px solid black"><code>&gt;0</code></td> 
   <td style="border:1px solid black">The element pointed by&nbsp;p1&nbsp;goes after the element pointed by&nbsp;p2</td> 
  </tr> 
 </tbody> 
</table>

For types that can be compared using regular relational operators, a general  compar function may look like:

<table style="font-size:12px"> 
 <tbody> 
  <tr> 
   <td style="text-align:right; vertical-align:top; min-width:20px"> <pre style="margin-top:0px; margin-bottom:0px"><code>1
2
3
4
5
6
</code></pre> </td> 
   <td style="background-color:rgb(239,239,255); border:1px solid rgb(192,192,208); vertical-align:top"> <pre style="margin-top:0px; margin-bottom:0px"><code>int compareMyType (const void * a, const void * b)
{
  if ( *(MyType*)a &lt;  *(MyType*)b ) return -1;
  if ( *(MyType*)a == *(MyType*)b ) return 0;
  if ( *(MyType*)a &gt;  *(MyType*)b ) return 1;
}</code></pre> </td> 
   <td style="vertical-align:top; padding:0px">&nbsp;</td> 
  </tr> 
 </tbody> 
</table>

其实大可以改为

int compareMyType (const void * a, const void * b)
    {
      return  *(MyType*)a <  *(MyType*)b ;
    }

qsort定义compare比较麻烦-\_-\#

int cmp(const void* x,const void* y)
    {
     if((*(Mytype*)x).s==(*(Mytype*)y).s)return (*(Mytype*)x).b<(*(Mytype*)y).b;
     else return (*(Mytype*)x).s<(*(Mytype*)y).s;
    }

**sort：**

源自于stl模板，灵活，算法较为稳定。同qsort平均排序复杂度为n\*log（n）。

函数原型：

<table style="border-bottom-width:0px; font-family:verdana,arial,helvetica,sans-serif; font-size:12px; color:black; border-collapse:collapse; width:728px"> 
 <tbody> 
  <tr style="border-bottom-width:1px; border-bottom-style:dashed; border-bottom-color:rgb(240,240,240); background-color:rgb(242,255,242)"> 
   <td style="padding-left:12px; color:rgb(0,128,0)"> <pre style="margin-top:0px; margin-bottom:0px">template &lt;class RandomAccessIterator, class Compare&gt;</pre> <pre style="margin-top:0px; margin-bottom:0px">  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);</pre> </td> 
  </tr> 
 </tbody> 
</table>

**Sort elements in range**

Sorts the elements in the range `[first,last)` into ascending order.  
  
The elements are compared using `operator<` for the first version, and comp for the second.  
  
Equivalent elements are not guaranteed to keep their original relative order (see [stable\_sort][stable_sort]).

排列指定范围内的元素，第一个默认为运算符 "<" 排序，当你排序结构体时，你可以重载运算符进行排序，但是qsort'不行+\_+。

或者你可以继续用自定义的compare。

### Parameters ###

first, last

[Random-access iterators][] to the initial and final positions of the sequence to be sorted. The range used is `[first,last)`, which contains all the elements between  first and  last, including the element pointed by  first but not the element pointed by  last.  
RandomAccessIterator shall point to a type for which  [swap][] is properly defined and which is both  *[move-constructible][]* and  *[move-assignable][]*.

首地址，末地址；注意这是半开半闭区间排序。

comp

Binary function that accepts two elements in the range as arguments, and returns a value convertible to `bool`. The value returned indicates whether the element passed as first argument is considered to go before the second in the specific  *strict weak ordering* it defines.  
The function shall not modify any of its arguments.  
This can either be a function pointer or a function object.

自定义compare

[size_t]: http://www.cplusplus.com/cstdlib:size_t
[stable_sort]: http://www.cplusplus.com/stable_sort
[Random-access iterators]: http://www.cplusplus.com/RandomAccessIterator
[swap]: http://www.cplusplus.com/swap
[move-constructible]: http://www.cplusplus.com/is_move_constructible
[move-assignable]: http://www.cplusplus.com/is_move_assignable