`
dengqsintyt
  • 浏览: 291302 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

c++ 实现-基本排序算法

阅读更多

一直以来就很想整理一下基本的算法实现,工作太忙一直没有来得及整理。

基本排序算法:

   首先:代码实现

   一、直接插入排序

   二、冒泡排序

   三、直接选择排序

   四、希尔排序

   五、快速排序

   六、归并排序

   七、堆排序

   八、总结

 

   首先:代码实现

         1.algorith.h文件          

 

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <math.h>
#include <fstream>
#include <io.h>
#include <cstdlib>
#include <time.h>
#include <sstream>
#include <time.h>
#include <iostream>
#include <string>
#include <set>

using namespace std;

namespace algorith{

	class CAlgorith
	{

	public:
		CAlgorith(void);
	public:
		~CAlgorith(void);
	public:
		//直接插入排序
		void swap(int array[],int i,int j);
		void insertSort(int array[],int n);

		//冒泡排序
		void bubbleSort(int array[],int n);

		//直接选择排序
		void selectionSort(int array[],int n);

		//希尔排序
		void shellSort(int array[],int n);

		//快速排序
		int partition(int array[],int left,int right);
		void quickSort(int array[],int left,int right);
		void quickSort1(int array[],int left,int right);

		//归并排序
		void merge(int array[],int tempArray[],int left,int right,int middle);
		void mergeSort(int array[],int tempArray[],int left,int right);

		//堆排序
		void maxHeap(int array[],int n); //用已有数组初始化一个最大堆   
		void buildHeap();   //构建最大堆  
		void siftDown(int index);  //向下筛选法  
		void swap(int index1,int index2);  //交换位置为index1与index2的元素  
		void removeMax();  //删除堆顶的最大值--与数组最后一个元素交换位置并重新构建最大堆  
		int leftChild(int index);  //返回左孩子的位置  
		int rightChild(int index);  //返回右孩子的位置


	private:
		//关于树
		set<string> m_setDeleteForm;
		int size; //最大堆的元素数目
		int *array;//最大堆数组的首地址指针

	};
}

 

 

 

         2.algorith.cpp文件

         

#include "algorith.h"

using namespace algorith;

algorith::CAlgorith::CAlgorith(void)
{

}
algorith::CAlgorith::~CAlgorith(void)
{

}

//交换两个元素的位置
void algorith::CAlgorith::swap(int array[],int i,int j)
{
	int tmp=array[i];  
	array[i]=array[j];  
	array[j]=tmp; 

}
void algorith::CAlgorith::insertSort(int array[],int n)
{
	//第一层for循环
	for (int i=1;i<n;i++)
	{
		//关键的第二层for循环
		for (int j=i;j>0;j--)
		{
			//如果后者大于前者,交换位置-----降序
			if (array[j] > array[j-1])
			{
				swap(array,j,j-1);
			}
			else
				break;
		}
	}

}


//冒泡排序
void algorith::CAlgorith::bubbleSort(int array[],int n)
{
	for (int i =0;i<n-1;i++)
	{

		for (int j=n-1;j>i;j--)
		{
			//依次比较,把大的放在前面去
			if (array[j] < array[j-1])
			{
				swap(array,j,j-1);
			}
		}
	}
}


//选择排序,选择最小的放在前面
void algorith::CAlgorith::selectionSort(int array[],int n)
{
	for(int i =0;i<n-1;i++)
	{
		int minimum = i;
		for (int j = i+1;j<n;j++)
		{
			if (array[minimum] >array[j])
			{
				minimum = j;
			}
		}
		swap(array,i,minimum);

	}
}

/*先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。
1、先在各组内进行直接插人排序;
2、然后取第二个增量d2<d1重复上述的分组和排序,
3、直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
*/
void algorith::CAlgorith::shellSort(int array[],int n)
{
	for (int avg = n/2;avg>0;avg/=2)
	{
		for(int i =0;i<avg;i++)
		{
			for (int j= i+avg;j<n;j+=avg)
			{
				for (int k=j;k>0;k-=avg)
				{
					if (array[k] < array[k-1])
					{
						swap(array,k,k-1);
					}
				}
			}
		}
	}
}

int algorith::CAlgorith::partition(int array[],int left,int right)
{
	int mid = (left + right)/2;
	int tmp = array[mid];
	swap(array,mid,right);
	int i = left;
	int j = right;

	while(1)
	{
		//i指针向右移动,直到找到一个大于轴值的值
		if(i==j)
		{
			array[i] = tmp;
			return i;
		}

		if (array[i] > tmp)
		{
			array[j] = array[i];
			j--;
			break;
		}
		i++;
	}
	while(1)  
	{  
		/*如果i与j相遇则确定轴值位置,将其返回*/  
		if(i==j)  
		{  
			array[j]=tmp;  
			return j;  
		}  
		if(array[j]<tmp)  
		{  
			array[i]=array[j];  
			i++;  
			break;  
		}  
		j--;  
	}  
}

//快速排序
void algorith::CAlgorith::quickSort(int array[],int left,int right)
{
	if(right<=left)  
		return;  
	int pivot=partition(array,left,right);  
	quickSort(array,left,pivot-1);  
	quickSort(array,pivot+1,right);
}

//快速排序
void algorith::CAlgorith::quickSort1(int array[],int left,int right)
{
	if(left < right){
		int key = array[left];
		int low = left;
		int high = right;
		while(low < high){
			while(low < high && array[high] > key){
				high--;
			}
			array[low] = array[high];

			while(low < high && array[low] < key){
				low++;
			}
			array[high] = array[low];
		}
		array[low] = key;
		quickSort1(array,left,low-1);
		quickSort1(array,low+1,right);
	}
}


//归并排序
void algorith::CAlgorith::merge(int array[],int tempArray[],int left,int right,int middle)
{
	int index1 = left;
	int index2 = middle +1;
	int i;
	for (i = left;(index1<=middle) &&(index2 <=right);i++)
	{
		if (array[index1] < array[index2])
		{
			tempArray[i] = array[index1++];
		}
		else
		{
			tempArray[i] = array[index2++];
		}
	}

	while(index1 <= middle)
	{
		tempArray[i++] = array[index1++];
	}

	while(index2 <= right)
	{
		tempArray[i++]= array[index2++];
	}

	for(int i = left;i<= right;i++)
	{
		array[i] = tempArray[i];
	}
}

//归并排序
void algorith::CAlgorith::mergeSort(int array[],int tempArray[],int left,int right)
{
	if (left < right)
	{
		int middle = (left + right)/2;
		mergeSort(array,tempArray,left,middle);
		mergeSort(array,tempArray,middle+1,right);
		merge(array,tempArray,left,right,middle);
	}
}


//堆排序
void algorith::CAlgorith::maxHeap(int array[],int n)  
{  
	this->array=array;  
	size=n;  
	buildHeap();  
}  

void algorith::CAlgorith::buildHeap()  
{  
	for(int i=size/2-1;i>=0;i--)  
		siftDown(i);  
}  

void algorith::CAlgorith::siftDown(int index)  
{  
	int max_index=leftChild(index);  
	while(max_index<size)  
	{  
		if(max_index<size-1&&array[rightChild(index)]>array[max_index])  
			max_index++;  
		if(array[index]>array[max_index])  
			break;  
		swap(index,max_index);  
		index=max_index;  
		max_index=leftChild(index);  
	}  
}  

void algorith::CAlgorith::swap(int index1,int index2)  
{  
	int temp=array[index1];  
	array[index1]=array[index2];  
	array[index2]=temp;  
}  

void algorith::CAlgorith::removeMax()  
{  
	swap(0,size-1);  
	size--;  
	siftDown(0);  
}  

int algorith::CAlgorith::leftChild(int index)  
{  
	return index*2+1;  
}  

int algorith::CAlgorith::rightChild(int index)  
{  
	return index*2+2;  
} 

  

 

         3.mainTest.cpp文件           

 

#include "algorith.h"

using namespace algorith;

int main(int argc,char * argv[])
{
	CAlgorith calgorith;
	//int array[5]={3,1,2,5,4};
	int array[8]={6,8,7,3,1,2,5,4};
	//calgorith.insertSort(array,5);
	//calgorith.selectionSort(array,5);
	//calgorith.shellSort(array,5);
	//calgorith.quickSort1(array,0,7);
	int tempArray[8];  
	calgorith.mergeSort(array,tempArray,0,7);
	for(int i=0;i<8;i++)  
		cout<<array[i]<<"  ";  
	cout<<endl;
	system("pause");
}

 

 

    一、直接插入排序

      每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。

第一趟比较前两个数,然后把第二个数按大小插入到有序表中;

第二趟把第三个数据与前两个数从前向后扫描,把第三个数按大小插入到有序表中;

依次进行下去,进行了(n-1)趟扫描以后就完成了整个排序过程。

直接插入排序属于稳定的排序,最坏时间复杂性为O(n^2),空间复杂度为O(1)。

直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较,所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较,直到找到比待比较数值小的并将待比较数值置入其后一位置,结束该次循环。

    二、冒泡排序

        冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

          冒泡排序的最大时间代价,最小时间代价和平均时间代价均为θ(n²)。

     冒泡排序算法的运作如下:

1、比较相邻的元素。如果第一个比第二个大,就交换他们两个。

2、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

3、针对所有的元素重复以上的步骤,除了最后一个。

4、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

 

    三、直接选择排序

        选择排序的最大时间代价,最小时间代价和平均时间代价均为θ(n²)。选择排序不依赖于原始数组的输入顺序。

 

    四、希尔排序

         增量为2的shell排序的时间代价可以达到θ(n的3/2次方),有的增量可以达到θ(n的7/6次方),很接近θ(n)。

         希尔排序:将无序数组分割为若干个子序列,子序列不是逐段分割的,而是相隔特定的增量的子序列,对各个子序列进行插入排序;然后再选择一个更小的增量,再将数组分割为多个子序列进行排序......最后选择增量为1,即使用直接插入排序,使最终数组成为有序。

增量的选择:在每趟的排序过程都有一个增量,至少满足一个规则 增量关系 d[1] > d[2] > d[3] >..> d[t] = 1 (t趟排序);根据增量序列的选取其时间复杂度也会有变化,这个不少论文进行了研究,在此处就不再深究;本文采用首选增量为n/2,以此递推,每次增量为原先的1/2,直到增量为1;

下图详细讲解了一次希尔排序的过程:



 

 

    五、快速排序

        快速排序的最大时间代价为θ(n²),最小时间代价为θ(n*logn),平均时间代价为θ(n*logn)。

        基本思想是:

1.先从数列中取出一个数作为基准数

2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边

3.再对左右区间重复第二步,直到各区间只有一个数

 

    六、归并排序

         归并排序的最大时间代价,最小时间代价和平均时间代价均为θ(n*logn)。归并排序不依赖于原始数组的有序程度。

       归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

       将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。                                     

  

    七、堆排序

     利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

    其基本思想为(大顶堆):

    1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆,此堆为初始的无序区;

    2)将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n]; 

    3)由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

 

    七、总结

稳定的排序算法:

      冒泡排序(bubble sort) — O(n2)

  鸡尾酒排序 (Cocktail sort, 双向的冒泡排序) — O(n2)

  插入排序 (insertion sort)— O(n2)

  桶排序 (bucket sort)— O(n); 需要 O(k) 额外记忆体

  归并排序 (merge sort)— O(n log n); 需要 O(n)额外记忆体

  原地归并排序 — O(n2)

  二叉树排序 (Binary tree sort) — O(n log n); 需要 O(n) 额外记忆体

  基数排序 (radix sort)— O(n·k); 需要 O(n) 额外记忆体

 

不稳定的排序算法:

      选择排序 (selection sort)— O(n2)

    希尔排序 (shell sort)— O(n log n) 

  Comb sort — O(n log n)

  堆排序 (heapsort)— O(n log n)

  Smoothsort — O(n log n)

  快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序

      一般来说:存在不相邻交换的排序算法是不稳定的,相邻交换的排序算法是稳定的;对于相邻交换的稳定排序算法,通过控制交换条件可以转换成不稳定排序算法;冒泡、插入、归并和基数排序是稳定的;选择、快速、希尔和堆排序是不稳定的。

 

 

   

  • 大小: 122.9 KB
分享到:
评论

相关推荐

    C++实现FP-Growth算法

    C++是广泛应用的编程语言,能够提供高效的性能,因此C++实现FP-Growth算法具有很高的实用价值。 FP-Growth的核心思想是通过构建一个FP树(Frequent Pattern tree)来存储频繁项集,并利用这个树结构来挖掘出所有的...

    C++算法-图算法(第三版).rar

    《C++算法-图算法(第三版)》是一本深入探讨C++编程语言在实现图算法方面的专业书籍。作为第三版,它很可能包含了最新的研究进展和技术改进,旨在为读者提供全面且更新的知识体系。该书可能涵盖了从基础理论到高级...

    数据结构课程设计(C++代码+报告)--各种排序算法时间性能的比较

    "各种排序算法时间性能的比较"这个程序文件可能是用C++语言实现的,C++以其高效和灵活性成为实现算法的常用语言。在这个程序中,应该包含了各种排序算法的函数实现,并且有一个主程序用于测试和比较这些排序算法的...

    C++版的fp-growth算法

    **C++实现的FP-Growth算法** FP-Growth算法是一种高效的数据挖掘技术,主要用于关联规则学习,即在大规模数据集中发现频繁项集。这个算法在处理大数据量时表现出了较高的性能,因为它避免了构建和搜索全频繁项集的...

    C++堆排序实现算法

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

    用c++实现的快速排序算法

    用c++实现的快速排序算法 算法实现的简单易懂

    C++实现常用排序算法

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

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

    本文将探讨如何使用这两种语言实现几种基本的排序算法:冒泡排序、选择排序,以及两种全比较排序(并行和串行)。 首先,让我们了解一下排序算法。排序是计算机科学中最基础的操作之一,它涉及到将一组数据按照特定...

    快速排序算法c++实现

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

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

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

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

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

    算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索

    算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索算法Ⅰ-Ⅳ...

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

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

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

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

    数据结构课程设计(C++)实现各种排序算法

    数据结构课程设计中,C++实现的八种排序算法涵盖了数据结构的核心概念,这些排序算法在实际编程中具有广泛的应用。下面将详细解释每一种排序算法的设计思想和性能特点。 1. **交换排序**: - **冒泡排序**:通过...

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

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

    C++ STL--数据结构与算法实现(余文溪)示例程序代码.rar

    C++ STL,全称为Standard Template Library(标准模板库),是C++编程语言中的一部分,它提供了丰富的容器、迭代器、算法和函数对象等组件,极大地简化了数据结构和算法的实现。余文溪的《C++ STL--数据结构与算法...

    c++实现比较各种排序算法的效率

    然而,了解并手动实现这些基本排序算法有助于深入理解它们的工作原理,同时在特定场景下优化性能。 比较这些排序算法的效率时,通常考虑以下因素: 1. **时间复杂度** - 描述算法运行所需的步骤数量与输入规模的...

    c++排序算法-冒泡排序

    尽管冒泡排序的时间复杂度较高,但在教学和理解排序算法的基本原理时非常有用。在实际应用中,更高效的排序算法如快速排序、归并排序和堆排序通常更受欢迎,尤其是在处理大数据集时。不过,了解和掌握冒泡排序有助于...

    数据结构课程设计---排序算法比较

    数据结构课程设计,C语言,七大排序算法比较

Global site tag (gtag.js) - Google Analytics