排序

数据结构 排序 yudesong

#include <iostream>
using namespace std;
//插入排序 
void InsertSort(int num[],int n)
{
    int i,j,tmp;
    for(i=1;i<n;i++)
    {
        j=i;
        tmp = num[i]; //哨兵
        //找到位置之后元素后移 
        while(j>0 && num[j-1]>tmp)
        {
            num[j] = num[j-1];    
            j--;
        }   
        num[j] = tmp;
    }
}
//希尔排序 
void ShellSort(int num[],int n)
{
    int i,j,tmp;
    int d;
    for(d=n/2;d>=1;d=d/2)   //以d/2为增量 
    {
        for(i=d+1;i<n;i++)
        {
            tmp = num[i]; //哨兵 
            for(j=i-d;j>0 && num[j]>tmp;j=j-d)   //插入排序 
                num[j+d] = num[j];
            num[j+d] = tmp;   
        }
    }
}
//冒泡排序 
void BubbleSort(int num[],int n)
{
    int i,j,tmp;
    for(i=0;i<n-1;i++)  //比较次数 
    for(j=n-1;j>=i;j--) //循环比较 
    {
        if(num[j-1]>num[j])      
        {
            tmp = num[j];
            num[j] = num[j-1];
            num[j-1] =tmp; 
        }       
    }
}
//快速排序 
void QuickSort(int num[],int left,int right)
{
    int i = left;
    int j = right;
    int tmp;
    if(left>right) 
    return ;   
    while(i<j)
    {
        while(i<j && num[i]<=num[j]) j--;
        if(i<j)
        {
            tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
            i++;
        }   
        while(i<j && num[i]<=num[j]) i++;
        if(i<j)
        {
            tmp = num[i];
            num[i] = num[j];
            num[j] = tmp;
            j--;
        }
    }
    QuickSort(num,left,i-1);
    QuickSort(num,i+1,right);
}
void HeapAdjust(int num[],int i,int n)
{
    int left = 2*i+1;
    int right = 2*i+2;
    int target = i;
    int tmp;
    if(i<=(n/2)-1)
    {
        if(left<n && num[left]>num[target])
        {
            target = left;
        }
        if(right<n && num[right]>num[target])
        {
            target = right;
        }
        if(target!=i)
        {
            tmp = num[target];
            num[target] = num[i];
            num[i] = tmp;
            HeapAdjust(num,target,n); 
        }
    }
}
//建堆 
void BuildHeap(int num[],int n) 
{
    int i;
    int tmp;
    //所有非叶子结点 
    for(i=(n/2)-1;i>=0;i--)
    {
        HeapAdjust(num,i,n);        
    }   
}
//堆排序 
void HeapSort(int num[],int n)
{
    int i;
    int tmp;
    BuildHeap(num,n);
    for(i=n-1;i>0;i--)
    {
        tmp = num[0];
        num[0] = num[i];
        num[i] = tmp;
        HeapAdjust(num,0,i-1);  
    }
} 
void Merge(int num[],int tmp[],int start,int mid,int end)
{
    int i = start;
    int j = mid+1;   
    int k = start;
    while(i!=mid+1 && j!=end+1)
    {
        if(num[i]<num[j]) tmp[k++] = num[i++];
        else
            tmp[k++] = num[j++];
    }
    while(i!=mid+1) tmp[k++] = num[i++];
    while(j!=end+1) tmp[k++] = num[j++];
    for(i=start;i<=end;i++)
    num[i] = tmp[i];
}
//归并排序 
void MergeSort(int num[],int tmp[],int start,int end)
{
    int mid;   
    if(start<end)
    {
        mid = (start+end)/2;
        MergeSort(num,tmp,start,mid);
        MergeSort(num,tmp,mid+1,end);
        Merge(num,tmp,start,mid,end);
    }
} 
int main()
{
    int num[9]={1,9,4,7,8,6,2,5,3};    
//  InsertSort(num,9);
//  BubbleSort(num,9);
//  ShellSort(num,9);
//  QuickSort(num,0,8);
//  HeapSort(num,9);
    int tmp[9];
    MergeSort(num,tmp,0,8);
    for(int i=0;i<9;i++)
      cout<<num[i]<<" ";
}