HNU内排序实验

时间过得真快啊，又到了写数据结构实验的时候。这次是内排序。

【问题描述】

    输入若干整数，使用shell排序后输出。

【输入形式】

    输入的第一行一个整数 n （ 0 < n ≤ 107），表示待排序的数的个数。

    接下来的一行，包含 n 个整数，表示待排序的数据。

【输出形式】

    输出为一行 n 个数，表示已排序后的数。

【样例输入】

5
5 4 3 2 1

【样例输出】

1 2 3 4 5

#  include  
#  include  
using  namespace  std;



void  inssort(int  *A,  int  n,  int  incr)
{//可以看到这里完成的是插入排序，跳跃间隔为incr，复杂度为n方
        for(int  i  =  incr;  i  <  n;  i  +=  incr)
                for(int  j  =  i;  (j  >=  incr)  &&  (A[j]  <  A[j  -  incr]);  j  -=  incr)
                        swap(A[j],  A[j  -  incr]);
}

void  shellsort(int  *A,  int  n)
{
        for(int i=n/2;i>2;i/=2) //for each incr incr递增从2到n
		for(int j=0;j>  a[i];

        shellsort(a,  n);

        for(int  i  =  0;  i  <  n;  i++)
                cout  <<  a[i]  <<  "  ";
        cout  <<  endl;
        return  0;
}

这一版本shellsort有点问题，在CG高并发的时候会run time error，应该是复杂度太高了（n立方）

【问题描述】

    输入若干整数，使用归并排序后输出。

【输入形式】

    输入的第一行一个整数 n （ 0 < n ≤ 107），表示待排序的数的个数。

    接下来的一行，包含 n 个整数，表示待排序的数据。

【输出形式】

    输出为一行 n 个数，表示已排序后的数。

【样例输入】

5
5 4 3 2 1

【样例输出】

1 2 3 4 5

#  include  
#  include  
using  namespace  std;


void  mergesort(int  *A,  int  *temp,  int  left,  int  right)
//shaffe教材给出的mergesort非常优美，值得记下来
{
if(left==right) return;

int mid=(left+right)/2;//

mergesort(A,temp,left,mid);
mergesort(A,temp,mid+1,right);

for(int i=left;i<=right;i++) //copy
temp[i]=A[i];

int i1=left;int i2=mid+1;
for(int curr=left;curr<=right;curr++) {
    if(i1=mid+1)//left exhausted 左子串用完补右子串
        A[curr]=temp[i2++];
    else if(i2>right)//right exhausted 右子串用完补左子串
        A[curr]=temp[i2++];
    else if(temp[i1]>  a[i];

        mergesort(a,  temp,  0,  n  -  1);          

        for(int  i  =  0;  i  <  n;  i++)
                cout  <<  a[i]  <<  "  ";
        cout  <<  endl;
        return  0;
}

我太菜了，其实CG上没做出来，考试的时候才做出来的。我在CG上做错的是，左右用完再补的地方不理解，以及递归终止条件没写对。
递归终止条件是左等于右，这从归并排序原理可以看到，将每个子串分到一个元素就停止。

归并排序补充一个非递归实现版本
摘自CSDN用户 W1024201

void Merge(int arr[], int len, int gap)//gap：代表合并的两个组中单独的组个数是多少(几几合并的几)
{
	//第一步，先整出来辅助空间brr
	int* brr = (int*)malloc(len * sizeof(int));
	assert(brr != NULL);
	int i = 0; //i是辅助空间brr的下标   代表下一个值插入位置
 
	int low1 = 0;//左手的左边界
	int high1 = low1 + gap - 1;//左手的右边界
	int low2 = high1 + 1;//右手的左边界
	int high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;//右手的右边界
 
	while (low2 <= high2)//确保左手和右手都抓到值（左右手都不空），只要右手还有值，左手肯定抓满值了
	{
        //代表着，融合比较过程中，左右手还不空
        //有一个空了，就不用比较了，直接向brr挪动另一个手中的数据即可
		while (low1 <= high1 && low2 <= high2)
		{
			if (arr[low1] <= arr[low2])//如果左手的第一个值 <= 右手的第一个值
			{
				brr[i++] = arr[low1++];//将左手的第一个值放到brr中
			}
			else//如果左手的第一个值 > 右手的第一个值
			{
				brr[i++] = arr[low2++];//将右手的第一个值放到brr中
			}
		}
 
		//当内层while循环退出，代表着肯定有一个手空了
		//这里可以不用判断到底哪个手空了，简单粗暴一点（两个数组都调用一下，将其剩余数据向brr挪动）
		while (low1 <= high1)//将左手剩余数据向brr中挪动
		{
			brr[i++] = arr[low1++];
		}
		while (low2 <= high2)//将右手剩余数据向brr中挪动
		{
			brr[i++] = arr[low2++];
		}
 
		//左手右手数据处理完毕，平移，让左手右手再抓两个组
		low1 = high2 + 1;
		high1 = low1 + gap - 1;
		low2 = high1 + 1;
		high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;
	}
 
	//此时，代表着处理到最后一组了：这时候退出有两种情况：1.左右手都没有抓到值 2.左手不空，右手空 
	//会不会存在第三种情况：左手空，右手不空？  这种情况不存在
	//那么怎么处理上面两种可以出现的情况：第一种皆大欢喜，不用管了
	//                                    第二种，需要处理一下
 
	//处理2：左手的值放到brr里，右手肯定为空 不用管
	while (low1 < len)//将左手剩余数据向brr中挪动  //这里是low1 
摘录的原因是，考了递归实现和非递归实现排序两趟的结果
 需要注意，递归实现和非递归实现两趟的结果并没有什么区别，我们老师认为第一趟排序结果是两两排序，第二趟是四四排序
 
3.快速排序qsort 
【问题描述】
 
    输入若干整数，使用快速排序后输出。
 
【输入形式】
 
    输入的第一行一个整数 n （ 0 < n ≤ 107），表示待排序的数的个数。

    接下来的一行，包含 n 个整数，表示待排序的数据。
 
【输出形式】
 
    输出为一行 n 个数，表示已排序后的数。
 
【样例输入】
 
5
 5 4 3 2 1
 
【样例输出】
 
1 2 3 4 5
 
#  include  
#  include  
using  namespace  std;

inline  int  findpivot(int  *A,  int  i,  int  j)
{
        return  (i  +  j)  /  2;
}
inline  int  Partition(int  *A,  int  left,  int  right,  int&  pivot)
{
        do
        {
                while(A[++left]  <  pivot);
                while((left  <  right)  &&  (pivot  <  A[--right]));
                swap(A[left],  A[right]);
        }
        while(left  <  right);
        return  left;
}
void  qsort(int  *A,  int  left,  int  right)
{
          if (left >= right)  return;
  
    int pivotidx=findpivot(A,left,right);//找界标
    swap(A[pivotidx],A[right]);//界标放在最边上
    int k=Partition(A,left-1,right,A[right]);//传左右界限参数和界标，放入划分函数
    swap(A[k],A[right]);//把界标放在界标位置（界标在par函数里一直在最右边，没动过）
    
    qsort(A,left,k-1);
    qsort(A,k+1,right);

}
int  main()
{
        int  n;
        scanf("%d",  &n);
        int  *a;
        a  =  new  int[n];

        for(int  i  =  0;  i  <  n;  i++)
                cin  >>  a[i];

        qsort(a,  0,  n  -  1);

        for(int  i  =  0;  i  <  n;  i++)
                cout  <<  a[i]  <<  "  ";
        cout  <<  endl;
        return  0;
}