05_排序

稳定性: 假定在待排序的记录序列中, 存在多个具有相同的关键字记录, 若经过排序, 这些记录的相对次序保持不变, 则称为这种排序算法是稳定的, 否则称为不稳定

内部排序: 数据元素全部放在内存中的排序

外部排序: 数据元素太多不能同时放在内存中, 根据排序过程的要求不能在内外存之间移动数据的排序

插入排序

将待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中, 直到所有的记录插入完为止, 得到一个新的有序序列

直接插入排序

将a[i]的元素与a[i]前面的元素进行比较, 找到插入位置将a[i]插入, 原来位置上的元素向后移

void InsertSort(int* a, int size) {
	// 逐个取出待排序的元素
	for (int i = 1; i < size; ++i) {
		// 取i号位置元素, 用key来比较
		int key = a[i];
		int end = i - 1;
		while (end >= 0 && key < a[end]) {
			// end元素向后搬移
			a[end + 1] = a[end];
			--end;
		}
		a[end + 1] = key;
	}

  • 元素集合越接近有序, 直接插入排序算法的时间效率越高
  • 时间复杂度O(N^2)
  • 空间复杂度O(1)
  • 是一种稳定的排序算法

希尔排序(缩小增量排序)

把记录按下标的一定增量分组, 对每组直接使用插入排序算法排序, 随着增量逐渐减少, 每组包含的关键词越来越多, 当增量减至1时, 整个文件被分为一组, 算法终止

void ShellSort(int* a, int size) {
	int gap = size;
	while (gap > 0) {
		gap = gap / 3 + 1;
		for (int i = gap; i < size; ++i) {
			int key = a[i];
			int end = i - gap;
			while (end >= 0 && key < a[end]) {
				a[end + gap] = a[end];
				end -= gap;
			}
			a[end + gap] = key;
		}
		gap -= 1;
	}
}
  • 希尔排序是对直接插入排序的优化
  • 当gap > 1时, 都是预排序, 目的是让数组更接近有序. 当gap == 1时, 数组已经是接近有序的了
  • 平均时间复杂度为O(N^1.3 -- N^2)
  • 是一种不稳定的排序算法

选择排序

每一次从待排序的数据元素中选出最小(最大)的一个元素, 存放在序列的起始位置, 直到全部待排序的元素排完

直接选择排序

void Swap(int* pLeft, int* pRight) {
	int temp = *pLeft;
	*pLeft = *pRight;
	*pRight = temp; 
}

void SelectSort(int* a, int size) {
	for (int i = 0; i < size - 1; ++i) {
		int minPos = i;
		for (int j = i + 1; j < size; ++j) {
			if (a[j] < a[minPos]) {
				minPos = j;
			}
		}
		if (minPos != i) {
			Swap(&a[minPos], &a[i]);
		}
	}
}
  • 时间复杂度: O(N^2)
  • 空间复杂度: O(1)
  • 是一种不稳定的排序算法

堆排序

排升序要建大堆, 排小序要建小堆

void Swap(int* pLeft, int* pRight) {
	int temp = *pLeft;
	*pLeft = *pRight;
	*pRight = temp; 
}

void AdjustDown(int* a, int size, int parent) {
	int child = parent * 2 + 1;
	if (parent < size) {
		while (child < size) {
			if (child + 1 < size && a[child + 1] < a[child]) {
				child += 1;
			}
			if (a[parent] > a[child]) {
				Swap(&a[child], &a[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else {
				return;
			}
		}
	}
}

void HeapSort(int* a, int size) {
	int nleaf = (size - 2) >> 1;
	for (int i = nleaf; i >= 0; --i) {
		AdjustDown(a, size, i);
	}
	for (int j = size - 1; j >= 0; --j) {
		Swap(&a[0], &a[j]);
		AdjustDown(a, j, 0);
	}
}
  • 时间复杂度: O(N*logN)
  • 空间复杂度: O(1)
  • 是一种不稳定的排序算法

交换排序

根据两个记录键值的比较来对换两个记录在序列中的位置

特点是: 将键值较大的队列向序列的尾部进行移动, 键值较小的队列向序列的前部移动

冒泡排序

void Swap(int* pLeft, int* pRight) {
	int temp = *pLeft;
	*pLeft = *pRight;
	*pRight = temp; 
}

void BubbleSort(int* a, int size) {
	for (int i = 0; i < size - 1; ++i) {
		for (int j = 1; j < size - i; ++j) {
			if (a[j] < a[j - 1]) {
				Swap(&a[j - 1], &a[j]);
			}
		}
	}
}
  • 时间复杂度: O(N^2)
  • 空间复杂度: O(1)
  • 是一种稳定的排序算法

快速排序

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

void Swap(int* pLeft, int* pRight) {
	int temp = *pLeft;
	*pLeft = *pRight;
	*pRight = temp; 
}

// 快速排序优化: 三数取中法选择key
int GetMiddleIndex(int* a, int left, int right) {
	int mid = left + ((right - left) >> 1);
	if (a[left] > a[right - 1]) {
		if (a[mid] < a[left]) {
			return left;
		}
		else if (a[mid] > a[right - 1]) {
			return right - 1;
		}
		else {
			return mid;
		}
	}
	else {
		if (a[mid] > a[left]) {
			return left;
		}
		else if (a[mid] < a[right - 1]) {
			return right - 1;
		}
		else {
			return mid;
		}
	}
}

// hoare法
int Partion1(int* a, int left, int right) {
	int begin = left;
	int end = right - 1;
	int mid = GetMiddleIndex(a, left, right);
	Swap(&a[mid], &a[right - 1]);
	int key = a[right - 1];
	while (begin < end) {
		// 从左到右找比基准值大的元素, 找到之后停止
		while (begin < end && a[begin] <= key) {
			++begin;
		}
		// 从右到左找比基准值小的元素, 找到之后停止 
		while (begin < end && a[end] >= key) {
			--end;
		}
		// 交换两个位置的元素
		if (begin != end) {
			Swap(&a[begin], &a[end]);
		}
	}
	if (begin != right - 1) {
		Swap(&a[begin], &a[right - 1]);
	}
	return begin;
}

// 挖坑法
int Partion2(int* a, int left, int right) {
	int begin = left;
	int end = right - 1;
	int mid = GetMiddleIndex(a, left, right);
	Swap(&a[mid], &a[right - 1]);
	int key = a[right - 1];

	while (begin < end) {
		// 从左向右找比基准值大的元素, 找到后填充end位置
		while (begin < end && a[begin] <= key) {
			++begin;
		}
		if (begin < end) {
			a[end] = a[begin];
			--end;
		}
		// 从右到左找比基准值小的元素, 找到后填充begin位置
		while (begin < end && a[end] >= key) {
			--end;
		}
		if (begin < end) {
			a[begin] = a[end];
			++begin;
		}
	}
	a[begin] = key;
	return begin; 
}

// 前后指针法  
int Partion3(int* a, int left, int right) {
	int cur = left;
	int pre = cur - 1;
	int mid = GetMiddleIndex(a, left, right);
	Swap(&a[mid], &a[right - 1]);
	int key = a[right - 1];

	while (cur < right) {
		if (a[cur] < key && ++pre != cur) {
			Swap(&a[cur], &a[pre]);
		}
		++cur;
	}
	if (++pre != right) {
		Swap(&a[pre], &a[right - 1]);
	}
	return pre;
}

void QuickSort(int* a, int left, int right) {
	if (right - left > 1) {
		int div = Partion1(a, left, right);
		QuickSort(a, left, div);
		QuickSort(a, div + 1, right);
	}

  • 时间复杂度: O(N*logN)
  • 空间复杂度: O(logN)
  • 是一种不稳定的排序算法

归并排序

将已有序的子序列合并, 得到完全有序的序列. 即先使每个子序列有序, 再使子序列段间有序

// 递归方式
void MergeData(int* a, int left, int mid, int right, int* temp) {
	int begin1 = left, end1 = mid;
	int begin2 = mid, end2 = right;
	int index = left;
	while (begin1 < end1 && begin2 < end2) {
		if (a[begin1] < a[begin2]) {
			temp[index++] = a[begin1++];
		}
		else {
			temp[index++] = a[begin2++];
		}
	}
	while (begin1 < end1) {
		temp[index++] = a[begin1++];
	}
	while (begin2 < end2) {
		temp[index++] = a[begin2++];
	}
}

void _MergeSort(int* a, int left, int right, int* temp) {
	if (right - left > 1) {
		int mid = left + ((right - left) >> 1);
		_MergeSort(a, left, mid, temp);
		_MergeSort(a, mid, right, temp);
		MergeData(a, left, mid, right, temp);
		memcpy(a + left, temp + left, sizeof(int*)* (right - left));
	}
}

void MergeSort(int* a, int size) {
	int* temp = (int*)malloc(sizeof(int) * size);
	if (NULL == temp) {
		assert(0);
		return;
	}
	_MergeSort(a, 0, size, temp);
	free(temp);
}

// 循环方式
void MergeSort1(int* a, int size) {
	int* temp = (int*)malloc(sizeof(int) * size);
	if (NULL == temp) {
		assert(0);
		return;
	}
	int gap = 1;
	while (gap < size) {
		for (int i = 0; i < size; i += 2 * gap) {
			int left = i;
			int mid = left + gap;
			int right = mid + gap;
			MergeData(a, left, mid, right, temp);
		}
		memcpy(a, temp, sizeof(int) * size);
		gap *= 2;
	}
	free(temp);
}
  • 缺点在于需要O(N)的空间复杂度
  • 时间复杂度: O(N*logN)
  • 空间复杂度: O(N)
  • 是一种稳定的排序算法

排序算法复杂度及稳定性对比

image-20200302162431534


我们的征途是星辰大海!