常用的排序算法

#include<iostream>
using namespace std;

/*
 1.直接插入排序    （稳定）

 平均时间复杂度：O（n^2）；最好时间复杂度：O（n）；最坏时间复杂度：O(n^2)
 辅助空间：O（1）
 最坏的比较次数：n(n-1)/2 ;最好比较次数：n-1
*/

template<class Elemtype>
void StraightinsertionSort(Elemtype elem[], int n)
{  
	for (int i = 1; i < n; i++)
	{
		Elemtype e = elem[i];                         //暂存elem[i]
		int j;
		for (j = i - 1; j >= 0 && elem[j] > e; j--)   //将比e大的记录都往后移
		{
			elem[j+1] =elem[j];                      
		}
		elem[j + 1] = e;
	}
}

/*-----------------------------------------------------------------------------*/

/*
2.希尔排序  (不稳定，对直接插入排序的一种改进)

平均时间复杂度：O(n^(3/2); 最好时间复杂度：O(n); 最坏时间复杂度：O(n^2)
辅助空间：O(1)
*/
template<class Elemtype>
void shellInsertion(Elemtype elem[], int n, int arr)
{
	for (int i = arr; i < n; i++)
	{
		Elemtype e = elem[i];
		int j;
		for (j = i - arr; j >= 0 && elem[j] > e; j -= arr)
		{
			elem[j+arr ] = elem[j];
		}
		elem[j + arr] = e;
	}
}

template<class Elemtype>
void shellsort(Elemtype elem[], int n, Elemtype arr[], int t)  //Elemtype arr[]为增量序列,增量序列的最后一个增量值必须等于1
{
	for(int i = 0; i < t; i++)
	{
		shellInsertion(elem, n, arr[i]);
	}
}

/*------------------------------------------------------------------------------------------*/

/*
3.冒泡排序 （稳定）

平均时间复杂度：O(n^2); 最好时间复杂度：O（n）；最坏时间复杂度：O(n^2)
辅助空间：O(1)
最坏的比较次数：n(n-1)/2
*/

template<class Elemtype>
void swap(Elemtype* a, Elemtype* b)
{
	Elemtype tem = *a;
	*a = *b;
	*b = tem;
}

template<class Elemtype>
void bubblesort(Elemtype elem[], int n)
{
	for (int i = n - 1; i > 0; i--)
	{
		for (int j = 0; j < i; j++)
		{
			if (elem[j] > elem[j + 1])
			{
				swap(elem[j], elem[j + 1]);
			}
		}
	}
}

/*-------------------------------------------------------------*/

/*
4.快速排序 (不稳定)

平均时间复杂度：O(nlogn); 最好时间复杂度O(nlogn)；最坏时间复杂度O(n^2)
辅助空间：O(logn)

*/

template<class Elemtype>
int partition(Elemtype elem[], int low, int high)
{
	while (low < high)
	{
		while (low < high && elem[high] >=elem[low])
		{
			high--;                             //elem[low]为枢轴，使high右边的元素不小于elem[low]
		}
		swap(elem[low], elem[high]);
		while (low < high && elem[low] <= elem[high])
		{
			low++;                             //elem[high]为枢轴，使low左边的元素不大于elem[high]
		}
		swap(elem[low], elem[high]);
	}
	return low;                                 //返回枢轴的位置
}

template<class Elemtype>
void quicksorthelp(Elemtype elem[], int low, int high)
{
	if (low < high)
	{
		int pivot = partition(elem, low, high);  //进行一趟划分
			quicksorthelp(elem, low, pivot - 1);
		    quicksorthelp(elem, pivot + 1, high);
        
	}
}

template<class Elemtype>
void quicksort(Elemtype elem[], int n)
{
	quicksorthelp(elem, 0, n - 1);
}

/*--------------------------------------------------------------------*/

/*
5.简单选择排序 （不稳定）

平均时间复杂度：O(n^2); 最好时间复杂度：O(n^2); 最坏时间复杂度：O(n^2)
辅助空间：O(1)
*/

template<class Elemtype>
void simpleselectionsort(Elemtype elem[], int n)
{
	for (int i = 0; i < n-1; i++) //注意此处i<n-1
	{
		int lowindex = i;         //lowindex用来记录最小元素的下标
		for (int j = i+1; j < n; j++)
		{
			if (elem[j] < elem[lowindex])
			{
				lowindex = j;
			}
		}
		swap(elem[i], elem[lowindex]);
	}
}

/*-------------------------------------------------------------------*/

/*
6.堆排序（不稳定，此为构造大顶堆）

平均时间复杂度：O(nlogn);最好时间复杂度：O(nlogn) 最坏时间复杂度：O(nlogn)
辅助空间：O(1)
*/

template<class Elemtype>
void siftadjust(Elemtype elem[], int low, int high)
{
	for (int f = low, i = 2 * low + 1; i <=high; i = i * 2 + 1) //f为被调整的结点
	{
		if (i < high && elem[i] < elem[i + 1]) //i为f最大的孩子
		{
			i++;
		}
		if (elem[f] >= elem[i])//已成为大顶堆
		{
			break;
		}
		swap(elem[f], elem[i]);
		f = i;   //成为新的调整结点
	}
}

