排序算法汇总

插入排序

void insertionSort(std::vector<int>& arr)
{
	if (arr.size() <= 1)
		return;
	for (int i = 1; i < arr.size(); ++i)
	{
		int j = i - 1;
		int key = arr[i];
		while (j >= 0 && arr[j] > key)
		{
			arr[j + 1] = arr[j];
			--j;
		}
		arr[j + 1] = key;
	}
}

时间复杂度:O(n^2),空间复杂度O(n)

分治排序

void merge(std::vector<int>& arr, int p, int q, int r)
{
	std::vector<int> left;
	std::vector<int> right;
	for (int i = p; i < q; ++i)
		left.push_back(arr[i]);
	left.push_back(INT_MAX);
	for (int i = q; i < r; ++i)
		right.push_back(arr[i]);
	right.push_back(INT_MAX);
	int k = 0, t = 0;
	for (int i = p; i < r; ++i)
	{
		if (left[k] <= right[t])
		{
			arr[i] = left[k++];
		}
		else
		{
			arr[i] = right[t++];
		}
	}
}

void mergeSort(std::vector<int>& arr, int p, int r)
{
	if (r - p > 1)
	{
		int mid = (p + r) / 2;
		mergeSort(arr, p, mid);
		mergeSort(arr, mid, r);
		merge(arr, p, mid, r);
	}
}

时间复杂度:O(nlogn),空间复杂度:O(n)

希尔排序

void shellSort(std::vector<int>& arr)
{
	int d = arr.size() / 2;
	while (d >= 1)
	{
		for (int i = d; i < arr.size(); ++i)
		{
			int temp = arr[i];
			int j = i - d;
			while(j >= 0 && arr[j] > temp)
			{
				arr[j + d] = arr[j];
				j -= d;
			}
			arr[j + d] = temp;
		}
		d /= 2;
	}
}

时间复杂度:O(nlogn),空间复杂度:O(n)

快排

int partition(std::vector<int>& arr, int p, int q)
{
	int c = rand() % (q - p + 1) + p;
	std::swap(arr[c], arr[q]);
	int i = p - 1;
	int j = p;
	for (; j < q; ++j)
	{
		if (arr[j] < arr[q])
		{
			++i;
			std::swap(arr[i], arr[j]);
		}
	}
	std::swap(arr[i + 1], arr[q]);
	return i + 1;
}

void quickSort(std::vector<int>& arr, int p, int q)
{
	if (p < q)
	{
		int index = partition(arr, p, q);
		quickSort(arr, p, index - 1);
		quickSort(arr, index + 1, q);
	}
}

时间复杂度:O(nlogn),空间复杂度:O(n)

快选希堆not stable

发表评论

电子邮件地址不会被公开。 必填项已用*标注

16 − 8 =

50 − 43 =