前言：qsort和sort都是系统提供给我们的可以直接排序的两个函数。在面试的时候手写代码需要排序的时候可以直接去调用这两个函数 。我自己在A题目的时候遇到了排序函数的问题，用了sort ， AC不过，用了qsort竟然过了。。搞不懂。来看一下两者的区别，并分析下当时出现的错误原因。
qsort：
函数原型：void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));
函数作用：使用compar函数来对 从base地址开始的num 个元素（第二个参数）来进行排序，compar决定排序的方式。函数不返回任何值，修改了base指针指向的数组的内容。
函数参数：
- base 指向要排序数组的第一个对象，被转换为一个void*指针.
- num 无符号整形变量，从base指针指向的对象开始有多少个对象需要排序。
- size 无符号整形变量，代表数组中每个元素的大小
- compar 指向一个比较两个元素大小的函数。这个函数将会被qsort函数重复的调用来比较两个元素的大小，它的定义方式是固定的。
compar 的定义方式应该是 int compar (const void* p1, const void* p2); 需要两个参数，都会被转化为const void*，会根据返回值的大小来决定排序的方式。
如果返回值 <0,则按照从小到大排序，如果返回值大于0，则从大到小排序，返回值等于0，则应该是按从小到大排序。
Code Example:
//
// main.cpp
// sortAndqsortExample
//
// Created by mini on 12/20/13.
// Copyright (c) 2013 mini. All rights reserved.
//
#include <iostream>
#include <string.h>
using namespace std;
int cmp (const void * a, const void * b)
{
if ( *(int*)a < *(int*)b )
return 1;
else
return -1;
}
int main(int argc, const char * argv[])
{
int a[ ] = {5, 211111111, -211111111, 7, 8, 2};
qsort(a, 6, sizeof( a[ 0 ] ), cmp);
for( int i = 0; i < 6; i++ )
cout << a[ i ] << " ";
cout << endl;
return 0;
}
Output: 211111111 8 7 5 2 -211111111
时间复杂度为 nlog2（n）.
这里有一个问题，cmp函数最好不要写成这个样子：
int cmp (const void * a, const void * b)
{
return *( int * ) a - *( int * )b;
}
如果直接写成这个样子的话，当排序的数组值很大的时候，有可能会造成溢出的问题。看下面的代码：
#include <iostream>
#include <string.h>
using namespace std;
int cmp (const void * a, const void * b)
{
return *( int * ) a - *( int * )b;
}
int main(int argc, const char * argv[])
{
int a[ ] = {5, 2147483646, -2147483646, 7, 8, 2};
qsort(a, 6, sizeof( a[ 0 ] ), cmp);
for( int i = 0; i < 6; i++ )
cout << a[ i ] << " ";
cout << endl;
return 0;
}
输出会是这样的： 5 7 8 2147483646 -2147483646 2 ，因为那2个大的值会造成溢出。和我们原先想要的效果不一样。
结构体的排序：
#include <iostream>
#include <string.h>
using namespace std;
struct Student{
int number;
int age;
char s;
};
int cmp (const void * a, const void * b)
{
struct Student * p = (Student *) a;
struct Student * q = (Student *) b;
if( p -> number < q -> number )
return -1;
else if ( p ->number > q -> number )
return 1;
else
return ( p -> age < q -> age ) ? -1 : 1;
}
int main(int argc, const char * argv[])
{
Student A[ 5 ];
A[ 0 ] = { 5,8,'c'};
A[ 1 ] = { 8,8,'c'};
A[ 2 ] = { 6,6,'c'};
A[ 3 ] = { 6,8,'c'};
A[ 4 ] = { 2,8,'c'};
qsort( A, 5, sizeof(Student), cmp );
for( int i = 0; i < 5; i++ )
cout << A[ i ].number << " " << A[ i ].age << " " << A[ i ].s << endl;
return 0;
}
output：
2 8 c 5 8 c 6 6 c 6 8 c 8 8 c
先按照number排序，如果number相等，按照age 从小到大排序.
Sort
sort 排序算法是STL中提供给我们的。STL中提供了好多个排序的算法
1. 所有STL sort算法函数的名字列表:
函数名 功能描述
sort 对给定区间所有元素进行排序
stable_sort 对给定区间所有元素进行稳定排序
partial_sort 对给定区间所有元素部分排序
partial_sort_copy 对给定区间复制并排序
nth_element 找出给定区间的某个位置对应的元素
is_sorted 判断一个区间是否已经排好序
partition 使得符合某个条件的元素放在前面
stable_partition 相对稳定的使得符合某个条件的元素放在前面
如果你需要自己定义比较函数，你可以把定义好的仿函数作为参数传入，每种算法都支持比较函数。
2.sort 函数
sort的两种定义：
template< class RandomIt > void sort( RandomIt first, RandomIt last ); (1) template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp );
这个函数的作用是排序 范围[first，last)以递增的形式（默认情况下）。不能保证相同的元素排序后前后次序不发生变化，就是不稳定排序。如果你想自定义函数也是可以的。
自定义函数必须定义为下列形式：
bool cmp(const Type1 &a, const Type2 &b);
参数的形式不一定要定义为const &，但是在cmp函数中不能修改参数的值。 函数返回true 如果第一参数小于第二个参数。
Code Example:
#include <algorithm>
#include <iostream>
#include <string>
#include <array>
using namespace std;
bool cmp( const int & a, const int & b ){
return a < b;
}
int main()
{
array< int, 10 > s ={ 5,2,3,8,1,9,0,7,4,6};
sort( s.begin(), s.end(), less< int >());
//sort( s.begin(), s.end() );
for( int a: s )
cout << a << " ";
cout << endl;
sort( s.begin(), s.end(), greater< int >());
for( int a: s )
cout << a << " ";
cout << endl;
sort( s.begin(), s.end(), cmp);
for( int a: s )
cout << a << " ";
cout << endl;
return 0;
}
输出：
0 1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
partial_sort：
两种定义：
template< class RandomIt > void partial_sort( RandomIt first, RandomIt middle, RandomIt last ); (1) template< class RandomIt, class Compare > void partial_sort( RandomIt first, RandomIt middle, RandomIt last, Compare comp ); (2)
这个函数的作用是[first，middle)区间中包含排序后的函数，这个排序函数也是不稳定函数，不能保证相同值的元素在排序后的前后次序不发生变化。 自定义函数和sort 类似。
时间复杂度：(last-first)log(middle-first))
Code Example：
#include <algorithm>
#include <iostream>
#include <string>
#include <array>
using namespace std;
bool cmp( const int & a, const int & b ){
return a < b;
}
int main()
{
array< int, 10 > s ={ 5,2,3,8,1,9,0,7,4,6};
partial_sort( s.begin(), s.begin() + 4, s.end());
for( int a: s )
cout << a << " " ;
cout << endl;
return 0;
}
output： 0 1 2 3 8 9 5 7 4 6 ，我们看到了 前 4个是排序好的，后面的是未排序的，次序和原先也不同，其实根据名字也可以看出来这个函数的作用。部分排序。。
3.stable_sort 稳定排序
使用方法和sort 类似，只不过这个排序是稳定的，直接上代码：
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
struct Employee {
Employee(int age, std::string name) : age(age), name(name) { }
int age;
string name; // Does not particpate in comparisons
};
bool operator<(const Employee &lhs, const Employee &rhs) {
return lhs.age < rhs.age;
}
int main()
{
std::vector<Employee> v = {
Employee(108, "Haha"),
Employee(108, "Zaphod"),
Employee(108, "Ford"),
Employee(32, "Arthur"),
};
stable_sort(v.begin(), v.end());
for (const Employee &e : v) {
cout << e.age << ", " << e.name << '\n';
}
}
Output:
32, Arthur 108, Haha 108, Zaphod 108, Ford
可以看出值等于108的三个元素的前后次序是没有变化的，所以它叫稳定排序。
nth_element
两种定义:
template< class RandomIt > void nth_element( RandomIt first, RandomIt nth, RandomIt last ); (1) template< class RandomIt, class Compare > void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp ); (2)
函数作用：找到排序后在第n个位置上的元素，也就是说在n位置前面的元素都比n这个位置的元素小或者等于，n位置后面的元素都会大于等于这个元素。
Code Example：
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
std::vector<int> v{5, 6, 4, 3, 2, 7, 9, 1, 0, 8};
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "The median is " << v[v.size()/2] << '\n';
for( int a : v )
cout << a << " ";
cout << endl;
std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());
std::cout << "The second largest element is " << v[1] << '\n';
for( int a : v )
cout << a << " ";
cout << endl;
}
OutPut:
The median is 5 0 1 2 3 4 5 6 7 9 8 The second largest element is 8 9 8 7 6 5 4 3 2 1 0
可以看出来，5前面都是比它小的，后面的都是比它大的。但是并不一定是排序的。
需要注意的两点：
1：qsort和sort 使用的时候，自定义函数的函数原型是不同的。
qsort 自定义函数函数原型：int compar (const void* p1, const void* p2);
sort 自定义函数函数原型： bool compare（const Type& p1, const Type& p2);
在自定义函数的时候应该完全遵循这两种函数原型。
2. qsort 和sort 排序的空间 是由区别的。
qsort 函数中会提供一个值n ，表示从头开始算，排序 n个元素
sort 函数会由一个区间[first, last), 记住这是一个半开闭区间，所以last的值要特殊的注意下。
OK，打完收工。