C++ 算法教程

2024-06-16

本文作者原创，首发在本博客；CSDN 上的同名文章已标注为转载并回链到本页：https://blog.csdn.net/qq_30220519/article/details/139724486

归并排序

#include<iostream>
using namespace std;
template <class T>
void Merge(T data[],int start,int mid,int end)
{
	int len1 = mid - start + 1, len2 = end - mid;
	int i, j, k;
	T* left = new int[len1];
	T* right = new int[len2];
	for (i = 0; i < len1; i++)
		left[i] = data[i + start];
	for (i = 0; i < len2; i++)
		right[i] = data[i + mid + 1];
	i = 0, j = 0;
	for (k = start; k < end; k++)
	{
		if (i == len1 || j == len2)
			break;
		if (left[i] <= right[j])
			data[k] = left[i++];
		else
			data[k] = right[j++];
	}
	while (i < len1)
		data[k++] = left[i++];
	while (j < len2)
		data[k++] = right[j++];
	delete[] left;
	delete[] right;
}
template <class T>
void MergeSort(T data[], int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;
		MergeSort(data, start,mid);
		MergeSort(data, mid + 1, end);
		Merge(data, start, mid, end);
	}
}
void show(int*temp,int n)
{
	for (int i = 0; i < n; i++)
		cout << temp[i] << "  ";
}
void main()
{
	int temp[8];
	for (int i = 0; i < 8; i++)
		cin >> temp[i];
	MergeSort<int>(temp, 0,7);
	show(temp, 8);
}

冒泡排序_相邻交换

#include <stdio.h>  
  
int main()  
{  
    int i,p,temp;  
    int array[10] = {2,6,1,9,4,7,5,8,3,0};  
    printf("Display this array:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",array[i]);  
    }  
    for(i = 1;i < 10; ++i)
{
   for(p = 0; p < 10; ++p)
  {
       if(array[i]>array[p])
      {
	array[i] = 	array[i]^array[p];
	array[p] = array[i]^array[p];	
	array[i] = array[i]^array[p];
      }
  }
}
    printf("\n");  
    printf("After sorting,this array is:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",array[i]);  
    }     
    printf("\n");  
    return 0;  
}

判断循环链表

1.建立set集合，每次遍历存储元素，当集合大小不变，但循环仍在继续时说明存在循环，并得出该位置
2.定义双指针遍历:一个指针每次移动一个节点，一个指针每次移动2个节点，当2个节点指针在一个节点指针后面时，此链表存在循环。
3.链表反向
4.构造双向链表

swap

a:1001
b:1100
a=a^b; a:0101
b=a^b; b:1001
a=a^b; a:1100

a = a + b;
b = a - b;
a = a - b;

直插排序

#include <stdio.h>  
  
int main()  
{  
    int i,p,temp;  
    int array[10] = {2,6,1,9,4,7,5,8,3,0};  
    printf("Display this array:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",array[i]);  
    }  
      	//选择第一个数做为起始排序
	for(i = 1; i < 10; ++i)
	{
		temp = array[i];	//待插入排序数
		for(p = i-1; p >=0 && array[p]>temp; --p)
		{//遍历已排序数列表
			{//如果当前数大小在已排序范围中，开始向右位移一个数让出空间
				array[p+1] = array[p];	
			}
		}
		//找到待排序数的位置，在让出的空间直接插入		
		array[p+1]=temp;			
	}
    printf("\n");  
    printf("After sorting,this array is:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",array[i]);  
    }     
    printf("\n");  
    return 0;  
}

#include <stdio.h>  
  
int main()  
{  
    int i,j,t;  
    int array[10]={2,7,1,8,5,9,3,4,0,6};  
    printf("\nDisplay this array:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",array[i]);  
    }  
    printf("\n");  
    for(i=1;i<=9;i++)  
    {  //遍历
        int t = i-1;  //假设当前数为最小数
        for(j=i;j<10;j++)  
        {  
            if(array[j]<array[t])  
            {  //遍历找到最小的数,保存最小数索引
                t=j;  
            }  
        }  
        if(t!=(i-1))  
        {  //交换最小数与假设最小数
            int temp = 0;  
            temp=array[i-1];  
            array[i-1]=array[t];  
            array[t]=temp;  
        }  
    }  
    printf("After sorting,this array is:\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d ",array[i]);  
    }  
    printf("\n");  
    return 0;  
}