字符串的排序

怼烎@ 2022-08-07 08:46 196阅读 0赞

题目：输入一个字符串，打印出该字符串中字符的所有排序

《剑指offer》解

void Premutation(char *pStr)
    {
    	if (pStr == NULL)
    		return;
    	Premutation(pStr, pStr);
    }
    
    void Premutation(char *pStr, char *pBegin)
    {
    	if (*pBegin == '\0')	cout << pStr << endl;
    	else
    	{
    		for (char *pch = pBegin; *pch != '\0'; ++pch)
    		{
    			char temp = *pch;				*pch = *pBegin;			*pBegin = temp;
    			Premutation(pStr, pBegin + 1);
    			temp = *pch;			*pch = *pBegin;				*pBegin = temp;
    		}
    	}
    }

注：这种解法没有考虑，字符串中有相同的字符

在这中方法上进行修改——考虑字符串中可能出现相同的字符

#include<iostream>
    using namespace std;
    
    void Premutation(char *pStr);
    void Premutation(char *pStr, char *pBegin);
    void QuickSort(char *pStr);
    void QuickSort(char *pStr,int low,int hight);
    
    // 字符串排序 可以对字符串中有相同字符进行正确处理
    void Premutation(char *pStr)
    {
    	if (pStr == NULL)
    		return;
    	QuickSort(pStr);//对字符串进行排序
    	Premutation(pStr, pStr);
    }
    
    void Premutation(char *pStr, char *pBegin)
    {
    	if (*pBegin == '\0')	cout << pStr << endl;
    	else
    	{
    		for (char *pch = pBegin; *pch != '\0'; ++pch)
    		{
    			if (pBegin != pch && *pBegin == *pch)
    				continue;
    			char temp = *pch;				*pch = *pBegin;			*pBegin = temp;
    			Premutation(pStr, pBegin + 1);
    			temp = *pch;			*pch = *pBegin;				*pBegin = temp;
    		}
    	}
    }
    
    //快速排序
    void QuickSort(char *pStr)
    {
    	if (*pStr == '\0')
    		return;
    	QuickSort(pStr, 0, strlen(pStr)-1);
    }
    
    void QuickSort(char *pStr, int low, int hight)
    {
    	if (low >= hight)	return;
    
    	int first = low, last = hight;
    	char key = pStr[first];
    
    	while (first < last)
    	{
    		while (first < last&&pStr[last] >= key)		
    			--last;
    		pStr[first] = pStr[last];
    
    		while (first < last && pStr[first] <= key)	
    			++first;
    		pStr[last] = pStr[first];
    	}
    	pStr[first] = key;
    	QuickSort(pStr, low, first - 1);
    	QuickSort(pStr, first + 1, hight);
    }
    
    
    int main()
    {
    	char p[] = "acba";
    	Premutation(p);
    	cout << endl;
    }