各种排序算法分析与比较

时间：2023-02-10 22:09:15

1.直接插入排序

每一趟将一个待排序的元素作为关键字，按照其关键字的大小插入到已经排好的部分序列的适当位置上。平均时间复杂度为O（n2），空间复杂度为O(1)。

void InsertSort(int R[], int n)
{
	if (R == nullptr || n<=0)
		return;
	int i, j;
	int temp;
	for (i = 1; i < n; ++i)
	{
		j = i - 1;
		temp = R[i];
		while (j >= 0 && R[j] > temp)
		{
			R[j+1] = R[j];
			--j;
		}
		R[j+1] = temp;
	}
}

2.冒泡排序

平均时间复杂度为O（n2），空间复杂度为O(1)

void BubbleSort(int R[], int n)
{
	if (R == nullptr || n <= 0)
		return;
	int i, j;
	int temp;
	int flag = 0;
	for (i = n; i >= 1; --i)
	{
		flag = 0;//每次重新置为0
		for (j = 1; j < i; ++j)
		{
			if (R[j - 1] > R[j])
			{
				temp = R[j];
				R[j] = R[j - 1];
				R[j - 1] = temp;
				flag = 1;//有数据交换，flag=1;
			}
		}

		if (flag == 0)
			return;
	}
}

3.快速排序

快速排序以枢轴为中心，将序列分成两部分。关键是枢轴的划分。

时间复杂度：最好的情况下为O(nlogn),最坏为O(n2)

空间复杂度：O(log2n)

递归算法：

void QuickSort(int R[], int low, int high)
{
	if (low >= high)
		return;
	int pivot = Partition(R, low, high);
	QuickSort(R, low, pivot - 1);
	QuickSort(R, pivot + 1, high);
}
几种划分算法：

1.从后往前扫描直到小于枢轴的位置j，将R[j]交换到i的位置；从i开始往后扫描，直到遇到大于枢轴的位置i,把R[i]交换到j的位置。

int Partition(int R[], int low, int high)
{
	int pivot = R[low];
	while (low < high)
	{
		while (low < high && R[high] >= pivot)
			--high;
		if (low < high)
			R[low] = R[high];
		while (low < high && R[low] <= pivot)
			++low;
		if (low < high)
			R[high] = R[low];
	}
	R[low] = pivot;
	return low;
}
2.从前往后扫描，遇到小于枢轴的值，则递增small值，如果当前下标与small不相等，则交换，保证small左边的元素都小于枢轴。 

int Partition(int data[], int start, int end)
{
	int index= RandomInRange(start,end);//随机生成一个数作为中枢值
	swap(data[index],data[end]);//最后一个值作为中枢值
	
	int small=start-1;
	for(index=start; index<end; ++index)
	{
		if(data[index]<data[end])
		{
			++small;
			if(small != index)
				swap(data[index], data[small]);
		}
	}
	++small;
	swap(data[small], data[end]);
	return small;
}

3.两边同时进行扫描，并交换位置。

int Partition3(int R[], int low, int high)
{
	int pivot = R[low];
	int i = low + 1;
	int j = high;
	while (i <= j)
	{
		while (i <= j && R[j] >= pivot)
			--j;
		while (i <= j && R[i] <= pivot)
			++i;
		if (i < j)
		{
			swap(R[i], R[j]);
			++i;
			--j;
		}
	}
	swap(R[low], R[j]);
	return j;
}

4.堆排序

堆是一种数据结构，可以把堆看成完全二叉树，这棵完全二叉树满足：任何一个非叶节点的值都不大于（或不小于）其左右孩子节点的值。若父节点大于孩子节点，则叫大顶堆，父节点小于孩子节点，则叫小顶堆。

堆排序的主要操作是将序列调整为堆。

时间复杂度：O(n log2n);空间复杂度：O(1)

void Shift(int R[], int low, int high)
{
	int i = low;
	int j = 2 * i + 1;
	int temp = R[i];
	while (j <= high)
	{
		if (j < high && R[j] < R[j + 1])
		{
			++j;
		}
		if (temp < R[j])
		{
			R[i] = R[j];
			i = j;
			j = 2 * i + 1;
		}
		else
			break;
	}
	R[i] = temp;
}
void HeapSort(int R[], int n)
{
	int i;
	int temp;
	for (i = n / 2 - 1; i >= 0; --i)
	{
		Shift(R, i,n);
	}
	for (i = n-1; i >= 1; --i)
	{
		temp = R[0];
		R[0] = R[i];
		R[i] = temp;
		Shift(R, 0, i - 1);
	}
}

4.二路归并排序

归并排序的时间复杂度和初始序列无关，平均情况下为O(n log2n),最好情况下为O(nlog2n),最坏情况下也为O(nlog2n)。

空间复杂度：因归并排序需要转存整个待排序列，因此空间复杂度为O(n)

void Merge(int R[], int tempArray[], int low, int mid, int high)
{
	int i = low;
	int j = mid + 1;
	int k = i;
	while (i <= mid && j <= high)
	{
		if (R[i] < R[j])
			tempArray[k++] = R[i++];
		else
			tempArray[k++] = R[j++];
	}
	while (i <= mid)
		tempArray[k++] = R[i++];
	while (j <= high)
		tempArray[k++] = R[j++];
	for (int i = low; i <= high; ++i)
	{
		R[i] = tempArray[i];
	}
}
void MergeSort(int R[],int tempArray[], int low, int high)
{
	if (low < high)
	{
		int mid = (low + high) / 2;
		MergeSort(R, tempArray, low, mid);
		MergeSort(R, tempArray, mid + 1, high);
		Merge(R, tempArray, low, mid, high);
	}
}
void MergeSort(int R[], int n)
{
	int *tempArray = new int[n];
	MergeSort(R, tempArray, 0, n - 1);
	delete []tempArray;
}
5.计算排序

适用于元素的取值范围比较小的情况。

1>统计每个元素的个数

2>统计每个元素比自身小的元素个数

template <typename Type>
void CountingSort(Type array[], int low, int high, int range)//range为元素的取值范围
{
	Type *result = new Type[high - low + 1];
	Type *valueCount = new Type[range + 1];

	for (int i = 0; i <= range; ++i)
	{
		valueCount[i] = 0;
	}

	for (int i = low; i <= high; ++i)
	{
		valueCount[array[i]] += 1;
	}

	for (int i = 1; i <= range; ++i)
	{
		valueCount[i] += valueCount[i - 1];
	}

	for (int i = high; i >= low; --i)
	{//form high to low , in order to guarantee the stable sort
		result[valueCount[array[i]] - 1] = array[i];
		--valueCount[array[i]];
	}
	
	int i = low;
	while (i <= high)
	{
		array[i] = result[i - low];
		++i;
	}

	delete[] result;
	delete[] valueCount;
}

参考博客：

http://blog.csdn.net/anonymalias/article/details/11547039

http://www.cnblogs.com/wxisme/p/5243631.html



















标签：

相关文章