c++实现常见算法

我会带着你远行 2022-02-15 05:41 160阅读 0赞

### 文章目录 ###

*   *  排序算法
     *   *  快速排序法：
         *  归并排序法
         *  冒泡排序法
         *  插入排序法
         *  选择排序法

## 排序算法 ##

冒泡排序，合并排序法，插入排序法，选择排序法，快速排序法

### 快速排序法： ###

1.取左边第一个元素哨兵，从后向前找，比该元素大的，不动；比该元素小的，换位  
2.哨兵在左边，和最右边比，找小于哨兵的换位  
3.哨兵在右边，和最左边边，找大于哨兵的换位  
4.哨兵左边都比其大，右边都比其小；则两边各自做快排  
demo.cpp

int partition(int *pArr, int arrLen, int low, int high)
    {
    	int standarVal = pArr[low];
    	while (low < high)
    	{
    		while (low < high&& pArr[high] >= standarVal)
    		{//最右边元素比标准值要大时，保持循环，
    			high--;
    		}
    		if (low < high)//如果比标准值大时换位
    		{
    			int tmp = pArr[low];
    			pArr[low] = pArr[high];
    			pArr[high] = tmp;
    		}
    		printArray(pArr, arrLen);
    		while (low < high&& pArr[low] <= standarVal)
    		{//最左边元素比标准值要小时，保持循环，
    			low++;
    		}
    		if (low < high)//如果比标准值大时换位
    		{
    			int tmp = pArr[low];
    			pArr[low] = pArr[high];
    			pArr[high] = tmp;
    		}
    		printArray(pArr, arrLen);
    	}
    	return low; //返回中间值
    }
    bool quickSortImpl(int *pArr, int arrLen,int low,int high)
    {
    	printf("\nlow = %d, high = %d\n", low, high);
    	if (low < high)
    	{
    		//第一步：找到中间值    负责排序的函数
    		int centerPoint = partition(pArr, arrLen, low, high);
    		printf("\ncenterPoint =  %d\n", centerPoint);
    		//第二步：前半部分排序
    		quickSortImpl(pArr, arrLen, low, centerPoint - 1);
    
    		//第三步：后半部分排序
    		quickSortImpl(pArr, arrLen, centerPoint + 1, high);
    	}
    	return true;
    }
    bool quickSort(int *pArr, int arrLen, int *pTar)
    {
    	if (!pArr || !pTar)
    	{
    		return false;
    	}
    	for (int i = 0; i < arrLen; i++)
    	{
    		pTar[i] = pArr[i];
    	}
    	quickSortImpl(pTar, arrLen, 0, arrLen - 1);
    	return true;
    }

### 归并排序法 ###

先相邻的两两一组排序，排完后将相邻两组排序，依次排完

### 冒泡排序法 ###

demp.cpp

/*
    冒泡排序法
    */  
    #include <cstdlib>
    #include <iostream>
    using namespace std;
    void printArray(int *pArr, int n)
    {
    	for (int j = 0; j < n; j++)
    	{
    		cout << pArr[j] << " ";
    	}
    	cout << endl;
    }
    bool bubbleSort(int *pArr, int arrLen, int *pTar)
    {
    	if (!pArr || !pTar)
    	{
    		return false;
    	}
    	for (int i = 0; i < arrLen; i++)
    	{
    		pTar[i] = pArr[i];
    	} 
    	for (int i = 0; i < arrLen - 1; i++) //最后一个不用排
    	{
    		for(int j = 0;j < arrLen - i - 1;j++)
    		{
    			if (pTar[j] > pTar[j + 1])
    			{
    				int temp = pTar[j];
    				pTar[j] = pTar[j + 1];
    				pTar[j + 1] = temp;
    			}
    			
    		}
    		printArray(pTar, arrLen);
    	}
    	return true;
    }
    
    int main(void)
    {
    	int arr[5] = { 6,5,4,3,2 };
    	int tar[5] = { 0 };
    
    	printArray(arr, 5);
    	bubbleSort(arr, 5, tar);
    	//printArray(tar, 5);
    	system("pause");
    	return 0;
    }

### 插入排序法 ###

demo.cpp

bool insertSort(int *pArr, int arrLen, int *pTar)
    {
    	if (!pArr || !pTar)
    	{
    		return false;
    	}
    	for (int i = 0; i < arrLen; i++)
    	{
    		pTar[i] = pArr[i];
    	}
    	//一共要排n-1次
    	for (int i = 0; i < arrLen - 1; i++)
    	{
    		//每次选一个哨兵 i+1   第0个元素不用插入
    		//如果哨兵比前面相邻的元素大，就不用排序，直接插入
    		if (pTar[i] > pTar[i + 1]) 
    		{
    			int x = pTar[i + 1]; //x为哨兵
    			int j = i;
    			while (x < pTar[j]) //找到合适的位置
    			{
    				pTar[j + 1] = pTar[j]; //该元素向后移动一位
    				j--;
    				if (j < 0) //防止插在第一个位置时，循环不能终止
    				{
    					break;
    				}
    			}
    			//出来时,j+1,哨兵不能把比他小的值覆盖，索引要向前移动一位
    			pTar[j + 1] = x;
    		}
    		printArray(pTar, arrLen);
    	}
    
    	return true;
    }

### 选择排序法 ###

demo.cpp

//在指定的集合中找出最小索引  from（含）,to(不含)
    int selectMinKey(int *pArr, int from, int to)
    {
    	int k = from; //存放最小值的索引
    	for (int i = from + 1; i < to; i++)
    	{
    		if (pArr[k] > pArr[i])
    		{
    			k = i;
    		}
    	}
    	return k;
    }
    
    bool selectSort(int *pArr, int arrLen, int *pTar)
    {
    	if (!pArr || !pTar)
    	{
    		return false;
    	}
    	for (int i = 0; i < arrLen; i++)
    	{
    		pTar[i] = pArr[i];
    	}
    	for (int i = 0; i < arrLen; i++)
    	{
    		int key = selectMinKey(pTar, i, arrLen); // 找到最小值
    		if (key != i)
    		{
    			//交换位置
    			int tmp = pTar[i];
    			pTar[i] = pTar[key];
    			pTar[key] = tmp;
    		}
    		printArray(pTar, arrLen);
    	
    	}
    	return true;
    }