常见的排序算法

in 个人博客 on Algorithm

常见的排序算法复习

简单的复习一下常见的排序算法：快速排序，希尔排序，堆排序，直接插入排序，基数排序，冒泡排序，直接选择排序以及归并排序。

冒泡排序

很简单，主要思想就是不断比较相邻两个数，让“较大”的元素不断后移，最多N-1轮。

void BubbleSort(int a[], int length)
{
	//int a[10];
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length - 1 - i; j++)
		{
			if (a[j]>a[j + 1])
			{
				int t = a[j];
				a[j] = a[j + 1];
				a[j + 1] = t;
			}
		}
	}
}

冒泡排序是稳定排序算法，时间复杂度是O(N^2)。
有哪些优化的地方？

  1. 如果一次内循环中没有交换元素的位置，那么可以认定已经排好序了，这时就可以终止外循环了
  2. 每一次内循环中最后一次元素交换的位置就是无序数列的边界，可以记录下来，减少外循环的次数

简单选择排序

选择排序是通过每一趟排序过程中从待排序的记录中选出最大(小)的元素，将其依次放在数据最前(后)来实现排序：选取最大(小)元素与第一个元素交换位置，然后从剩下的元素中再选择一个数与第二个元素交换位置直到最后两个位置的元素交换位置。选择排序和冒泡排序的区别就在于选择排序的交换次数要少。

void SelectionSort(int a[], int length) {
	int i, j, min;
	int temp;
	for (i = 0; i < length - 1; i++) {
		min = i;
		for (j = i + 1; j < length; j++) {
			if (a[j] < a[min]) {
				min = j;
			}
		}
		if (i == min)
			continue;
		temp = a[i];
		a[i] = a[min];
		a[min] = temp;
	}
}

选择排序是一个不稳定的排序算法，时间复杂度为O(N^2)。

直接插入排序

直接插入排序的主要思想就是将一个记录插入到一个已经排好序的序列中，从而得到一个新的有序序列：

  1. 从第一个元素开始，认为是一个有序序列。
  2. 取出下一个元素，在已排序的序列中从后向前扫描。
  3. 如果该元素大于新元素，将该元素移至下一个位置。
  4. 重复步骤3，直到已排序元素中元素小于或等于新元素。
  5. 将新元素插入有序表。
  6. 重复2-5。
void InsertSort(int a[], int length)
{
	for (int i = 1; i < length; i++) {
		int j = i;
		int temp = a[i];
		while (j>0 && temp<a[j - 1])
		{
			a[j] = a[j - 1];
			j--;
		}
		a[j] = temp;
	}
}

插入排序是一个稳定的排序算法，时间复杂度为O(N^2)。

以上三种算法时间复杂度上来说都一样，但是性能上略有区别，冒泡排序和插入排序的交换次数和序列的有序程度相关，越接近有序，性能就越好，在此基础上，插入排序要比冒泡排序好一点(插入排序的交换是连续的)。而选择排序的交换次数是固定的，和序列的有序程度无关。序列有序程度高，插入排序效率高一点，序列接近于无序，则选择排序性能要更好。

希尔排序

希尔排序是对直接插入排序的一种改进，将全部数据按照下标以一个增量进行分组，对每一个分组进行直接插入排序，然后逐渐减小增量，分组，排序，直到最后以增量为1，对全部数据进行插入排序。主要思想就是先将序列划分为小序列，然后对小序列进行插入排序，提升整个序列的有序程度。

void ShellSort(int a[], int length) {
	int r, i, j, temp;
	for (r = length / 2; r > 0; r /= 2) { //确定分组
		for (i = r; i < length; i++) { //开始插入排序
			j = i - r;
			temp = a[i];
			while (j >= 0 && temp<a[j])
			{
				a[j + r] = a[j];
				j -= r;
			}
			a[j + r] = temp;
		}
	}
}

希尔排序是不稳定的，但其时间复杂度会小于O(N^2)。

快速排序

快速排序将要进行排序的数分为两部分，其中一部分的数要比另外一部分的数要小，然后对这两部分按照相同的规则进行划分，直到全部数据变为有序：

  1. 首先从待排序的数据中选取一个数作为基准，一般为第一个数或者最后一个数。
  2. 通过分区，将比基准小的数全部放在一边，大的数放在另一边。
  3. 对两个分区重复第二步。
void QuickSort(int a[], int low, int high)
{
	if (low >= high)
	{
		return;
	}
	int i = low;
	int j = high;
	int base = a[i];
	while (i<j)
	{
		while (i<j&&base <= a[j])
		{
			j--;
		}
		a[i] = a[j];
		while (i<j&&a[i] <= base)
		{
			i++;
		}
		a[j] = a[i];
	}
	a[i] = base;
	QuickSort(a, low, i - 1);
	QuickSort(a, i + 1, high);
}

