编辑代码

#include <stdio.h>
int main () {
    //JSRUN引擎2.0，支持多达30种语言在线运行，全仿真在线交互输入输出。 
	printf("Hello JSRUN!   \n\n         - from C .");
	return 0;
}

void InsertSort(int n,List A)
{
    int i,j,temp;
    //指针i指向待插入元素，注意初始从A[1]开始与A[0]比较
    for(i=1;i<n;i++)
    {
        if(A[i-1]>A[i])
        {
            temp = A[i];
            //把前面所有比A[i]小的元素右移
            for(j=i-1;j>=0 && A[j]<temp;j--)
            {
                A[j+1] = A[j];
            }
            A[j+1] = temp; //最后把temp插入到位置A[j+1] (不大于A[i]元素的下一个位置)
        }
    }
}

//希尔排序
void ShellSort(int A[] ,int n)
{
    int d, i, j;
    //步长每次变化,初始为n/2,这样一个组两个元素排序
    for(d=n/2;d>0;d=d/2)
    {
        //i指向A[d+1]，因为最初肯定是比较A[1]和A[d+1]
        for(i=d+1; i<=n; ++i)
        {
            if(A[i]<A[i-d])
            {
                A[0]=A[i];//A[0]作为temp暂存A[i]的值
                for(j=i-d; j>0 && A[0]<A[j]; j-=d)
                {
                    A[j+d]=A[j];//后移
                }
                A[j+d]=A[0];
            }
        }
    }
}

//冒泡排序
void BubbleSort(int A[],int n)
{
    int i,j;//这里注意A[0]~A[n-1]为全部元素，下标要记得-1
    //每轮冒泡，j指向位置之前的元素已经排好序
    for(j=0;j<n-1;j++)
    {
        bool flag = false;//用来判断本轮冒泡是否交换过次序，没交换过则提前终止
        for(i=n-1;i>j;i--)
        {
            if(A[i-1] > A[i])
            {
                swap(A[i-1],A[i]);
                flag = true;
            }
        }
        if(flag == false)   return;
    }
}

//快速排序
void QuickSort(int A[],int low,int high)
{
    if(low < high)  //当low = high时说明划分已经最小
    {
        //计算本次划分的基准点位置 pivot_pos;
        pivot_pos = Partition(A,low,high);
        //递归实现划分左右子表
        QuickSort(A,low,pivot_pos-1);
        QuickSort(A,pivot_pos+1,high);
    }
}
void Partition(int A[],int low,int high)
{
    int pivot = A[low];//第一个元素作为基准
    while(low < high)
    {
        while(A[high]>=pivot && low < high)
        {
            high--;//high一直找到不符合的元素位置
        }
        A[low]=A[high];
        while(A[low] <=pivot && low<high)
        {
            low++;//low一直找到不符合的元素位置
        }
        A[high]=A[low];
    }
    A[low] = pivot;//基准元素存放到最终位置
    return low;//返回基准元素的位置
}

//建立大根堆
void BuildMaxHeap(int A[],int n)
{
    //从最后一个非叶结点开始，从后向前遍历调整
    for(int i=n/2;i>0;i--)
    {
        HeadAdjust(A,i,len);
    }
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[] ,int k,int len)
{
    A[0] = A[k];//A[0]内暂存根节点
    //遍历k的左孩子结点,k已经为叶结点时跳出循环
    for(int i=k*2;i<=len;i=i*2)
    {   //比较左孩子和右孩子哪个更大,i指向更大的结点
        if(A[i]<A[i+1] && i<len)
        {
            i++;
        }
        //如果孩子节点小于根节点，那么跳出循环继续看下一层孩子结点
        if(A[i] <= A[0])    break;
        else
        {
            A[k]=A[i];//把孩子的值换到根节点上
            k = i;//根节点坐标换为更大值结点的坐标，下轮循环变为以孩子结点为根节点的堆
        }
    }
    A[k] = A[0];//空余的叶结点存为原根节点的值
}

void HeapSort(int A[],int n)
{
    BuildMaxHeap(A,n);
    for(int i=len;i>1;i--)
    {
        swap(A[i],A[1]);//堆顶元素交换到末尾
        HeadAdjust(A,1,i-1);//重新调整去掉末尾元素的堆 为最大堆
    }
}


int *B= (int*)malloc(n*sizeof(int));//定义辅助数组B
//归并排序
void MergeSort(int A[],int low,int high)
{
    int mid=(low+high)/2;
    //递归实现归并排序右半部分和左半部分
    MergeSort(A,low,mid);
    MergeSort(A,mid+1,high);
    Merge(A,low,mid,high);
}

//二路归并
void Merge(int A[],int low,int mid,int high)
{
    int i,j,k;
    //把A中元素复制到B中
    for(k=low;k<=high;k++)
    {
        B[k] = A[k];
    }
    //在B中进行比较，归并到A中
    for(i=low,j=mid+1,k=low;i<=mid && j<=high;k++)
    {
        if(B[i]<=B[j])  
        {
            A[k] = B[i];
            i++;
        }
        else
        {
            A[k] = B[j];
            j++;
        }
    }
    //检测某一段是否还有未归并完的部分，直接放到A中
    while(i <= mid) A[k++] = B[i++];
    while(j <= high) A[k++] = B[j++];
}