C++模板排序算法

小灰灰 2023-07-03 08:26 2阅读 0赞

# 交换函数 #

template<typename SORTVALUE>
    	void commonswap(SORTVALUE &exchange1, SORTVALUE &exchange2) 
    	{ 
    		SORTVALUE value(exchange2);
    		exchange2 = exchange1;
    		exchange1 = value;
    	}

# 冒泡排序 #

template<typename SORTVALUE>
    	void BubbleSort(SORTVALUE sortBegin, SORTVALUE sortEnd)
    	{ 
    		for (int i = 0; i < sortEnd - sortBegin - 1; ++i)
    		{ 
    			for (int j = 0; j < sortEnd - sortBegin - 1 - i; ++j)
    			{ 
    				if ((*(sortBegin + j) > *(sortBegin + j + 1))) { 
    					commonswap(*(sortBegin + j + 1), *(sortBegin + j));
    				}
    			}
    		}
    	}

插入排序

template <typename SORTVALUE>
    	void InsertSort(SORTVALUE sortBegin, SORTVALUE sortEnd)
    	{ 
    		for (int i = 1; i < sortEnd - sortBegin; ++i)
    		{ 
    			int j = i - 1;
    			while (j >= 0 && *(sortBegin + j) > *(sortBegin + j + 1))
    			{ 
    				commonswap(*(sortBegin + j + 1), *(sortBegin + j));
    				j--;
    			}
    		}
    	}

# 希尔排序 #

template <typename SORTVALUE>
    	void ShellSort(SORTVALUE sortBegin, SORTVALUE sortEnd)
    	{ 
    		for (auto shellIndex = (sortEnd - sortBegin) / 2; shellIndex > 0; shellIndex /= 2)
    		{ 
    			for (int i = 0; i < sortEnd - sortBegin - 1; ++i)
    			{ 
    				for (int j = 0; j < sortEnd - sortBegin - shellIndex; ++j)
    				{ 
    					if (*(sortBegin + j) > *(sortBegin + j + shellIndex)) { 
    						commonswap(*(sortBegin + j + shellIndex), *(sortBegin + j));
    					}
    				}
    			}
    		}
    	}

# 选择排序 #

template<typename SORTVALUE>
    	void SelectSort(SORTVALUE sortBegin, SORTVALUE sortEnd)
    	{ 
    		for (int i = 0; i < sortEnd - sortBegin - 1; ++i)
    		{ 
    			int index = i;
    			for (int j = i + 1; j < sortEnd - sortBegin; ++j)
    			{ 
    				if (*(sortBegin + index) > *(sortBegin + j)) { 
    					index = j;
    				}			
    			}
    
    			if (index != i) { 
    				commonswap(*(sortBegin + index), *(sortBegin + i));
    			}
    		}
    	}

# 快速排序 #

template<typename SORTVALUE>
    	void QuickSort(SORTVALUE sortBegin, SORTVALUE sortEnd)
    	{ 
    		if (sortBegin == sortEnd - 1){ 
    			return;
    		}
    
    		SORTVALUE baseValue(sortBegin);
    		SORTVALUE left(sortBegin);
    		SORTVALUE right(sortEnd - 1);
    
    		while (left != right)
    		{ 
    			while (*right >= *baseValue && left != right) { 
    				right--;
    			}
    
    			while (*left <= *baseValue && left != right) { 
    				left++;
    			}
    
    			commonswap(*(left), *(right));
    		}
    
    		commonswap(*(baseValue), *(left));
    		if (sortBegin != right) { 
    			QuickSort(sortBegin, right);
    		}
    		if (right + 1 != sortEnd) { 
    			QuickSort(right + 1, sortEnd);
    		}
    	}

# 归并排序 #

template<typename P_SORT,typename SORTVALUE>
    	void MergeSort(P_SORT sortBegin, P_SORT sortMid, P_SORT sortEnd, SORTVALUE valueBegin)
    	{ 
    		if (sortBegin == sortEnd - 1) { 
    			return;
    		}
    
    		P_SORT left(sortBegin);
    		P_SORT right(sortMid);
    
    		std::vector<SORTVALUE> sortValue;
    		sortValue.clear();
    		while (left < sortMid && right < sortEnd)
    		{ 
    			if (*left <= *right) { 
    				sortValue.push_back(*left++);
    			}
    			else { 
    				sortValue.push_back(*right++);
    			}
    		}
    
    		while (left < sortMid)
    		{ 
    			sortValue.push_back(*left++);
    		}
    		while (right < sortEnd)
    		{ 
    			sortValue.push_back(*right++);
    		}
    
    		std::vector<SORTVALUE>::iterator iter = sortValue.begin();
    		for (; iter != sortValue.end(); ++iter, ++sortBegin) { 
    			*sortBegin = *iter;
    		}
    	}
    
    	template<typename SORTVALUE>
    	void MergeSort(SORTVALUE sortBegin, SORTVALUE sortEnd)
    	{ 
    		if (sortBegin < sortEnd - 1) { 	
    			
    			MergeSort(sortBegin, sortBegin + (sortEnd - sortBegin) / 2);
    			MergeSort(sortBegin + (sortEnd - sortBegin) / 2, sortEnd);
    			MergeSort(sortBegin, sortBegin + (sortEnd - sortBegin) / 2, sortEnd, *sortBegin);
    		}
    	}