sortdlg.cpp

这 里 是 用mfc 做的 一些排序 ,各种 排序都有

    {   
	      s.Format("%d",x[i]); 
          GetDlgItem(a[i+10] )->SetWindowText(s); 
		
    }                   //将排序后的数组元素赋给右边的编辑框 
        m_clear.EnableWindow(TRUE);   //启用”清空数据”按扭 
}

void CSortDlg::OnBinaryInsertSort() //折半排序
{
	// TODO: Add your control notification handler code here
	int x[10];         CString s; 
	int a[20]={IDC_EDIT1,IDC_EDIT2,IDC_EDIT3,IDC_EDIT4,IDC_EDIT5,IDC_EDIT6
	 ,IDC_EDIT7,IDC_EDIT8,IDC_EDIT9,IDC_EDIT10,IDC_EDIT11,IDC_EDIT12,IDC_EDIT13,
	 IDC_EDIT14,IDC_EDIT15,IDC_EDIT16,IDC_EDIT17,IDC_EDIT18,IDC_EDIT19,IDC_EDIT20};
    for(int i=0;i<10;i++ ) 
    {     
		 GetDlgItem(a[i] )->GetWindowText(s); 
           x[i ]= atoi(s); //将编辑框中的字符转化为数字后对应的赋给包含10个元素的数组 
		
    } 
	
BinaryInsertSort(x);


	for(i=0;i<10;i++ ) 
    {   
		 s.Format("%d",x[i]); 
          GetDlgItem(a[i+10] )->SetWindowText(s);
		

	
    }                   //将排序后的数组元素赋给右边的编辑框 
        m_clear.EnableWindow(TRUE);   //启用”清空数据”按扭 

}



void CSortDlg::OnQuickSort() //快速排序
{
	// TODO: Add your control notification handler code here
	 int x[10];         CString s,str; 
	 time(&start);
//	 CString ID[20]={"IDC_EDIT1","IDC_EDIT2","IDC_EDIT3","IDC_EDIT4","IDC_EDIT5"};
	 int a[20]={IDC_EDIT1,IDC_EDIT2,IDC_EDIT3,IDC_EDIT4,IDC_EDIT5,IDC_EDIT6
	 ,IDC_EDIT7,IDC_EDIT8,IDC_EDIT9,IDC_EDIT10,IDC_EDIT11,IDC_EDIT12,IDC_EDIT13,
	 IDC_EDIT14,IDC_EDIT15,IDC_EDIT16,IDC_EDIT17,IDC_EDIT18,IDC_EDIT19,IDC_EDIT20};
	//	 ,"IDC_EDIT6","IDC_EDIT7","IDC_EDIT8","IDC_EDIT9","IDC_EDIT10","IDC_EDIT11
	//	 };
    for(int i=0;i<10;i++ ) 
    {     
//		GetDlgItem(ID[0])->GetWindowText(s);
		GetDlgItem(a[i])->GetWindowText(s);
		x[i]=atoi(s);



    } 	
    quick_sort(x,0,9); //调用快速排序函数，对数组的元素排序 

 for(i=0;i<10;i++ ) 
    {   

	 s.Format("%d",x[i]); 
          GetDlgItem(a[i+10])->SetWindowText(s); 
		  
    }    //将排序后的数组元素赋给右边的编辑框 
 
        m_clear.EnableWindow(TRUE);   //启用”清空数据”按扭  
}



void CSortDlg::OnClear() 
{
	// TODO: Add your control notification handler code here

	int a[20]={IDC_EDIT1,IDC_EDIT2,IDC_EDIT3,IDC_EDIT4,IDC_EDIT5,IDC_EDIT6
	 ,IDC_EDIT7,IDC_EDIT8,IDC_EDIT9,IDC_EDIT10,IDC_EDIT11,IDC_EDIT12,IDC_EDIT13,
	 IDC_EDIT14,IDC_EDIT15,IDC_EDIT16,IDC_EDIT17,IDC_EDIT18,IDC_EDIT19,IDC_EDIT20};
	for(int i=0;i<20;i++ ) 
    {         
        GetDlgItem(a[i] )->SetWindowText(""); 
    
  
    } 
        m_clear.EnableWindow(false);     
}




