`
缥缈孤鸿
  • 浏览: 41865 次
  • 性别: Icon_minigender_1
  • 来自: 大连
最近访客 更多访客>>
社区版块
存档分类
最新评论

c++实现的一些排序算法

    博客分类:
  • C++
阅读更多
最近用c++简单实现了一些排序算法,记下来,以便以后用到


//合并排序全代码

void merge (int a[], int low, int high)
{  
   int i, j, k = -1; 

for (i=low, j=(low+high)/2+1; i<=(low+high)/2||j<=high;   )
{  
   if ( i>(low+high)/2 )  
   {
    b[++k]=a[j++]; 
   }
      else if (j>high) 
   {
    b[++k]=a[i++]; 
   }
      else if (a[i]>=a[j]) 
   {
    b[++k]=a[j++]; 
   }
      else   b[++k]=a[i++];
} 
k=0; 
for(i=low; i<=high; i++) 
{
   a[i]=b[k++]; 
}
} 


void mergeSort(int a[], int low, int high)
{ 
if ( high > low)
{
   mergeSort(a, low, (low+high)/2);
   mergeSort(a, 1+(low+high)/2, high);
   merge(a, low, high);
}
}
//直接插入排序
void insertSort(double a[],int n)
{
  int i,j;
  double k;
  for(i=1;i<n;i++)
  {
    if(a[i]<a[i-1])
	{
		k=a[i];
		for(j=i-1;a[j]>k && j>=0;j--)
			a[j+1]=a[j];
		a[j+1]=k;
	}
  }
}
//折半插入排序
void binsertSort(double a[],int n)
{
   int i,j,m,low,high;
   double k;
   for(i=1;i<n;i++)
   {  
	   k=a[i];
	   low=0;
	   high=i-1;
    
	  while(low<=high)
	  {
	     m=(low+high)/2;
			 if(k<a[m])
				 high=m-1;
			 else low=m+1;

	  }
	  for(j=i-1;j>=high && j>=0;j--)
			a[j+1]=a[j];
	        a[high+1]=k;
	      
   }

 }
//快速排序
//分割函数
int Partition(double  a[],int n,int low,int high)
{
  double k=a[low];
  while(low<high)
  {
    while(low<high && a[high]>=k)--high;
	a[low]=a[high];
	while(low<high && a[low]<=k)++low;
	a[high]=a[low];
  }
  a[low]=k;
  return low;
}
void quitSort(double a[],int n,int low,int high)
{
	int key;
  if(low<high)
  {
    key=Partition(a,n,low,high);
	quitSort(a,n,low,key-1);
    quitSort(a,n,key+1,high);
  }
}
//堆排序
//筛选算法
void sift(double a[],int k,int m)
{
    int i=k,j=i*2;
	while(j<=m-1)
	{
	   if(j<m && a[j]<a[j+1])j++;
	   if(a[i]<a[j])
	   {
	      double temp=a[i];
		  a[i]=a[j];
		  a[j]=temp;

		  i=j;
		  j=i*2;
	   }
	   else break;
	}
}
void heapSort(double a[],int n)
{
   int k=(n-1)/2;
   for(int i=k;i>=1;i--)
	   sift(a,i,n-1);
   for(int j=n-1;j>1;j--)
   {
      double temp=a[1];
	  a[1]=a[j];
	  a[j]=temp;
	  sift(a,1,j-1);
   }
}
int main()
{
	int i;
	double a[9]={23,56,12,3,58,62,18,36,18};
	double b[9]={23,56,12,3,58,62,18,36,18};
	double c[9]={23,56,12,3,58,62,18,36,18};
	int d[9]={23,56,12,3,58,62,18,36,18};
	double e[10]={0,23,56,12,3,58,62,18,36,18};
	cout<<"直接插入排序";
	insertSort(a,9);
	for(i=0;i<9;i++)
		cout<<a[i]<<"  ";
	cout<<endl;
	cout<<"折半插入排序";
   binsertSort(b,9);
	for(i=0;i<9;i++)
		cout<<b[i]<<"  ";
	cout<<endl;
	cout<<"合并排序";
	mergeSort(d,0,8);
	for(i=0;i<9;i++)
		cout<<d[i]<<"  ";
	cout<<endl;
	cout<<"快速排序";
	quitSort(c,9,0,8);
	for(i=0;i<9;i++)
		cout<<c[i]<<"  ";
	cout<<endl;
	cout<<"堆排序";
	heapSort(e,10);
	for(i=0;i<10;i++)
		cout<<e[i]<<"  ";

	return 0;
}

结果[img]

[/img]

 public static void sort(int[] array,int size)       {           int i,j,temp;           for(i=0;i<size;i++)           {               for(j=0;j<size-i-1;j++)               {                   if(array[j]>array[j+1])                   {                       temp = array[j];                       array[j] = array[j+1];                       array[j+1] = temp;                   }                   System.out.println(Arrays.toString(array));                                  }               System.out.println("第"+i+"次----------------------");                          }       }  
分享到:
评论

相关推荐

    C++堆排序实现算法

    简单的堆排序算法:以定长数组为例,动态数组等可以以此类推

    C++实现常用排序算法

    本文将深入探讨C++实现的几种常见排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序以及堆排序。 1. **冒泡排序**: 冒泡排序是一种简单的排序算法,它重复地遍历待排序的数列,一次比较两个元素,如果...

    Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序

    在`array_sort`这个项目中,可能包含了实现这些排序算法的C++源代码文件和Verilog模块。通过阅读和分析这些代码,可以深入理解各种排序算法的内部工作原理,以及如何在不同层面(软件和硬件)实现它们。同时,这也为...

    C++实现各种排序算法.zip

    本资料包"**C++实现各种排序算法.zip**"提供了C++语言实现的多种排序算法,这对我们深入理解和运用这些算法具有重要意义。 首先,让我们探讨一下**排序算法**的基本概念。排序是指将一组数据按照特定顺序排列的过程...

    C++实现十大排序算法.rar

    C++实现十大排序算法.rar

    总结了各种排序算法,并用C++代码实现,并有演示

    本资源"总结了各种排序算法,并用C++代码实现,并有演示",提供了丰富的学习材料,包括不同类型的排序算法以及它们的C++实现,还有可能的可视化演示,帮助理解每种算法的工作原理。 首先,让我们逐一了解常见的排序...

    C++数据结构排序算法

    C++数据结构排序算法总结 在计算机科学中,排序算法是最基本和最重要的算法之一。在实际应用中,排序算法广泛应用于各种领域,如数据分析、机器学习、数据库管理等。C++数据结构排序算法总结将为您提供详细的排序...

    C++语言的算法实现包括插入排序冒泡排序堆排序快速排序

    本文将深入探讨四种在C++中实现的常见排序算法:插入排序、冒泡排序、堆排序和快速排序。这些算法各有特点,适用于不同的场景,理解并掌握它们对于提升编程能力至关重要。 1. **插入排序**: 插入排序是一种简单的...

    用C++语言基数排序算法实现

    该算法用C++语言实现了基数排序算法,已经调试通过,在Linux系统环境中运行结果正常

    C++实现堆排序

    1、 实现堆排序算法。 2、 理论分析并实验验证堆排序算法的时间复杂度。

    C++实现希尔、快速、堆排序、归并排序算法

    本文将详细介绍C++中实现的希尔排序、快速排序、堆排序和归并排序这四种经典排序算法。 希尔排序,由Donald Shell于1959年提出,是一种改进的插入排序。它的基本思想是通过设置一个增量序列,将待排序的元素按照...

    快速排序算法c++实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法,通过选取一个“基准”元素,将数组分为两个子数组,使得左边的元素都小于基准,右边的元素都大于基准,然后对这...

    C++实现各种排序算法排序性能的比较,如果有更好的算法,替换相应的算法就可以

    标题中的"C++实现各种排序算法排序性能的比较"指出,这是一个关于C++编程的项目,其核心内容是对比不同排序算法的效率。排序是计算机科学中的基础问题,它在数据分析、数据库管理等领域有着广泛的应用。C++作为一种...

    3种排序算法可视化程序 c++ 算法

    在这个C++实现的项目中,我们有三种经典的排序算法被可视化:冒泡排序、插入排序和选择排序。这些算法的可视化能够帮助我们更好地理解它们的工作原理。** ### 冒泡排序 冒泡排序是最基础的排序算法之一,它通过重复...

    用C++实现各种排序算法

    本文将详细探讨在C++语言中实现的几种常见排序算法,包括快速排序、Shell排序、堆排序、折半排序、冒泡排序、归并排序以及B树的实现,并对直接排序法进行简要介绍。 1. **快速排序**:由C.A.R. Hoare提出的快速排序...

    C++实现选择排序算法

    下面将详细介绍如何用C++实现选择排序算法: 1. **算法步骤**: - 初始化:遍历整个数组,找到当前未排序部分的最小元素。 - 交换:将找到的最小元素与未排序部分的第一个元素进行交换。 - 更新:将已排序部分的...

    C++10大排序算法PPT及代码示例,视频动图演示

    本资源包涵盖了C++实现的十大经典排序算法,包括PPT讲解和代码示例,以及生动的视频动图演示,帮助学习者深入理解各种排序算法的原理和实际应用。** 1. **冒泡排序**(Bubble Sort)是最基础的排序算法之一,通过...

    7种常用排序算法实现(C++)(冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序)

    这里我们将深入探讨七种常用的排序算法,并通过C++语言实现它们。这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之...

    C++实现6种排序算法对四种类型数据排序

    本主题聚焦于使用C++实现六种不同的排序算法,并应用于四种不同类型的数据。这些排序算法包括了冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,它们各自有其独特的性能特征和适用场景。以下是对这六种...

Global site tag (gtag.js) - Google Analytics