template<class Elemtype>
void heapsort(Elemtype elem[], int n)
{
	for (int i = (n - 2) / 2; i >=0; i--) //第一次构造一个完整的大顶堆，（n-2）/2是最后一个非终端结点的下标
	{
		siftadjust(elem, i, n - 1);
	}
	for (int j = n - 1; j > 0; j--)
	{
		swap(elem[j],elem[0]);            
		siftadjust(elem, 0, j - 1);       //将elem[0....j-1]重新调整为大顶堆
	}
}

/*--------------------------------------------------------------------------------*/

/*
7.归并排序（稳定，2-路归并排序，递归实现）

平均时间复杂度：O(nlogn);最好时间复杂度：O(nlogn);最坏时间复杂度：O(nlogn)
辅助空间：O(n+logn)

*/

template<class Elemtype>
void merge1(Elemtype elem[], Elemtype tmp[], int low, int mid, int high)
{
	int i, j, k;
	for ( i = low, j = mid + 1, k = low; i <= mid && j <= high; k++)
	{
		if (elem[i] <= elem[j])
		{
			tmp[k] = elem[i];
			i++;
		}
		else
		{
			tmp[k] = elem[j];
			j++;
		}
	}
	for (; i <= mid; i++, k++)
	{
		tmp[k] = elem[i];
	}
	for (; j <= high; j++, k++)
	{
		tmp[k] = elem[j];
	}
	for ( i = 0; i <= high; i++)
	{
		elem[i] = tmp[i];
	}
}

template<class Elemtype>
void mergehelp1(Elemtype elem[], Elemtype tmp[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;
		mergehelp1(elem, tmp, low, mid);
		mergehelp1(elem, tmp, mid+1, high);
		merge1(elem, tmp, low, mid, high);
	}
}

template<class Elemtype>
void mergesort1(Elemtype elem[], int n)
{
	Elemtype* tmp = new Elemtype[n];
	mergehelp1(elem, tmp, 0, n - 1);
	delete[]tmp;
}

/*
8.归并排序（2-路归并，非递归实现）

平均时间复杂度：O(nlogn);最好时间复杂度：O(nlogn);最坏时间复杂度：O(nlogn)
辅助空间：O(n+logn)

*/

template<class Elemtype>
void merge2(Elemtype elem[], Elemtype tmp[], int low, int mid, int high)
{
	int i, j, k;
	for (i = low, j = mid + 1, k = low; i <= mid && j <= high; k++)
	{
		if (elem[i] <= elem[j])
		{
			tmp[k] = elem[i];
			i++;
		}
		else
		{
			tmp[k] = elem[j];
			j++;
		}
	}
	for (; i <= mid; i++, k++)
	{
		tmp[k] = elem[i];
	}
	for (; j <= high; j++, k++)
	{
		tmp[k] = elem[j];
	}
	for (i = 0; i <= high; i++)
	{
		elem[i] = tmp[i];
	}
}

template<class Elemtype>
void mergehelp2(Elemtype elem[], Elemtype tmpElem[], int high)
{
	int step = 1;                  //步长
	while (step <= high)
	{
		int index = 0;             //当前的下标
		while (index <= high - 2 * step + 1)  //将相邻数组归并
		{
			merge2(elem, tmpElem, index, index + step - 1, index + 2 * step - 1);//两两归并
			index = index + 2 * step;  //到下一个要归并的两个序列的首序列
		}
		if (index + step <= high)  //合并有序的左半部分和不及一个步长的右半部分
		{
			merge2(elem, tmpElem, index, index + step - 1, high);
		}
		step *= 2;
	}
	
}

template<class Elemtype>
void mergesort2(Elemtype elem[], int n)
{
	Elemtype* tmpElem = new Elemtype[n];
	mergehelp2(elem, tmpElem, n - 1);
	delete[]tmpElem;
}

/*-----------------------------------------------------------------*/

int main()
{
	int a[] = { 1,4,5,2,3,7,1,8,1 };
	int n = sizeof(a)/sizeof(a[0]);
	//StraightinsertionSort(a,  n);//直接插入排序

	int arr[] = { 4,2,1 };        //增量序列
	int t = sizeof(arr) / sizeof(arr[0]);

	//shellsort(a, n, arr, t);    //希尔排序
	//bubblesort(a, n);            //冒泡排序
	//quicksort(a, n);            //快速排序
	//simpleselectionsort(a, n);    //简单选择排序
	//heapsort(a, n);             //堆排序
	//mergesort1(a, n);          //归并排序，递归实现
	mergesort2(a, n);
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << " ";
		
	}
	cout << endl;
	system("pause");
	return 0;
}

最后

以上就是忧虑玫瑰为你收集整理的常用的排序算法 （C++实现）常用的排序算法的全部内容，希望文章能够帮你解决常用的排序算法 （C++实现）常用的排序算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。