void CSortDlg::bubble_sort(int x[]){
	//对数组x[]逐趟进行比较 ，遇到逆序即交换
		int i =1;int exchange=1;//当exchange为0时，则停止排序

		while((i<10 )&&exchange){//
			BubbleExchange( x, i, exchange);
			i++;
			
		}

	}
void CSortDlg::BubbleExchange(int x[],int i,int exchange){
		exchange = 0;//假定元素未交换
		for(int j =9;j>=i;j--){
		
			if(x[j-1]>x[j])//发生了逆序
			{
				
		int	temp = x[j-1];//交换
			x[j-1]=x[j];
			x[j] = temp;
			  exchange = 1;//做“发生了交换”的标志
		
			}
			}

}


void CSortDlg::InsertionSort(int x[])
{
	for(int i=1;i<10;i++)
	{
		Insert(x,i);
	}
}

void CSortDlg::Insert(int x[],int i)
{
	int temp=x[i]; int j=i;
	while (j>0&&temp<x[j-1]) 
	{
		x[j]=x[j-1];
		j--;
	}

	x[j]=temp;
}


void CSortDlg::Shellsort(int x[])
{
	int gap=10/2;//增量的初始值
	while (gap)//循环条件是gap>=1
	{
		ShellInsert(x,gap);//按增量gap划分子序列，分别进行插入排序
		gap=gap==2?1:(int)(gap/2);//缩小增量gap
	}
}


void CSortDlg::ShellInsert(int x[],const int gap)
{
	for(int i=gap;i<10;i++)//各子序列轮流执行插入排序
	{
		int temp=x[i];int j=i;//暂存待插入对象
		while (j>=gap&&temp<x[j-gap]) {//当前插入元素比位于j-gap的元素小，则位于j-gap的元
                                //素后移
			x[j]=x[j-gap];
	
			j-=gap;//后移到第j个位置，j指标前指
		}
		x[j]=temp;//插入

	}
}

void CSortDlg::MergeSort(int x[])
{
	int temp_array[10];
	int len=1;
	while (len<10) {    //归并排序
		MergePass(x,temp_array,len);//一趟两路归并后归并项长度加倍
		len*=2;
		MergePass(temp_array,x,len);
		len*=2;
	}
//	delete[] temp_array;
}

void CSortDlg::MergePass(int init_array[],int merge_array[],const int len)
{//一趟归并排序
	int i=0;
	while (i+2*len<=9) {//对长度为len的子表两两归并，直到表中剩余元素个数不足2*len为止
		merge(init_array,merge_array,i,i+len-1,i+2*len-1);
		i+=2*len;
	}
	if (i+len<=9)
	
		merge(init_array,merge_array,i,i+len-1,9);
			else						
			for (int j=i;j<=9;j++) {//若不能做归并，就复制
				merge_array[j]=init_array[j];
			}
			
	

}


void CSortDlg::merge(int init_array[],int merge_array[],const int l,const int m,const int n)
{
       int i=l,j=m+1,k=l;
	   while (i<=m&&j<=n) 
		   if (init_array[i]<=init_array[j]) {
			   merge_array[k]=init_array[i];
			   i++;k++;
		   }
		   else
		   {
			   merge_array[k]=init_array[j];
			   j++;k++;
		   }   

		   if (i<=m) 
			   for (int n1=k,n2=i;n1<=n&&n2<=m;n1++,n2++) {
				   merge_array[n1]=init_array[n2];
			   }
		 else
				   for (int n1=k, n2=j;n1<=n&&n2<=n;n1++,n2++) {
					  merge_array[n1]= init_array[n2];
				   }
		   
	   
}

