常用排序算法：冒泡排序，快速排序，归并排序，插入排序，堆排序，统计排序。
冒泡排序伪代码：
for i = [1,n)
for (j = i; j > 0 ; j--)
if(x[i] > x[j]) swap(i,j)
插入排序伪代码：
for i = [1,n)
for (j = i; j > 0 && x[j-1] > x[j]; j--)
swap(j-1,j)
原理是，想象自己在摸牌，牌放在桌子上，我们每拿起一张，先将这张牌放在最右边，然后与手里的牌从右到左的比较，一次一次的向前交换，直到到达合适的位置。
实用C++代码：
//insert_sort.cpp
template<typename RandomAccessIterator>
void insert_sort(RandomAccessIterator first, RandomAccessIterator last)
{
if(first == last) return;
for(RandomAccessIterator i = first+1; i != last; ++i) //拿起桌子上的牌，从first+1开始拿是因为只有一张的话，本身就有序了。
linear_insert(first, i, value_type(first)); //给拿起来的牌排序，从右往左插入。
}
template<typename RandomAccessIterator>
inline void linear_insert(RandomAccessIterator first, RandomAccessIterator last,
T* )
{
T value = *last;
if(value < *first){ //最右边的值比最左边的值还要大，那就把最右边的牌放在最前面，因此其他的牌依次向后（右边）移动。
std::copy_backward(first, last, first+1); //其他的牌依次向后（右边）移动，将第一个位置留给新牌。
*first = value; //把新的牌放在第一个位置。
}
else{
unguarded_linear_insert(last, value); //依次线性的
从右往左比较，让新牌自己去找个合适的位置。
}
}
template<typename RandomAccessIterator>
inline void unguarded_linear_insert(RandomAccessIterator last, T value)
{
RandomAccessIterator next = last;
--next;
while(value < *next){ //一个一个的来比较，如果新牌比较大，就和老的牌换一下位置
*last = *next;
last = next;
--next;
}
*last = value;
/*
//Or we can make it like this:
RandomAccessIterator position = find(last, first, less_than(*last));
swap(value, copy(position, last,position+1) );
*/
}
快速排序伪代码：
void qsort(lower, uper)
if lower >= uper then
return
middle = lower
for i = [lower+1, uper]
if x[i] < x[l] then
swap(++middle, i)
swap(lower, middle)
qsort(lower, middle-1)
qsort(middle+1, uper)
实际代码，之后重新定制了这个算法，使用双边快排：
#include <iostream>
#include <bits/stl_iterator_base_types.h>
#include <algorithm>
template<typename RandomAccessIterator>
void qsort(RandomAccessIterator first, RandomAccessIterator last){
if( first == last ) return;
typename std::iterator_traits<RandomAccessIterator>::value_type tmp = *first;// *(last - 1);
RandomAccessIterator left = first;
RandomAccessIterator right = last;
while(true){
while(*left < tmp) ++left;
--right;
while(*right > tmp) --right;
if(right - left < 1) break;
std::swap(*left, *right);//iter_swap(leftm, right);
++left;
}
//std::swap(*first,*right); 这个交换可以换得比较稳定的时间复杂度，但是有些情况下，效率没有去掉此行高
qsort(first, left);
qsort(right+1, last);
}
int main(){
int x[10] = {5,6,8,4,9,1,3,7,6,33};
for(int i = 0; i < 9999999; ++i)
std::sort(x,x+10); //use time 2.272s
//qsort(x,x+10); //use time 4.072s
std::for_each(x, x+10, [](int tmp){
std::cout<<tmp<<" ";
});
return 0;
}
//程序的执行时间在linux下的测试方式是time a.out
一个题，写一个函数将第一个参数所有的小写字母转换成大写字母，结果放在第二个参数里面。函数原型为void transfer_up(const char *first, char *second);
输入限制为a-zA-Z
//单个字符小写转换为大写
char toupper( char c){
return c & 0x5F ;
}
//单个字符大写转换为小写
char tolower( char c) {
// c | 0x60也行,但不太好,因为0x60会改变结果的第7位值,根据题目意思,改变第6位值为1,而其它位保持不变就够了。
return c | 0x20 ;
}
完全方案
void transfer_up(const char *first, char *second){
if(*first == '\0' || first == (char*)0 ){
second = 0;
return;
}
do{
if(*first > 'a' && *first < 'z')
*second++ = (*first) &0x5F; //或者static int delta = 'A' - 'a'; *second++ = *first + delta;
}while(*（++first） != '\0');
*second = '\0';
}
那么大写转小写也是同样的道理了。不过是同0x20求与。