sort

//--------------------------------------------bubble sort--------------------------------------
void bubble_sort(int *p,int length)
{
    int i,j,temp;
    for(i = 0;i<length-1;i++) //这里i不必循环到最后一个，当前面的都排好后，第一个自然就在最小的位置了
    {
        for(j = 0;j<length-i-1;j++)
        {
            if(p[j]>p[j+1])
            {
                temp = p[j];
                p[j] = p[j+1];
                p[j+1] = temp;
            }

        }

    }

}


//--------------------------------------select sort-----------------------------------
void select_sort(int *p,int n)
{
    int i,j,mini,temp;
    for(i = 0;i<n-1;i++)// 前n-1个位置都是局部最小，那最后一个一定是最大的
    {
        mini = i;
        for(j = i+1;j<n;j++)
        {
            if(p[mini]>p[j])
                mini = j;  //精华，直接用mini作为最小的下标，就不用原思路：设置两个变量，
                           //一个记录最小值，一个记录下标
        }

        temp = p[i];
        p[i] = p[mini];
        p[mini]=temp;
    }

}


//--------------------------------------insert sort -----------------------------------------
//类比摸牌齐牌，当摸一张新牌起来（即i+1），从后往前比，当手中的牌比摸起来的牌大就往后移，停止移动后的位置就是
//摸起来的牌该在的位置
//该算法默认前面的是有序的，是从有序中插入
void insert_sort(int *p,int length)
{
   int i,temp,j;

   for(i = 1;i<length;i++)
   {
        temp = p[i];
        j = i-1;
        while(j>=0&&p[j]>temp)//不是p[j]>p[i]，因为第一次后p[i]就被p[j]覆盖了
        {
            p[j+1] = p[j];//第一步就将p[i]覆盖掉
            j--;
        }
        p[j+1] = temp;//是p[j+1]不是p[j]，最后跳出循环后p[j]指向的是比temp小的数

   }

}


//----------------------------------------shell sort----------------------------------
//希尔排序是插入排序的进化版时间复杂度突破n^2  gap 是精华，这里的算法实现不是按照gap来分一组，一组一组的
//插入排序做完，从for循环可以看出，当i++后，并不是原gap组的元素
//
void shell_sort(int *p,int length)
{
    int gap = length/2;
    int i,j,temp;
    while(gap>=1)//gap为1时即为普通插入排序
    {
        for(i = gap;i<length;i++)//这里是i++而不是i+=gap，就说明不是一组一组的用insert sort
        {
            temp = p[i];
            j = i-gap;
            while(j>=0&&p[j]>temp) //j可以等于0
            {
                p[j+gap] = p[j];
                j = j-gap;//别忘了j要变，不然循环一直出不去
            }
            p[j+gap] = temp; 

        }
        gap = gap/2; //使得算法不是n^2时间复杂度
    }

}

//----------------------------------quick sort----------------------------------------
//快排用的是递归，其中Partition函数的目的是，将当前low到high范围的第一个数定位到他有序后该有的位置
//quick sort函数调用Partition
//注意主函数调用quicksort时，参数为p,0,n-1而不是n
//quick sort函数调用Parition函数时，传入的参数也是pivot-1和pivot+1而不是pivot本身
int Paritition(int *p,int low,int high)
{
    int target =p[low];//将传入数组的第一个数作为最后的分界点数
    while(low<high)//终止时low==high
    {
        while(low<high &&p[high]>=target) high--;
        p[low] = p[high];//注意这里别写反了，第一次是从右往左找到第一个比target小的，移到左边
        while(low<high&&p[low]<=target) low++;
        p[high]=p[low];
    }
    p[low]=target;
    return low;//注意要返回low，即分界点的坐标
}

void quick_sort(int *p,int low,int high)
{
    if(low<high)
    {
        int pivot = Paritition(p,low,high);
        quick_sort(p,low,pivot-1);
        quick_sort(p,pivot+1,high);

    }

}



void main()
{
    int n;
    int *p;
    scanf("%d",&n);
    p =(int *)malloc(sizeof(int)*n);
    for(int i = 0; i<n; i++)
    {
        scanf("%d",&p[i]);
    }

    //bubble_sort(p,n);
    //select_sort(p,n);
    //shell_sort(p,n);
    //quick_sort(p,0,n-1);
    
    for(int i = 0; i<n; i++)
    {
        printf("%d ",*(p+i));

    }

}