void CSortDlg::BinaryInsertSort(int x[])
{
	for (int i=1;i<10;i++) 
	{
		BinaryInsert(x,i);
	}
}

void CSortDlg::BinaryInsert(int x[],int i)
{
	int left=0,right=i-1;
	int temp=x[i];
	while (left<=right) //利用折半查找找插入位置
	{
		int middle=(left+right)/2;//取中点
		if (temp<x[middle]) //插入值小于中点值
		{
			right=middle-1;//向左缩小区间
		}
		else            //否则向右缩小区间
			left=middle+1;
	}
	for (int k=i-1;k>=left;k--)//成块移动，空出插入位置
	{
		x[k+1]=x[k];
	}
	x[left]=temp;//插入
}


void CSortDlg::SelectSort(int x[])
{
	for (int i=0;i<9;i++) {
		SelectExchange(x,i);
	}
}


void CSortDlg::SelectExchange(int x[],const int i)
{
	int k=i;
	for (int j=i+1;j<10;j++) 
		if(x[j]<x[k])
			k=j;
	if(k!=i)
	{
		int temp=x[i];
		x[i]=x[k];
		x[k]=temp;
	}
}




int CSortDlg::digit(int data,int n)
{
	      int i = -1;
       for (int k = 0; k <= n;++k)

       {
              i = data % RADIX;
              data = data / RADIX;
       }
       return i;
}

void CSortDlg::SortOnDigit(int* data,int d,int left,int right)
{
	
       int c[RADIX] = {0};  //c[i]记录d位上为i的元素个数
       for (int i = left; i <= right ;i++ )
       {
              ++c[digit(data[i],d)];  //记录d位上相同的数据个数
       }
       for (int j = 1;j < RADIX ;++j )
       {
              c[j] += c[j-1];         //很明显，d位上较大（就是j的值），元素越大
                                     //c[j]记录d位上小于等于j的元素的个数
       }
       int len = right - left +1;
       int* tmp = new int[len];
       //知道了有多少元素在d位置上比自己小，则可以确定d位上的值的元素位置
       for (int k = right; k >= left; k--)
       {
              tmp[--c[digit(data[k],d)]] = data[k];
       }
       for (int m = left;m <= right ;++m )
       {
              data[m] = tmp[m - left];
      }
       delete[] tmp;
}

void CSortDlg::RadixSort(int* data,int left,int right)
{
	for (int i = 0;i < WIDTH; ++i)

       {
              SortOnDigit(data,i,left,right);
       }
}



void CSortDlg::quick_sort(int x[], int low, int high)   //快速排序函数的实现过程 
{ 

     int pivotkey;
         if(low<high)
      {
        pivotkey=partition(x,low,high);
          quick_sort(x,low,pivotkey-1);
           quick_sort(x,pivotkey+1,high);
       }

} 


int CSortDlg::partition(int x[],int low,int high)
{
  int pivotkey;

  
  pivotkey=x[low];
    while(low<high)
   {
     while(low<high&&x[high]>pivotkey)
               --high;
            x[low]=x[high];
      while(low<high&&x[low]<pivotkey)
               ++low;
            x[high]=x[low];
    }
 //     x[low]=x[0];
	  x[low]=pivotkey;
      return low;
}



void CSortDlg::HeapSort(int*list,int num)
{
	for(int i=(num-2)/2;i>=0;i--)
		FiltDown(list,i,num-1);
	for(i=num-1;i>=1;i--)
	{
		int temps=list[0];
		list[0]=list[i];
		list[i]=temps;
		FiltDown(list,0,i-1);
//		if(m_mark==1)
//		show(list);
	}
}

void CSortDlg::FiltDown(int*list,int i,int end)
{
	int c=i;int ch=2*i+1;
	int temp=list[i];
	while(ch<=end)
	{
		if(ch<end&&list[ch]<list[ch+1])
			ch++;
		if(temp>=list[ch])break;
		else
		{
			list[c]=list[ch];
			c=ch;ch=2*ch+1;
		}
	}
	list[c]=temp;
}