七种排序算法包括直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，归并排序

七种排序算法（包括直接插入排序，折半插入排序，希尔排序，冒泡排序，快速排序，简单选择排序，归并排序） 还有两道题 1./*设计并实现一个有效的对n个整数重排的算法，使得所有负数位于非负数之前，给出算法的性能分析*/ 2./*试给出一个同时找到n个元素中最大元素与最小元素的有效算法，并说明理由*/

#include
#include
#include
#include
#include
using namespace std;
#define max（ab） （（a）>（b）?（a）:（b））
#define min（ab） （（a）<（b）?（a）:（b））
class Array
{
public:int *data;
	   int size;
	   Array（）
	   {data=NULL;size=0;}
	   ~Array（）
	   {
		   delete [] data;
	   }
	   void show（）
	   {
		   for（int i=0;i		   {
			   cout<		   }cout<	   }
	  Array（int n）
	   {
		   data=new int[n];size=n;
		   int i;
		   for（i=0;i		   {
			   data[i]=-rand（）%201+100;
		   }
	   }
	  void InsertionSort（）//直接插入排序
	  {
		  int pi;
		  for（p=1;p		  {
			  int temp=data[p];
			  i=p-1;
			  while（i>=0&&data[i]>temp）
			  {
				  data[i+1]=data[i];i--;
			  }
			  data[i+1]=temp;
		  }cout<<“直接插入排序：“<	  }
	  void BinaryInsertionSort（）//折半插入排序
	  {
		  int leftmidrightiptemp;
		  for（p=1;p		  {
			  temp=data[p];
			  left=0;right=p-1;
			  while（left<=right）
			  {
				  mid=（left+right）/2;
				  if（data[mid]>temp）
				  {right=mid-1;}
				  else{left=mid+1;}
			  }
			  for（i=p-1;i>=left;i--）
			  {
				  data[i+1]=data[i];
			  }data[left]=temp;
		  }cout<<“折半插入排序：“<	  }
	  void ShellSort（）//希尔排序
	  {cout<<“希尔排序：“<		  int d=size/2ktempij;
		  while（d>=1）
		  {
			  for（k=0;k			  {
				  for（i=k+d;i				  {
					  temp=data[i];j=i-d;
					  while（j>=k&&data[j]>temp）
					  {
						  data[j+d]=data[j];
						  j-=d;
					  }
					  data[j+d]=temp;
				  }
			  }d=d/2;
		  }
	  }
	  void BubbleSort（）//冒泡排序
	  {cout<<“冒泡排序：“<		  int flag=0ij;
		  for（i=0;i		  {
			  flag=0;
			  for（j=1;j			  {
				  if（data[j]				  {swap（data[j]data[j-1]）;flag=1;}
			  }if（flag==0）
			  {return;}
		  }

	  }
	  int Partition（int startint end）//快速分割策略
	  {
		  int pivot=data[start]leftright;
		  left=start;right=end;
		  while（left<=right）
		  {
			  while（left<=right&&data[left]<=pivot）{left++;}
			  while（left<=right&&data[right]>pivot）{right--;}
			  if（left			  {
				  swap（data[left]data[right]）;left++;right--;
			  }
		  }
		  swap（data[start]data[right]）;
		  return right;
	  }
	  void QuickSort（int leftint right）//快速排序
	  {
          if（left		  {
			  int p=Partition（leftright）;
			  QuickSort（leftp-1）;
			  QuickSort（p+1right）;
		  }
	  }
	  void SelectionSort（）//简单选择排序
	  {cout<<“简单选择排序：“<		  int ikj;
		  for（i=1;i		  {
			  k=i-1;
			  for（j=i;j