`
dengqsintyt
  • 浏览: 288031 次
  • 性别: 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
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics