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) 最坏情况; 对於大的、乱数串列一般相信是最快的已知排序

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