8种经典排序算法

1.冒泡排序（Bubble sort）
基本的

void BubbleSort(int A[],int n)
{
 int i,j;
 for(i=1;i<n;i++) //最多做n-1趟排序
   for(j=n-1;j>=i;j--) //从后往前冒泡，最"轻"的冒泡到最前面 
    if(A[j]<A[j-1])
      swap(A[j],A[j-1]);
}

改进的

void BubbleSort_O(int A[],int n)
{
 int i,j;
 for(i=1;i<n;i++){ //最多做n-1趟排序
   bool exchange=false; //交换标志
   for(j=n-1;j>=i;j--) //从后往前冒泡，最"轻"的冒泡到最前面 
    if(A[j]<A[j-1]){
      swap(A[j],A[j-1]);
      exchange=true;
     }
   if(!exchange) //本趟排序未发生交换，提前终止算法
      break;
 }
}

2.选择排序Selection sort

void SelectionSort(int A[],int n)
{
 int i,j;
 for(i=0;i<n-1;i++){
   int min_index=i;
   for(j=i+1;j<n;j++)
      if(A[j]<A[min_index])
         min_index=j;
   if(min_index!=i)
      swap(A[i],A[min_index]);
 }
}

3.插入排序Insertion sort

void InsertSort(int A[], int n)
{
    int i,j;
    for(i=1;i<n;i++) //依次插入R[1]，…，R[n-1]
      if(A[i]<A[i-1]){
        int insert_value=A[i];
        j=i-1;
        do { //从右向左在有序区R[0．．i-1]中查找A[i]的插入位置
            A[j+1]=A[j]; //将关键字大于A[i]的记录后移
            j--;
        }while(j>=0 && A[j]>insert_value); //当A[j]<=A[i]时终止
        A[j+1]=insert_value; //A[i]插入到正确的位置上
      }
}

4.希尔排序Shell sort

void ShellInsert(int A[],int n,int d)
{//希尔排序中的一趟排序，d为当前增量
 int i,j;
 for(i=d;i<n;i++) //将R[d．．n-1]分别插入各组当前的有序区
   if(A[i]<A[i-d]){
     int insert_value=A[i];
     j=i-d; 
     do {//查找A[i]的插入位置
        A[j+d]=A[j]; //后移记录
        j=j-d; //查找前一记录
     }while(j>=0 && A[j]>insert_value);
     A[j+d]=insert_value; //插入A[i]到正确的位置上
   } //endif
} //ShellPass

void  ShellSort(int A[],int n)
{
    int increment=n/2+(n/2%2?0:1); //增量初值,这里初始化为一个靠近n的一半的奇数 
    while(increment>0){
        ShellInsert(A,n,increment); //一趟增量为increment的Shell插入排序
        increment-=2; //求下一增量
    }
}

5.快速排序Quick sort

int Partition(int A[],int i,int j)
{
    int pivot=A[i];//中轴 
    while(i<j){
        //把右半边小于中轴的记录移到左半边 
        while(i<j && A[j]>=pivot) j--;
        if(i<j) A[i++]=A[j];
        //把左半边大于中轴的记录移到右半边 
        while(i<j && A[i]<=pivot) i++;
        if(i<j) A[j--]=A[i];
    }
    A[i]=pivot;
    return i;
}

void QuickSort(int A[],int low,int high)
{
     if(low>=high) return;
     int pivotpos=Partition(A,low,high);
     QuickSort(A,low,pivotpos-1);
     QuickSort(A,pivotpos+1,high);
}

6.堆排序Heap sort

void Heapify(int A[], int i, int HeapSize)
{
    int left = LEFT(i);
    int right = RIGHT(i);
    int largest=i;

    if (left<=HeapSize && A[largest]<A[left])
        largest = left;

    if (right<=HeapSize && A[largest]<A[right])
        largest = right;

    if (largest!=i)
    {
        swap(A[largest], A[i]);
        Heapify(A, largest, HeapSize); //调整后可能仍然违反堆性质(ps.也可以用非递归的方式)
    }
}

void BuildHeap(int A[], int n)
{
    for(int i=PARENT(n);i>=0;i--)//从最后一个非叶节点开始，往前逐个调整到根节点 
        Heapify(A, i, n);
}

void HeapSort(int A[], int n)
{
    BuildHeap(A,n);
    for (int i=n-1;i>0;i--)
    {
        swap(A[0], A[i]);
        Heapify(A,0,i-1);
    }
}

7.归并排序Merge sort

void Merge(int a[], int b[], int low, int mid, int high)
{
    int k = low;
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;
    while(k <= high )
    {
        if(begin1 > end1)
            b[k++] = a[begin2++];
        else if(begin2 > end2)
            b[k++] = a[begin1++];
        else
        {
            if(a[begin1] <= a[begin2])
                b[k++] = a[begin1++];
            else
                b[k++] = a[begin2++];
        }
    } 
}

void MergePass(int a[], int b[], int seg, int size)
{
    int seg_start_ind = 0;
    while(seg_start_ind + 2 * seg <= size) //#size - 2 * seg的意思是滿足可兩兩歸併的最低臨界值
    {
        Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, seg_start_ind + seg * 2 - 1);
        seg_start_ind += 2 * seg;
    }
    //如果一段是正好可歸併的數量而另一段則少於正好可歸併的數量
    if(seg_start_ind + seg < size)
        Merge(a, b, seg_start_ind, seg_start_ind + seg - 1, size - 1);
    else
        for(int j = seg_start_ind; j < size; j++) //如果只剩下一段或者更少的數量
            b[j] = a[j];
}
 
void MergeSort(int a[], int size)
{
    int* temp = new int[size];
    int seg = 1;
    while(seg < size)
    {
        MergePass(a, temp, seg, size);
        seg = seg*2;
        MergePass(temp, a, seg, size);
        seg = seg*2;
    }
    delete[] temp;
}

8.基数排序Radix sort

#include<iostream>
#include<vector>
#include<iterator>
#include<algorithm>
 
typedef std::vector<unsigned int> input_type;
 
void radix_sort(input_type & x)
{
    if ( x.empty() ) return; // at least one element
 
    typedef std::vector< std::vector< input_type::value_type > > buckets_type;
    buckets_type buckets(10); // allocate buckets
    // for sorting decimal numbers
 
    int pow10 = 1; // pow10 holds powers of 10 (1, 10, 100, ...)
 
    // find maximum in the array to limit the main loop below
    input_type::value_type max = *std::max_element(x.begin(), x.end());
 
    //begin radix sort
    for(; max != 0 ; max/=10, pow10*=10)
    {
        // 1. determine which bucket each element should enter
        // for each element in 'x':
        for(input_type::const_iterator elem = x.begin(); elem != x.end(); ++elem)
        {
                // calculate the bucket number:
                size_t const bucket_num = ( *elem / pow10 ) % 10;
                // add the element to the list in the bucket:
                buckets[ bucket_num ].push_back( *elem );
        }
 
        // 2. transfer results of buckets back into main array
        input_type::iterator store_pos = x.begin();
        // for each bucket:
        for(buckets_type::iterator bucket = buckets.begin(); bucket != buckets.end(); ++bucket)
        {
                // for each element in the bucket:
                for(buckets_type::value_type::const_iterator bucket_elem = bucket->begin();
                        bucket_elem != bucket->end(); ++bucket_elem)
                {
                        // copy the element into next position in the main array
                        *store_pos++ = *bucket_elem;
                }
                bucket->clear(); // forget the current bucket's list
        }
    }
}
 
int main(){
 
    input_type input;
 
    // read numbers from standard input (ends with end-of-file: ^Z / ^D, or
    // with a new line that contains something that's not a number)
    std::cout << "Enter positive numbers to sort:" << std::endl;
    std::copy(std::istream_iterator<unsigned int>(std::cin),
        std::istream_iterator<unsigned int>(), std::back_inserter(input));
 
    if ( input.end() != std::find(input.begin(), input.end(), 0) )
    {
        std::cerr << "Zero isn't positive" << std::endl;
        return 1;
    }
 
    std::cout << " ** Elements before sorting: " << std::endl;
    std::copy(input.begin(), input.end(),
        std::ostream_iterator<unsigned int>(std::cout, " "));
 
    radix_sort(input);
 
    std::cout << std::endl << " ** Elements after sorting: " << std::endl;
    std::copy(input.begin(), input.end(),
        std::ostream_iterator<unsigned int>(std::cout, " "));
    std::cout << std::endl;
 
    return 0;
}

参考：http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.3.2.4.htm
http://www.cnblogs.com/kkun/archive/2011/11/23/2260312.html
http://blog.csdn.net/deutschester/article/details/5946299