学步园

冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、基数排序、堆排序的实现：

#ifndef Sort_H_
#define Sort_H_
#include <iostream>
#include <cstring>
#include <queue>
#include <math.h>
#include <conio.h>
using namespace std;

inline void exchange(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

void print(int *array,int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<array[i]<<" ";
    }
    cout<<endl;
}

//------------------------------bubbleSort----------------------------------
//O(n^2)
void bubbleSort(int *array,int n)
{
    for(int i=n-1; i>=0; i--)
    {
        bool flag=0;
        for(int j=0; j<i; j++)
        {
            if(array[j]>array[j+1])
            {
                exchange(array[j],array[j+1]);
                flag=1;
            }
        }
        if(!flag)break;
    }
}

//-------------------------selectSort------------------------------------
//O(n^2)
void selectSort(int *array,int n)
{
    for(int i=0; i<n-1; i++)
    {
        int lowIndex=i;
        for(int j=i+1; j<n; j++)
        {
            if(array[lowIndex]>array[j])
            {
                lowIndex=j;
            }
        }
        exchange(array[i],array[lowIndex]);
    }
}

//-------------------------insertSort-----------------------------------
//O(n^2)
void insertSort(int *array,int n)
{
    for(int i=1; i<n; i++)
    {
        int cur=array[i];
        int j;
        for(j=i-1; j>=0&&cur<array[j]; j--)
        {
            array[j+1]=array[j];
        }
        array[j+1]=cur;
    }
}

//--------------------------------shellSort---------------------------------
//maybe O(n^1.5)
//修改过的插入排序
void shellSortHelp(int *array,int n,int inc)
{
    for(int i=inc; i<n; i++)
    {
        int cur=array[i];
        int j;
        for(j=i-inc; j>=0&&cur<array[j]; j-=inc)
        {
            array[j+inc]=array[j];
        }
        array[j+inc]=cur;
    }
}
//第一趟将序列分成n/2个长度至多为2的子序列，这时子序列中相邻两个元素下标差n/2
//第二趟 n/4
//直到增量为1为止，将增量存在inc[]中
void shellSort(int *array,int n)
{
    int inc[100];
    memset(inc,0,sizeof(inc));
    int count=0;
    int temp=n;
    while(temp/2)
    {
        temp=temp/2;
        inc[count++]=temp;
    }
    for(int i=0; i<count; i++)
    {
        shellSortHelp(array,n,inc[i]);
    }
}
//-----------------------------mergeSort-----------------------------------
//O(nlogn)
void merge(int*array,int *tempArray,int low,int mid,int high)
{
    //操作结果：将有子序列array[low...mid]和array[mid+1,high]归并为新的有序序列array[low...high]
    int i,j,k;
    //一个从头往后撸，一个从中间往后撸
    for(i=low,j=mid+1,k=low; i<=mid&&j<=high; k++)
    {
        if(array[i]<=array[j])
        {
            tempArray[k]=array[i];
            i++;
        }
        else
        {
            tempArray[k]=array[j];
            j++;
        }
    }
    //前边没撸完的接着撸完
    for(; i<=mid; i++,k++)
    {
        tempArray[k]=array[i];
    }
    //后边的
    for(; j<=high; j++,k++)
    {
        tempArray[k]=array[j];
    }
    //导回去
    for(i=low; i<=high; i++)
    {
        array[i]=tempArray[i];
    }
}

void mergeSortHelp(int *array,int *tempArray,int low,int high)
{
    if(low<high)
    {
        //2路归并排序
        int mid=(low+high)/2;
        mergeSortHelp(array,tempArray,low,mid);
        mergeSortHelp(array,tempArray,mid+1,high);
        merge(array,tempArray,low,mid,high);
    }
}

void mergeSort(int *array,int n)
{
    int *tempArray=new int[n];
    mergeSortHelp(array,tempArray,0,n-1);
    delete []tempArray;
}

//O(nlogn)
//-----------------------------quickSort---------------------------------
int partition(int *array,int low,int high)
{
    while(low<high)
    {
        while(low<high&&array[high]>=array[low])
        {
            high--;
        }
        exchange(array[low],array[high]);
        while(low<high&&array[low]<=array[high])
        {
            low++;
        }
        exchange(array[low],array[high]);
    }
    return low;
}

void quickSortHelp(int *array,int low,int high)
{
    if(low<high)
    {
        int pivotLoc=partition(array,low,high);
        quickSortHelp(array,low,pivotLoc-1);
        quickSortHelp(array,pivotLoc+1,high);
    }
}

void quickSort(int *array,int n)
{
    quickSortHelp(array,0,n-1);
}


//O(d*n)   d is weishu
//--------------------------------radixSort----------------------------------------
void radixSort(int *array,int n,int d)
{
    queue<int>Q[10];
    queue<int>A;
    int i,j;
    int m1=10;
    int m2=1;
    for (j=0; j<n; j++)
    {
        A.push(array[j]);
    }
    for(i=0; i<d; i++)
    {
        while(!A.empty())
        {
            int temp=A.front()%m1/m2;
            Q[temp].push(A.front());
            A.pop();
        }
        m1*=10;
        m2*=10;
        for(j=0; j<10; j++)
        {
            while(!Q[j].empty())
            {
                A.push(Q[j].front());
                Q[j].pop();
            }
        }
    }
    int k=0;
    while(!A.empty())
    {
        array[k++]=A.front();
        A.pop();
    }
}

//----------------------------------heapSort-------------------------------------
void siftAdjust(int *array,int low,int high)
{
    int adjust,i;//adjust is now to change
    for(adjust=low,i=2*low+1; i<=high; i=2*i+1)
    {
        if(i<high && array[i]<array[i+1]) i++;//cause the right child is biger so point to the right.
        if(array[adjust]>=array[i])break;
        exchange(array[adjust],array[i]);
        adjust=i;
    }
}
void heapSort(int *array,int n)
{
    int i;
    for(i=(n-2)/2; i>=0; i--)
    {
        siftAdjust(array,i,n-1);
    }
    for(i=n-1; i>0; i--)
    {
        exchange(array[0],array[i]);
        siftAdjust(array,0,i-1);
    }
}

#endif