排序算法

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <time.h>
using namespace std;
//插入排序
void Insert_Sort(int arr[10],int len)
{
    srand((unsigned)time(NULL));
    int j;
    int tmp = 0;
    for(int i = 1;i < len;i ++)
    {
        tmp = arr[i];
        j = i-1;
        while(j >=0 && arr[j] > tmp)
        {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = tmp;
    }
}
//希尔排序
void Shell_Sort(int arr[],int len,int div)
{
    int j,tmp;
    for(int i = div;i < len;i += div)
    {
        tmp = arr[i];
        j = i - div;
        while(j >=0 && arr[j] > tmp)
        {
            arr[j+div] = arr[j];
            j -= div;
        }
        arr[j + div] = tmp;
        if(i >= len-div)
        {
            div --;
            i = 0;
        }
        if(div == 0)
            break;
    }
}
void Select_Sort(int arr[10],int len)
{
    int tmp;
    for(int i = 0; i < len;i ++)
    {
        for(int j=i+1;j<len;j++)
        {
            if(arr[i]>arr[j])
            {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}
//堆排序
//建堆
void HeapAdjust(int *a,int i,int size)  //调整堆
{
    int lchild=2*i;       //i的左孩子节点序号
    int rchild=2*i+1;     //i的右孩子节点序号
    int max=i;            //临时变量
    if(i<=size/2)          //如果i是叶节点就不用进行调整
    {
        if(lchild<=size&&a[lchild]>a[max])
        {
            max=lchild;
        }
        if(rchild<=size&&a[rchild]>a[max])
        {
            max=rchild;
        }
        if(max!=i)
        {
            swap(a[i],a[max]);
            HeapAdjust(a,max,size);    //避免调整之后以max为父节点的子树不是堆
        }
    }
}

void BuildHeap(int *a,int size)    //建立堆
{
    int i;
    for(i=size/2;i>=1;i--)    //非叶节点最大序号值为size/2
    {
        HeapAdjust(a,i,size);
    }
}

void Heap_Sort(int arr[],int len)
{
    int i;
    BuildHeap(arr,len);
    for(i=len;i>=1;i--)
    {
        //cout<<a[1]<<" ";
        swap(arr[1],arr[i]);       //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
        //BuildHeap(a,i-1);        //将余下元素重新建立为大顶堆
        HeapAdjust(arr,1,i-1);     //重新调整堆顶节点成为大顶堆
    }
}
void Bubble_Sort(int arr[],int len)
{
    for(int i = 0;i < len;i ++)
    {
        for(int j = 0;j < len-i;j ++)
        {
            if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);
        }
    }
}
//快速排序
void Quick_Sort(int arr[],int left,int right)
{
    if(left<right)
    {
        int i = left;
        int j = right;
        int x=arr[left];
        while(i<j)
        {
            while(i < j && arr[j] > x)
                j--;
            arr[i]=arr[j];
            while(i < j && arr[i] < x)
                i++;
            arr[j]=arr[i];
        }
        arr[i] = x;
        Quick_Sort(arr,left,i-1);
        Quick_Sort(arr,i+1,right);
    }
}
//归并排序
void mergeSort(int a[], int l, int r) { //  8, 5, 4, 9, 2, 3, 6
    if(l >= r) return;   // exit.
    int mid = (l+r) / 2; // overflow  <->  l + (r-l)/2
    mergeSort(a, l, mid);
    mergeSort(a, mid+1, r);
    int *arr = new int[r-l+1];
    int k = 0;
    int i = l, j = mid + 1;
    while(i <= mid && j <= r) {
        if(a[i] <= a[j]) {
            arr[k++] = a[i++];
        }
        else {
            arr[k++] = a[j++]; // ans += (mid-i+1);
        }
    }
    while(i <= mid) arr[k++] = a[i++];
    while(j <= r) arr[k++] = a[j++];
    for(int i = l; i <= r; i++) {
        a[i] = arr[i-l];
    }
    delete []arr;
}
int main()
{
    int arr[10];
    //随机生成小于10的数组
    for(int i = 0;i < 10;i ++)
        arr[i] = rand()%10;

    for(int i = 0;i < 10;i ++)
        printf("%d\t",arr[i]);
    //插入排序
    //Insert_Sort(arr,10);
    //for(int i = 0;i < 10;i ++)
        //printf("%d\t",arr[i]);
    //shell 排序
    //Shell_Sort(arr,10,3);
    //选择排序
    //Select_Sort(arr,10);
    //冒泡排序
    //Bubble_Sort(arr,10);
    //堆排序
    //Heap_Sort(arr,10);
    //快速排序
    //Quick_Sort(arr,0,9);
    //归并排序
    mergeSort(arr,0,9);
    //排完序输出
    for(int i = 0;i < 10;i ++)
        printf("%d\t",arr[i]);
    return 0;
}