实用程序哈希表 趣味程序五子棋

Question

提交实用性程序如：数值排序、哈希表、回溯算法；趣味程序：五子棋

Answer 1

数值排序的常用算法：冒泡排序、选择排序、希尔排序、堆排序等等。
五子棋程序参考：

https://blog.csdn.net/weixin_61866141/article/details/125996622

数值排序的代码（含冒泡排序、选择排序、希尔排序、堆排序等），根据需要提取自己需要的即可：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAXLEN 10
//生成随机数组
void createSjArray(int a[])
{
    for (int i = 0; i < MAXLEN; i++)
        a[i] = rand()%500;
}


//冒泡排序
void Bubblesort(int* num, int n)
{
    int i, j, t;
    for (i = 0; i < n - 1; i++)
    {
        for (j = 0; j < n - 1 - i; j++)
        {
            if (num[j] > num[j + 1])  //从小到大，升序
            {
                t = num[j];
                num[j] = num[j + 1];
                num[j + 1] = t;
            }
        }
    }
}

//选择排序，升序
void SelectSort(int* num, int n)
{
    int i, j;
    int minindex, tmp;
    for (i = 0; i < n - 1; i++)
    {
        minindex = i;
        //找出第i小的数所在的位置
        for (j = i + 1; j < n; j++)
        {
            if (num[j] < num[minindex])
                minindex = j;
        }

        //将第i小的数放在第i个位置
        if (i != minindex)
        {
            tmp = num[i];
            num[i] = num[minindex];
            num[minindex] = tmp;
        }
    }

}

//插入排序
void InsertSort(int* nums, int numsSize)
{
    int i, j, temp;
    for (i = 1; i < numsSize; i++)
    {
        {
            if (nums[i] < nums[i - 1])
            {
                temp = nums[i];
                for (j = i - 1; j >= 0; j--)
                {
                    if (nums[j] > temp)
                        nums[j + 1] = nums[j];
                    else
                        break;
                }
                nums[j + 1] = temp;
            }
        }
    }
}

//希尔排序
void shellSort(int* a, int len)
{
    int i, j, k, tmp, gap;  // gap 为步长
    for (gap = len / 2; gap > 0; gap /= 2) {  // 步长初始化为数组长度的一半，每次遍历后步长减半,
        for (i = 0; i < gap; ++i) { // 变量 i 为每次分组的第一个元素下标 
            for (j = i + gap; j < len; j += gap) { //对步长为gap的元素进行直插排序，当gap为1时，就是直插排序
                tmp = a[j];  // 备份a[j]的值
                k = j - gap;  // j初始化为i的前一个元素（与i相差gap长度）
                while (k >= 0 && a[k] > tmp) {
                    a[k + gap] = a[k]; // 将在a[i]前且比tmp的值大的元素向后移动一位
                    k -= gap;
                }
                a[k + gap] = tmp;
            }
        }
    }
}


//显示数组
void showArray(int* num, int n)
{
    for (int i = 0; i < n; i++)
    {
        if ((i + 1) % 10 == 0)
            printf("%d\n", num[i]);
        else
            printf("%d ", num[i]);
    }
    printf("\n");
}

//快速排序
void QuickSort(int  nums[], int L, int R) {
    int i, j = L, temp, k = nums[R];
    if (L < R) {
        for (i = L; i < R; i++) {
            if (nums[i] < k) {
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                j++;
            }
        }
        temp = nums[R];
        nums[R] = nums[j];
        nums[j] = temp;
        QuickSort(nums, L, j - 1);
        QuickSort(nums, j + 1, R);
    }
    return;
}
//归并
void merge(int* nums, int L, int M, int R) {
    int LEFT_SIZE = M - L;
    int RIGHT_SIZE = R - M + 1;
    int* left = (int*)malloc(LEFT_SIZE * sizeof(int));
    int* right = (int*)malloc(RIGHT_SIZE * sizeof(int));
    int i, j, k;
    for (i = L; i < M; i++) left[i - L] = nums[i];
    for (i = M; i <= R; i++) right[i - M] = nums[i];
    i = 0, j = 0, k = L;
    while (i < LEFT_SIZE && j < RIGHT_SIZE) {
        if (left[i] < right[j]) {
            nums[k] = left[i];
            i++;
            k++;
        }
        else {
            nums[k] = right[j];
            j++;
            k++;
        }
    }
    while (i < LEFT_SIZE) {
        nums[k] = left[i];
        k++;
        i++;
    }
    while (j < RIGHT_SIZE) {
        nums[k] = right[j];
        k++;
        j++;
    }
}
void mergesort(int* nums, int L, int R) {
    //L为数组的开始下表，R为数组的结束下标，以[1,2,3,4]为例，L=0，R=3；
    if (L == R)return;
    else {
        int M = (R + L) / 2;
        mergesort(nums, L, M);
        mergesort(nums, M + 1, R);
        merge(nums, L, M + 1, R);
    }
}

//堆排序
void swap(int array[], int x, int y) {
    int key = array[x];
    array[x] = array[y];
    array[y] = key;
}
// 从小到大排序
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
    int parent = i;                    // 父节点下标
    int child = 2 * i + 1;            // 子节点下标
    while (child < n) {
        if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
            child++;
        }
        if (array[parent] < array[child]) { // 判断父节点是否小于子节点
            swap(array, parent, child);     // 交换父节点和子节点
            parent = child;                 // 子节点下标 赋给 父节点下标
        }
        child = child * 2 + 1; // 换行，比较下面的父节点和子节点
    }
}

void BuildHeap(int array[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
        Down(array, i, size);                 // 否则有的不符合大顶堆定义
    }
}

void HeapSort(int array[], int size) {
    BuildHeap(array, size); // 初始化堆

    for (int i = size - 1; i > 0; i--) {
        swap(array, 0, i); // 交换顶点和第 i 个数据
        // 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
        Down(array, 0, i); // 重新建立大顶堆        
    }
}






int main()
{
    int a[MAXLEN];
    int i = 0;
    srand((unsigned int)time(0)); //生成随机数种子

    printf("选择排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    SelectSort(a, MAXLEN); //调用选择排序算法
    printf("排序后：");
    showArray(a, MAXLEN);
   

    printf("\n冒泡排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    Bubblesort(a, MAXLEN); //调用冒泡排序算法
    printf("排序后：");
    showArray(a, MAXLEN);

    
    printf("\n插入排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    InsertSort(a, MAXLEN); //调用插入排序算法
    printf("排序后：");
    showArray(a, MAXLEN);


    printf("\n希尔排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    shellSort(a, MAXLEN); //调用希尔排序算法
    printf("排序后：");
    showArray(a, MAXLEN);
    
    
    printf("\n快速排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    QuickSort(a, 0, MAXLEN - 1); //调用快速排序算法
    printf("排序后：");
    showArray(a, MAXLEN);


    printf("\n归并排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    mergesort(a, 0, MAXLEN - 1); //调用归并排序算法
    printf("排序后：");
    showArray(a, MAXLEN);
    
    printf("\n堆排序：\n");
    printf("排序前：");
    createSjArray(a);
    showArray(a, MAXLEN);
    HeapSort(a, MAXLEN); //调用堆排序算法
    printf("排序后：");
    showArray(a, MAXLEN);
    
    

    system("pause");
    return 0;
}