常见排序算法实现

• 算法结构

  目录

  1. 冒泡排序
  2. 插入排序
  3. 希尔排序
  4. 选择排序
  5. 堆排序
  6. 快速排序
  7. 归并排序
  8. 计数排序

一.冒泡排序

算法思路：

通过多次遍历 不断比较并交换相邻的元素，直到所有元素有序。

交换过程

常见排序算法实现

代码如下：

// 冒泡排序 
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		bool exchange = false;
		for (int i = 1; i  a[i])
			{
				swap(a[i - 1], a[i]);
				exchange = true;
			}
		}

		if (exchange == false)
			break;
	}
}

复杂度分析：

时间复杂度最坏情况：O(n^2)

时间复杂度最好情况：当排序元素本身极度接近或有序时 只需遍历一遍 O(n^2）  

空间复杂度：O(1)

二.插入排序

算法思路：

把待排序的元素按其大小逐个插入到一个已经排好序的有序序列中，直到所有的元素插入完为止，得到一个新的有序序列 。

交换过程

常见排序算法实现

代码如下：

// 插入排序
void InsertSort(int* a, int n)
{
	// [0, end] end+1
	for (int i = 0; i = 0)
		{
			if (tmp > a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
}

时间复杂度分析：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度：O(N^2)

3. 空间复杂度：O(1)，它是一种稳定的排序算法

三.希尔排序

算法思路：

先选定一个小于N的整数gap，将所有距离为gap的元素分在同一组内，并对每一组内的元素进行直接插入排序。重复上述分组和排序的工作。当gap=1时，排序完成。

交换过程

常见排序算法实现

代码如下：

// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;

	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		//gap = gap / 2;
		gap = gap / 3 + 1;

		for (int i = 0; i = 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

 复杂度分析：

希尔排序的时间复杂度由于gap的取值不同以及牵扯一些数学上未被证明的问题，无法严格证明，目前一般认为O(n^1.3)。

 四.选择排序

算法思路：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的 数据元素排完 。实际上，一趟选出最大值和最小值，将其放在序列开头和末尾，可使选择排序的效率快一倍。

交换过程

常见排序算法实现

代码如下：

// 选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i]  a[maxi])
			{
				maxi = i;
			}
		}

		swap(a[begin], a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		swap(a[end], a[maxi]);

		++begin;
		--end;
	}
}

复杂度分析：

直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。

时间复杂度：O(N^2)

空间复杂度：O(1)

 五.堆排序

算法思路：

堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

交换过程

常见排序算法实现

代码如下：

// 堆排序

void down(int u)
{
    int t = u;
    if (2 * u  h[2 * u])
        t = 2 * u;
    if (2 * u + 1  h[2 * u + 1])
        t = 2 * u + 1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main()
{
    //排出n个数中最小(大)的前m个数
    cin >> n >> m;
    mySize = n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &h[i]);
    for (int i = n / 2; i; i--)
        down(i);

    while (m--)
    {
        cout << h[1] << " ";
        h[1] = h[mySize--];
        down(1);
    }

    return 0;
}

复杂度分析：

时间复杂度：O(N*logN)

空间复杂度：O(1)

  六.快速排序

算法思路：

任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

交换过程

1.单趟排序

常见排序算法实现

2.整体过程

常见排序算法实现

代码如下：

// hoare
int PartSort1(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	swap(a[midi], a[begin]);

	int left = begin, right = end;
	int keyi = begin;

	while (left < right)
	{
		// 右边找小
		while (left = a[keyi])
		{
			--right;
		}

		// 左边找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}

		swap(a[left], a[right]);
	}

	swap(a[left], a[keyi]);

	return left;
}

// 挖坑法
int PartSort2(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	swap(a[midi], a[begin]);

	int key = a[begin];
	int hole = begin;
	while (begin < end)
	{
		// 右边找小，填到左边的坑
		while (begin = key)
		{
			--end;
		}

		a[hole] = a[end];
		hole = end;

		// 左边找大，填到右边的坑
		while (begin < end && a[begin] <= key)
		{
			++begin;
		}

		a[hole] = a[begin];
		hole = begin;
	}

	a[hole] = key;
	return hole;
}

// 前后指针法
int PartSort3(int* a, int begin, int end)
{
	int midi = GetMidi(a, begin, end);
	swap(a[midi], a[begin]);
	int keyi = begin;

	int prev = begin;
	int cur = prev + 1;
	while (cur <= end)
	{
		if (a[cur] = end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

// 快速排序 栈优化 非递归
void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while(!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = PartSort3(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
		if (left < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}

		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi+1);
		}
	}

	STDestroy(&s);
}

复杂度分析：

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

空间复杂度：O(NlogN)

时间复杂度：O(logN）

 七.归并排序

算法思路：

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

交换过程

常见排序算法实现

代码如下：

//归并排序
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;

	int mid = (begin + end) / 2;
	// [begin, mid][mid+1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid+1, end, tmp);

	// [begin, mid][mid+1, end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while(begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}


// 归并排序 非递归 循环写法
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;
	while (gap ", gap);
		for (size_t i = 0; i = n || begin2 >= n)
			{
				break;
			}

			if (end2 >= n)
			{
				end2 = n - 1;
			}

			//printf("[%2d,%2d][%2d, %2d] ", begin1, end1, begin2, end2);

			int j = begin1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}

			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}

			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
            //一定注意memcpy 位置
			memcpy(a + i, tmp + i, sizeof(int) * (end2-i+1));
		}

		printf("\n");

		gap *= 2;
	}


	free(tmp);
}

复杂度分析：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。

时间复杂度：O(N*logN)

空间复杂度：O(N)

 八.计数排序

算法思路：

计数排序是一种非比较性的排序算法，它通过统计数组中每个元素出现的次数，然后根据元素的值和出现次数重新构建排序后的数组。

交换过程

常见排序算法实现

代码如下：

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i]  max)
			max = a[i];
	}

	int range = max - min + 1;
	int* count = (int*)calloc(range, sizeof(int));
	if (count == NULL)
	{
		printf("calloc fail\n");
		return;
	}

	// 统计次数
	for (int i = 0; i < n; i++)
	{
		count[a[i] - min]++;
	}

	// 排序
	int i = 0;
	for (int j = 0; j < range; j++)
	{
		while (count[j]--)
		{
			a[i++] = j + min;
		}
	}
}

复杂度分析：

计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。

时间复杂度：O(MAX(N,范围))

空间复杂度：O(范围)

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/ad6ab9f5a5.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