• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

排序C++实现

互联网 diligentman 2个月前 (02-26) 18次浏览
//插入排序
void insertsort(vector<int>& arr)
{
	for (int i = 1; i < arr.size(); i++)
	{
		int key = arr[i];
		int end = i - 1;
		while (key < arr[end])
		{
			arr[end + 1] = arr[end];
			--end;
			if (end < 0)
				break;
		}
		arr[end + 1] = key;
	}
}

//选择排序
void selectSort(vector<int>& arr)
{
	for (int i = 0; i < arr.size(); i++)
	{
		int min = i;
		for (int j = i; j < arr.size(); j++)
		{
			if (arr[j] < arr[min])
				min = j;
		}
		swap(arr[i], arr[min]);
	}
}

//堆排序
void ad_down(size_t pos, vector<int>& arr, size_t size);
void heap_sort(vector<int>& arr)
{
	//建堆
	int pos_end = (arr.size() - 2) / 2;
	for (int pos = pos_end; pos >= 0; pos--)
	{
		ad_down(pos, arr, arr.size());
	}
	//堆排序
	size_t pos_end2 = arr.size() - 1;
	while (pos_end2 > 0)
	{
		swap(arr[0], arr[pos_end2]);
		ad_down(0, arr, pos_end2);
		pos_end2--;
	}
}

//向下调整
void ad_down(size_t pos,vector<int>& arr,size_t size)
{
	size_t parent_pos = pos;
	size_t child_pos = pos * 2 + 1;
	while (child_pos < size)
	{
		if (child_pos<size-1 && arr[child_pos] < arr[child_pos + 1])
			child_pos++;
		if (arr[parent_pos] < arr[child_pos])
		{
			swap(arr[parent_pos], arr[child_pos]);
			parent_pos = child_pos;
			child_pos = child_pos * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//冒泡排序
void bubble_sort(vector<int>& arr)
{
	int n = arr.size();
	while (n--)
	{
		bool no_swap = 1;
		for (int i = 0; i < n; i++)
		{
			if (arr[i] > arr[i + 1])
			{
				swap(arr[i], arr[i + 1]);
				no_swap = 0;
			}
		}
		if (no_swap)
			break;
	}
}

//快速排序
//三数取中
size_t quick_mid(vector<int>& arr, size_t left, size_t right)
{
	int mid_num = arr[(right - left) / 2];
	int a = left, b = right-1, c = (right - left) / 2;
	if (arr[a] < arr[b])
	{
		if (arr[a] < arr[c])
		{
			if (arr[b] < arr[c])
				return b;
			else if (arr[b] >= arr[c])
				return c;
		}
		else if (arr[a] >= arr[c])
			return a;
	}
	else if (arr[a] >= arr[b])
	{
		if (arr[a] < arr[c])
			return a;
		else if (arr[a] >= arr[c])
		{
			if (arr[b] < arr[c])
				return c;
			else if (arr[b] >= arr[c])
				return b;
		}
	}
}

//hore法
size_t divide_hore(vector<int>& arr, size_t left, size_t right)
{
	int pos = quick_mid(arr,left,right);
	swap(arr[pos], arr[right-1]);
	int key = arr[right-1];
	size_t begin = left, end = right-1;
	while (begin < end)
	{
		while (begin < end && arr[begin] <= key)
			begin++;
		while (begin < end && arr[end] >= key)
			end--;
		swap(arr[begin], arr[end]);
	}
	swap(arr[begin], arr[right-1]);
	return begin;
}

//挖坑法
size_t divide_potholing(vector<int>& arr, size_t left, size_t right)
{
	int pos = quick_mid(arr, left, right);
	swap(arr[pos], arr[right - 1]);
	size_t begin = left, end = right - 1;
	int key = arr[end];
	while (begin < end)
	{
		while (begin < end && arr[begin] <= key)
			begin++;
		if (begin < end)
		{
			arr[end] = arr[begin];
			end--;
		}
		while (begin < end && arr[end] >= key)
			end--;
		if (begin < end)
		{
			arr[begin] = arr[end];
			begin++;
		}
	}
	arr[begin] = key;
	return begin;
}

//前后指针法
size_t divide_pointer(vector<int>& arr, size_t left, size_t right)
{
	int pos = quick_mid(arr, left, right);
	swap(arr[pos], arr[right - 1]);
	int key = arr[right - 1];
	size_t cur = left;
	size_t prev = left - 1;
	while (cur < right)
	{
		if (arr[cur] < key && ++prev != cur)
			swap(arr[cur], arr[prev]);
		cur++;
	}
	swap(arr[++prev], arr[right - 1]);
	return prev;
}

//快速排序递归调用
void quick_sort_recursion(vector<int>& arr,size_t begin,size_t end)
{
	if (end-begin > 1)
	{
		size_t div = divide_pointer(arr, begin, end);
		quick_sort_recursion(arr,begin, div);
		quick_sort_recursion(arr, div + 1, end);
	}
}

//快速排序循环调用
void quick_sort_loop(vector<int>& arr, size_t begin, size_t end)
{
	stack<size_t> s;
	s.push(begin);
	s.push(end);
	while (!s.empty())
	{
		size_t right = s.top();
		s.pop();
		size_t left = s.top();
		s.pop();
		if (right - left > 1)
		{
			int div = divide_pointer(arr, left, right);
			s.push(left);
			s.push(div);
			s.push(div + 1);
			s.push(right);
		}
	}
}


//归并
void merge_data(vector<int>& arr, size_t left, size_t mid, size_t right, int* tmp)
{
	size_t begin1 = left, end1 = mid;
	size_t begin2 = mid, end2 = right;
	size_t index = left;
	while (begin1 < end1 && begin2 < end2)
	{
		if (arr[begin1] <= arr[begin2])
			tmp[index++] = arr[begin1++];
		else
			tmp[index++] = arr[begin2++];
	}
	while (begin1 < end1)
		tmp[index++] = arr[begin1++];
	while (begin2 < end2)
		tmp[index++] = arr[begin2++];
}

void _merge_sort(vector<int>& arr, size_t begin, size_t end, int* tmp)
{
	if (end - begin > 1)
	{
		size_t mid = begin+((end - begin) >> 1);
		_merge_sort(arr, begin, mid, tmp);
		_merge_sort(arr, mid, end, tmp);
		merge_data(arr, begin, mid, end, tmp);

		memcpy(&arr[0]+begin, tmp+begin, sizeof(arr[0])*(end-begin));
	}
}

void merge_sort(vector<int>& arr)
{
	int* p = new int[sizeof(arr)];
	_merge_sort(arr, 0, arr.size(), p);
	delete[] p;
}

 

展开阅读全文

c++

© 著作权归作者所有

举报

打赏

0


0 收藏

微信
QQ
微博

分享

作者的其它热门文章

C++auto,for范围循环,指针空值
【项目】——智能AI语音管家tamako
C语言在函数形参列表用结构体类型定义变量报错的问题
c语言循环判断语句常见习题


程序员灯塔
转载请注明原文链接:排序C++实现
喜欢 (0)