排序算法

插入排序：

　　思路：设有一组关键字{k1,k2,k3,...}，排序一开始就认为k1是一个有序序列，让k2插入上述表长为1的有序序列，使之成为表长为2的有序序列，然后让k3插入上述表长为2的有序序列，使之成为表长为3的有序序列，以此类推，最后让kn插入上述表长为n-1的有序序列，得到一个表长为n的有序序列。

#include <iostream>
using namespace std;
void InsertSort(int a[], int size);
void main()
{
    int a[]={2,3,1,8,6,5,9,4,7};
    for(int j=0;j<9;j++)
        cout<<a[j]<<' ';
    cout<<endl;
    InsertSort(a,9);
    for(int i=0;i<9;i++)
        cout<<a[i]<<' ';
}
void InsertSort(int a[], int size)
{
    int i, j, tmp;
    for(i=1;i<size;i++)
    {
        tmp = a[i];
        j = i-1;
        while(tmp<a[j] && j>=0)
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1] = tmp;
    }
}

冒泡排序：

　　思路：

　　1.让j取n-1至1，将a[j]与a[j-1]比较，如果a[j]<a[j-1]，则将交换俩数的位置，否则不交换，第一趟比较结束后，最小的数就换到了最前面。

　　2.让j取n-1至2，重复上述比较对换操作，最终a[1]中存放的是剩余n-1个数中最小的那个。

　　3.以此类推，直到j取n-1至n-2，将a[n-1]与a[n-2]比较，小的放在a[n-2]的位置。

　　经过n-1躺冒泡处理，数组即按从小到大的顺序排列完毕。

void BubbleSort(int a[],int size)
{
    int i,j;
    for(i=1;i<size;i++)
    {
        for(j=size-1;j>=i;j--)
        {
            if(a[j]<a[j-1])
            {
                int tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }
}

归并排序：

　　思路：

　　1.把n个数看成n个长度为1的有序子表。

　　2.进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表。

　　3.重复2步，直到所有记录归并成一个长度为n的有序表。

#include <iostream>
using namespace std;

void MergeSort(int a[], int size);
void MSort(int a[], int TmpArray[], int left, int right);
void Merge(int a[], int TmpArray[], int lpos, int leftend, int rpos, int rightend);

void main()
{
    int a[]={2,3,1,8,6,5,9,4,7};
    for(int j=0;j<9;j++)
        cout<<a[j]<<' ';
    cout<<endl;
    MergeSort(a,9);
    for(int i=0;i<9;i++)
        cout<<a[i]<<' ';
}

void MergeSort(int a[], int size)
{
    //开辟与要排序数组同样大小的空间，用来存放排序好的元素
    int *TmpArray = new int[size];
    if(TmpArray!=NULL)
    {
        //将数组a的下标从0到size-1的元素进行递归
        MSort(a, TmpArray, 0, size-1);
        //删除新开辟的数组空间
        delete TmpArray;
    }
    else
        cout<<"No space for tmparray!";
}
void MSort(int a[], int TmpArray[], int left, int right)
{
    int center;
    if(left<right)
    {
        center = (left+right)/2;
        MSort(a, TmpArray, left, center);
        MSort(a, TmpArray, center+1, right);
        Merge(a, TmpArray, left, center, center+1, right);
    }
}
//对两个已经排好序的数组进行归并排序，将排序后的结果保存到TmpArray中
void Merge(int a[], int TmpArray[], int lpos, int leftend, int rpos, int rightend)
{
    int i, num, tmppos;
    num = rightend-lpos+1;
    tmppos = lpos;

    while(lpos<=leftend && rpos<=rightend)
    {
        if(a[lpos]<=a[rpos])
            TmpArray[tmppos++]=a[lpos++];
        else
            TmpArray[tmppos++]=a[rpos++];
    }

    while(lpos<=leftend)
        TmpArray[tmppos++]=a[lpos++];

    while(rpos<=rightend)
        TmpArray[tmppos++]=a[rpos++];

    for(i=0;i<num;i++,rightend--)
        a[rightend]=TmpArray[rightend];
}

堆排序：

　　思路：

　　1.建立最大堆树。从第一个非叶子节点i开始，将以i节点为跟的子树调整为堆，然后令i=i-1，再将以i节点为跟的子树调整为堆，以此类推，直到i=1，最大堆树建成。

　　2.堆排序。将堆顶元素与堆中最后一个元素交换位置，然后将前n-1元素调整为堆，交换堆顶元素与堆中倒数第二个元素，再恢复成堆，以此类推

#include <iostream>
using namespace std;
void HeapSort(int a[], int size);
void MaxHeapify(int a[], int index, int size);
void main()
{
    int a[] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
    HeapSort(a, sizeof(a)/sizeof(int));
    system("pause");
}
//堆排序
void HeapSort(int a[], int size)
{
    int i, tmp;
    //建立最大堆树
     for(int i=size/2-1;i>=0;i--)
        MaxHeapify(a, i, size);

    for(i=size-1;i>0;i--)
    {
        tmp=a[0];
        a[0]=a[i];
        a[i]=tmp;
        MaxHeapify(a, 0, i);
    }
}
//单一节点调整
void MaxHeapify(int a[], int index, int size)
{
    int l,r,tmp,largest;
    l=2*index+1;
    r=2*index+2;
    if(l<size && a[l]>a[index])//如果l>=size则数组越界
        largest=l;
    else
        largest=index;
    if(r<size && a[r]>a[largest])
        largest=r;
    if(largest!=index)
    {
        tmp=a[index];
        a[index]=a[largest];
        a[largest]=tmp;
        MaxHeapify(a, largest, size);
    }
}

快排：

　　思路：

　　1.分解。数组a[p..r]被划分成两个子数组a[a..q-1]和a[q+1..r]，使得a[a..q-1]中的每个元素都小于等于a[q]，而且，小于等于a[q+1..r]中的元素

　　2.解决。通过递归调用快速排序，对子数组a[a..q-1]和a[q+1..r]排序

#include <iostream>
using namespace std;
void quick_sort(int A[], int left, int right);
int partition(int A[], int left, int right);
void main()
{
    int a[]={2,5,9,3,5,7,4,6,11,8};
    quick_sort(a, 0, 9);
    for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;
}
void quick_sort(int A[], int left, int right)
{
    int index;
    if(left<right)
    {
        index = partition(A, left, right);
        quick_sort(A, left, index-1);
        quick_sort(A, index+1, right);
    }
}
int partition(int A[], int left, int right)
{
    int pivot=A[right];
    int i=left-1;
    for(int j=left; j<right; j++)
    {
        if(A[j]<=pivot)
        {
            ++i;
            //交换A[j]与A[i]
            int tmp=A[j];
            A[j]=A[i];
            A[i]=tmp;
        }
    }
    int temp=A[right];
    A[right]=A[i+1];
    A[i+1]=temp;
    return i+1;
}