快速排序是不稳定的，时间复杂度在O(NlogN)，最坏情况可以到O(N^2)

归并排序

归并排序是将数据分为两部分，一次对两部分进行归并排序，最后将这些有序序列合并成一个有序序列的过程：

  1. 将数据平均分为左右两部分：[left, mid]和[mid+1, right]
  2. 继续划分，直到划分区间长度为1
  3. 对所划分的N个子序列进行两两合并排序，直到获取到一个长度为N的有序序列
void Merge(int a[], int left, int right) {
	int length = right - left + 1;
	int* temp = (int *)malloc(length * sizeof(int));
	memcpy(temp, a + left, length * sizeof(int));
	int mid = (length - 1) / 2;
	int i, j = 0, k = mid + 1;
	for (i = left; i <= right; i++) {
		if (j > mid) {
			a[i] = temp[k++];
		}
		else if (k > length - 1) {
			a[i] = temp[j++];
		}
		else if (temp[j] < temp[k]) {
			a[i] = temp[j++];
		}
		else {
			a[i] = temp[k++];
		}
	}
	return;
}

void MergeSort(int a[], int left, int right) {
	if (left >= right) {
		return;
	}
	int mid = (left + right) / 2;
	MergeSort(a, left, mid);
	MergeSort(a, mid + 1, right);
	Merge(a, left, right);
}

归并排序是稳定的排序，时间复杂度稳定在O(NlogN)，需要额外的空间进行归并(merge)。

堆排序

堆，可以近似的看成是一个完全二叉树，分为大顶堆和小顶堆，其中大顶堆的定义为每个节点的值都不大于其父节点的值。可以看出，大顶堆的最大值一定再堆顶。
堆排序就是将待排序数据构造大顶堆或者小顶堆，从堆顶中取出最大值或最小值，然后在对剩下的元素构造大顶堆或小顶堆。

void HeapInit(int a[], int head, int tail) {
	if (head < tail) {
		int left = head * 2 + 1;
		int right = head * 2 + 2;
		int min = head;
		int temp;
		if (left <= tail) {
			if (a[min] > a[left]) {
				min = left;
			}
		}
		if (right <= tail) {
			if (a[min] > a[right]) {
				min = right;
			}
		}

		if (min != head) {
			temp = a[min];
			a[min] = a[head];
			a[head] = temp;
			HeapInit(a, min, tail);
		}
	}
}

void HeapSort(int a[], int length) {
	int i;
	int temp;
	for (i = (length - 1) / 2; i >= 0; i--) {   //第一次构造大顶堆
		HeapInit(a, i, length - 1);
	}
	for (i = 0; i < length; i++) {
		printf("%d ", a[i]);
	}
	i = length - 1;
	do {
		temp = a[0];
		a[0] = a[i];
		a[i] = temp;
		i--;
		HeapInit(a, 0, i);
	} while (i > 0);
}

堆排序是不稳定的，时间复杂度稳定在O(NlogN)。

基数排序

基数排序是将一组数据按照每一位进行排序，排序的顺序是个位，十位…

int GetMaxDigit(int a[], int length) {
	int i, max = a[0];
	for (i = 1; i < length; i++) {
		if (a[i] > max) {
			max = a[i];
		}
	}
	i = 0;
	while (max>0)
	{
		max /= 10;
		i++;
	}
	return i;
}

void LSDBaseSort(int a[], int length) {
	int digit = GetMaxDigit(a, length);
	int* temp = (int*)malloc(length * sizeof(int));
	int base = 1;
	int i;
	while (digit--)
	{
		int count[10] = { 0 };
		memset(temp, 0, length * sizeof(int));
		for (i = 0; i < length; i++) {
			count[a[i] / base % 10]++;
		}
		int start[10] = { 0 };
		for (i = 1; i < 10; i++) {
			start[i] = count[i - 1] + start[i - 1];
		}
		for (i = 0; i < length; i++) {
			temp[start[a[i] / base % 10]++] = a[i];
		}
		memcpy(a, temp, length * sizeof(int));
		base *= 10;
		for (int i = 0; i < length; i++) {
			printf("%d ", a[i]);
		}
		printf("\n");
	}
}

建议不要用于商业用途, 转载请注明原文地址: https://Soo-Q6.github.io/blog/2019-11-03-sorting/

© 2019. All rights reserved.

Powered by shouqin v1.0