current position:Home>Seven major sorting C language data structure and algorithm entertainment speed measurement non-professional

Seven major sorting C language data structure and algorithm entertainment speed measurement non-professional

2022-10-25 03:33:01Rondox

可能有错 Please correct me if there is

Associated with the first edition:CSDN

文件结构

 

1.bubbleSort.c 冒泡排序 内容

//bubbleSort.c内容
#include "megadata.h"
void bubbleSort(int* arr, int size) {
    int tmp;
    for (size_t i = 0; i < size; i++)
    {
        for (size_t j = 0; j < size - i - 1; j++)
        {
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

2.bucketSort.c排序 桶排序

#include "megadata.h"

void bucketSort(int* arr,int size) {
	//Calculate how many pieces are in each bucket 10位 0-9
	int* counts = (int*)malloc(sizeof(int) * 10);
	memset(counts, 0, sizeof(int) * 10);
	int tmp; //tmpis a temporary variable for each number of digits
	int index = 0;
	//10行 array of numbers 二级指针
	int** units = (int*)malloc(sizeof(int) * 10);
	memset(units, 0, sizeof(int) * 10);
	for (size_t i = 0; i < 10; i++)
	{
		units[i] = (int*)malloc(sizeof(int) * size);
		memset(units[i], 0, sizeof(int) * size);
	}

	
	//获得最大位数
	int max = arr[0];
	for (size_t i = 0; i < size; i++)
	{
		if (arr[i] > max) {
			max = arr[i];
		}
	}
	char maxStr[999] = { 0 };//要设置长度
	sprintf(maxStr,"%d",max );
	int maxLen = strlen(maxStr);
	for (size_t k = 0; k < maxLen; k++) //对应pow 0-个 1-十 2-百
	{
		//The array is cleared every round
		index = 0;
		memset(counts, 0, sizeof(int) * 10);
		for (size_t i = 0; i < 10; i++)
		{
			memset(units[i], 0, sizeof(int) * size);
		}

		//The first round of one-digit sorting 10个桶
		for (size_t i = 0; i < size; i++)
		{
			tmp = arr[i] / (int)pow(10, k) % 10;//个位
			units[tmp][counts[tmp]] = arr[i];
			counts[tmp]++;
		}
		//Reassignment is done at the end of each round of sortingarr

		for (size_t i = 0; i < 10; i++)
		{
			for (size_t j = 0; j < counts[i]; j++)
			{
				arr[index] = units[i][j];
				index++;
				//printf("|%d| ", units[i][j]);
			}
			//printf("-------------------------------\n");
		}
	}

	

	for (size_t i = 0; i < 10; i++)
	{
		free(units[i]);
	}
	free(units);
	free(counts);


}

void main0077() {


	int arr[] = { 53,3,542,748,14,214 };
	bucketSort(arr, 6);
	for (size_t i = 0; i < sizeof(arr)/sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
}

3.插入排序 insertSort.c

#include "megadata.h"
void insertSortOne(int* arr, int size) {
    int preIndex, tmp;
    for (size_t i = 1; i < size; i++)
    {
        tmp = arr[i];
        preIndex = i - 1;
        while (tmp < arr[preIndex] && preIndex >= 0) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = tmp;
    }
}

4.归并排序 mergeSort.c

#include "megadata.h"
void remedySort(int* arr, int left, int mid, int right, int* tmpArr) {
    int index = 0;
    int i = left;
    int j = mid + 1;
    //两段  [left~mid  mid+1~right]
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            tmpArr[index] = arr[i];
            i++;
            index++;
        }
        else {
            tmpArr[index] = arr[j];
            j++;
            index++;
        }
    }

    if (i > mid) {
        while (j <= right) {
            tmpArr[index] = arr[j];
            j++;
        }
    }
    if (j > right) {
        while (i <= mid) {
            tmpArr[index] = arr[i];
            i++;
        }
    }

}



void mergeSort(int* arr, int left, int right, int* tmpArr) {
    //recursive you alsowhile什么啊
    if (left < right)
    {
        int mid = (left + right) / 2;
        //mergeSort(arr, left, mid);
        //mergeSort(arr, mid+1, right);
        mergeSort(arr, left, mid, tmpArr);
        mergeSort(arr, mid + 1, right, tmpArr);
        remedySort(arr, left, mid, right, tmpArr);

    }

}

void mergeSortEntrance(int* arr, int size) {
    int* tmpArr = (int*)malloc(sizeof(int) * size);
    mergeSort(arr, 0, size - 1, tmpArr);


}

5.quickSort.c 快速排序

#include "megadata.h"
void quickSort(int* arr, int left, int right) {
    //It should not directly change what is sent over`left right值 A copy needs to be saved
    int l = left;
    int r = right;
    int vio = arr[(l + r) / 2];
    while (l < r) {
        while (arr[l] < vio) l++;
        while (arr[r] > vio) r--;
        if (l >= r) break;//l=rinfinite loop
        int tmp = arr[r];
        arr[r] = arr[l];
        arr[l] = tmp;
        if (arr[l] == vio) r--;
        if (arr[r] == vio) l++;
    }

    if (l == r) {
        l++;
        r--;
    }
    //At the end of each run, only the left side corresponding to the current middle value can be guaranteed to be smaller than the middle The right is larger than the middle 
    //But there is no guarantee of order in the left and right parts in the middle 所以需要递归
    //And after it's overl肯定大于r Even equal to the above expression will split it
    //But still need to judge ifl是大于right或者r小于left 就不运行

    if (left < r) {
        quickSort(arr, left, r);
    }
    if (l < right) {
        quickSort(arr, l, right);
    }


}

void quickSortEntrance(int* arr, int size) {
    quickSort(arr, 0, size - 1);
}   //I am your mother Why don't multiple parameters report an error

6.选择排序  selectSort.c

#include "megadata.h"
void selectSort(int* arr, int size) {
    int min, minIndex; //Each round is the corresponding minimum
    for (size_t k = 0; k < size - 1; k++)
    {
        min = arr[k];
        minIndex = k;
        for (size_t i = k; i < size; i++)
        {//i从k开始 因为k前面有序
            if (arr[i] < min) {
                minIndex = i;
                min = arr[i];
            }
        }
        arr[minIndex] = arr[k];
        arr[k] = min;
    }
}

7.shellSort.c 希尔排序

#include "megadata.h"

void shellSort(int* arr, int size) {
    int tmp;
    for (size_t gap = size; gap > 0; gap = gap / 2)
    {
        //第二轮的时候 
        //gap=2 
        for (size_t i = gap; i < size; i++)
        {
            for (size_t j = i; j >= gap; j = j - gap)
            {//递减gapGo back and compare

                if (arr[j] < arr[j - gap]) {
                    tmp = arr[j];
                    arr[j] = arr[j - gap];
                    arr[j - gap] = tmp;
                }
            }

        }
    }



}

正文 主程序

megadata.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>
void bubbleSort(int* p, int size);
void selectSort(int* p, int size);
void insertSortOne(int* p, int size);
void shellSort(int* p, int size);
void quickSortEntrance(int* p, int size);
void mergeSortEntrance(int* p, int size);
void bucketSort(int* p, int size);

megadata.c

#include "megadata.h"

enum fun {//不能与函数值重名
    bubble=1,
    shell,
    select  ,
    insert  ,
    bucket,
    quick,
    merge   ,
};

char* enumCh[8] = {
    "HEAD", 
    "bubble"  ,
    "shell "  ,
    "select"  ,
    "insert"  ,
    "bucket"  ,

    "quick "  ,
    "merge "  ,
    
};


void generateMegaData(int size) {
    srand((size_t)time(NULL));
    FILE* fp = fopen(D:/大文件排序.txt", "w");
    if (!fp)  return;
    for (size_t i = 0; i < size; i++)  fprintf(fp, "%d\n", rand() % (100000));
    fclose(fp);
}


int* getArr(int size) {
    FILE* fp = fopen("D:/大文件排序.txt", "r");
    if (!fp) return;
    int* arr = (int*)malloc(sizeof(int) * size);
    //有问题 这里是sizeof(int)* size
    memset(arr, 0, sizeof(int)* size);
    int index=0;
    while (!feof(fp)) {
        fscanf(fp,"%d",&arr[index] );
        index++;
    }
    fclose(fp);
    return arr;
}





void sortData(int size,int num) {
    int* p = getArr(size);
    int start, end;
    start = clock();
    
    switch (num)
    {
    case bubble: bubbleSort(p, size); break;
    case select: selectSort(p, size); break;
    case insert: insertSortOne(p, size); break;
    case shell: shellSort(p, size); break;
    case bucket: bucketSort(p, size); break;
    case quick: quickSortEntrance(p, size); break;
    case merge: mergeSortEntrance(p, size); break;
        default:break;
    }

    #pragma region last defined
    //**带Entranceare all recursive  Subsequent data are multiplied in turn10
    //1.冒泡排序bubbleSort  811ms
    //bubbleSort(p, size);
    //2.选择排序selectSort  370ms
    //selectSort(p, size);
    //3.(*难)插入排序一inserSort  185ms
    //insertSortOne(p, size);
    //4.希尔排序shellSort 586ms
    //shellSort(p, size);
    //5.快速排序quickSort 3ms 秒杀  debug
    //quickSortEntrance(p, size);
    //6.归并排序   4ms  Compare later
    //mergeSortEntrance(p, size);
    //7.桶/基数排序 6ms 63ms
    //bucketSort(p, size);
#pragma endregion

    end = clock();
    printf("%s运行了:%dms\n",enumCh[num],(end-start));

    FILE* fpSort = fopen("D:/大文件排序.txt", "w");
    for (size_t i = 0; i < size; i++)  fprintf(fpSort, "%d\n", p[i]);
    free(p);
    fclose(fpSort);
}

void main()
{
    for (size_t k =2; k < 10; k++)
    {
        int size = 5*pow(10, k);
        generateMegaData(size);
        printf("-----------5*10^%d个数据--------------\n", k);
        //遍历计算算法需要时间
        //The lower-level implementation does not compare other algorithms after a timeout
        size_t i = 1;
        if (k > 6) {
            i = 6;
        }else if (k > 5) {
            i = 5;
        }else if (k >4 ) {
            i = 5;
        }else if (k > 3) {
            i = 4;
        }
        for (i; i < 8; i++) 
        {   
            sortData(size, i);
        }
        printf("\n");
    }

    return 0;
}

附上结果

i5 8350u运行结果

Then it got stuck

学校i7 12700结果   Without exception also stuck at greater than5*10^8这里  Because it is for entertainment reasons, I won't go into it(明明有64G才用了9g)

 

 

copyright notice
author[Rondox],Please bring the original link to reprint, thank you.
https://en.bfun.fun/2022/298/202210250326124669.html

Random recommended