精华内容
下载资源
问答
  • 随机数归并排序c语言
    2021-05-25 08:00:11

    1.归并排序

    #include

    #include

    #include

    #define N 50000

    void merge(int [],int,int,int);//归并排序数组合并函数声明

    void mergesort(int [],int,int);//归并排序数组排序函数声明

    //主函数

    int main()

    {

    int i,a1[N];

    double t1,t2,t3,t4;

    for(i=0;i

    {

    a1[i]=rand()%N;

    }

    //归并排序N个随机数字所用的时间

    t2=clock();

    mergesort(a1,0,N-1);

    t2=clock()-t2;

    /*排好序的结果*/

    for(i=0;i

    {

    printf("%4d\n",a1[i]);

    }

    printf("\n归并排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);

    getch();

    return 1;

    }

    //归并排序

    //归并排序合并数组函数的具体实现

    void merge(int a[],int low,int middle,int high)

    {

    int h,i,j,k;

    int b[N];

    h=low;

    i=low;

    j=middle+1;

    while(h<=middle&&j<=high)

    {

    if(a[h]<=a[j])

    {

    b[i]=a[h];

    h++;

    }

    else

    {

    b[i]=a[j];

    j++;

    }

    i++;

    }

    if(h>middle)

    for(k=j;k<=high;k++)

    {

    b[i]=a[k];

    i++;

    }

    else

    {

    for(k=h;k<=middle;k++)

    {

    b[i]=a[k];

    i++;

    }

    }

    for(k=low;k<=high;k++)

    {

    a[k]=b[k];

    }

    }

    //归并排序函数的具体实现

    void mergesort(int a[],int low,int high)

    {

    int middle;

    if(low

    {

    middle=(low+high)/2;

    mergesort(a,low,middle);

    mergesort(a,middle+1,high);

    merge(a,low,middle,high);

    }

    }

    2.快速排序

    #include"stdio.h"

    #include

    #include

    #include

    #define N 50000

    void quickSort(int a[],int left,int right)

    {

    int i,j,temp;

    i=left;

    j=right;

    temp=a[left];

    if(left>right)

    return;

    while(i!=j)/*找到最终位置*/

    {

    while(a[j]>=temp && j>i)

    j--;

    if(j>i)

    a[i++]=a[j];

    while(a[i]<=temp && j>i)

    i++;

    if(j>i)

    a[j--]=a[i];

    }

    a[i]=temp;

    quickSort(a,left,i-1);/*递归左边*/

    quickSort(a,i+1,right);/*递归右边*/

    }

    int main()

    {

    double t2=clock();

    int i,a[N];

    for(i=0;i

    {

    a[i]=rand()%N;

    }

    quickSort(a,0,N-1);

    t2=clock()-t2;

    /*排好序的结果*/

    for(i=0;i

    {

    printf("%4d\n",a[i]);

    }

    printf("\n快速排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);

    getch();

    return 1;

    }

    3.堆排序

    #include

    #include

    #include

    #define LEFT(i) ((i)<<1)

    #define RIGHT(i) (((i)<<1) + 1)

    #define N 50000

    void max_heapify(int a[], int i, int heapsize);

    void heap_sort(int a[], int heapsize);

    void build_max_heap(int a[], int heapsize);

    void exchange(int *x, int *y);

    //交换两个数的值

    void exchange(int *x, int *y) {

    int temp;

    temp = *x;

    *x = *y;

    *y = temp;

    }

    //保持最大堆性质

    void max_heapify(int a[], int i, int heapsize) {

    int left, right, largerest;

    left = LEFT(i);

    right = RIGHT(i);

    if (left <= heapsize && a[left]>a[i])

    {

    largerest = left;

    }else{

    largerest = i;

    }

    if (right <= heapsize && a[right]>a[largerest])

    {

    largerest = right;

    }

    if(largerest != i) {

    exchange(&a[i], &a[largerest]);

    max_heapify(a, largerest, heapsize);

    }

    }

    //建造最大堆

    void build_max_heap(int a[], int heapsize) {

    int i;

    for (i=(int)ceil(heapsize/2); i >=1 ; i--)

    {

    max_heapify(a, i, heapsize);

    }

    }

    //堆排序

    void heap_sort(int a[], int heapsize) {

    //build heap

    build_max_heap(a, heapsize);

    while(heapsize>1)

    {

    //exchange max

    exchange(&a[1], &a[heapsize]);

    heapsize--;

    max_heapify(a, 1, heapsize);

    }

    }

    int main() {

    double t2=clock();

    int i,a[N];

    for(i=0;i

    {

    a[i]=rand()%N;

    }

    heap_sort(a, N-1);

    t2=clock()-t2;

    //打印排序后的数组

    for (i=1; i

    {

    printf("%d\n",a[i]);

    }

    printf("\n堆排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);

    getch();

    return 1;

    }

    4.冒泡排序

    #include

    #include

    #include

    #define N 50000

    int main()

    {

    double t2=clock();

    int i,j,a[N];

    int flag=1;

    int temp;

    for(i=0;i

    {

    a[i]=rand()%N;

    }

    for(i=0;i

    {

    for(j=0;j

    {

    if(a[j+1]

    {

    temp=a[j+1];

    a[j+1]=a[j];

    a[j]=temp;

    flag=0;

    }

    }

    if(flag==1)

    {

    break;

    }

    }

    t2=clock()-t2;

    //打印排序后的数组

    for (i=0; i

    {

    printf("%d\n",a[i]);

    }

    printf("\n冒泡排序%d个随机数字所用时间为:%f毫秒\n",N,(double)t2);

    getch();

    return 1;

    }

    时间性能最好的是快速排序,最差的是冒泡排序。。。。。。

    更多相关内容
  • 生成随机数排序.cbp

    2020-12-07 23:07:37
    自动生成随机数,然后分别用冒泡、选择、快速排序来输出排序结果。代码中还可以输出每一步的排序结果供分析
  • C语言归并排序算法

    千次阅读 2022-02-05 22:17:31
    如果说快速排序是让一个数组分成很多小集体进行排序,那么归并排序就是让很多有序的小集体合成一个有序数组。 思路: 如果是升序,对于每一个数字来说其本身是有序的,最初让两个只有一个元素的数组arr1,arr2的...

    今天我要和大家分享的是一个排序算法——归并算法。

    如果说快速排序是让一个数组分成很多小集体进行排序,那么归并排序就是让很多有序的小集体合成一个有序数组。

    思路:

    如果是升序,对于每一个数字来说其本身是有序的,最初让两个只有一个元素的数组arr1,arr2的元素进行比较,较小者放入第三个数组arr3的第一个元素的位置,然后另一个数组的元素放在arr3。然后让两个有一个以上的合并后数组的首元素进行比较较小者让在第三个数组首元素的位置,再向下进行比较,直到两个数组的元素全部进入第三个数组,然后一直重复,直到合并成最终的大数组。

    要想利用小集合合成大数组前提是有小集合,所以先让数组分成许多小数组。

    void merge_sort_divide(int* arr, int* temp, int start, int end)
    {
    	if (start < end)
    	{
    		int mid = (start + end) / 2;
    		merge_sort_divide(arr, temp, start, mid);
    		merge_sort_divide(arr, temp, mid + 1, end);
    		merge(arr, temp, start, mid + 1, end);
    	}
    }

    最后合并

    void merge(int* arr, int* temp, int arr1start, int arr2start, int arr2end)
    {
    	int p1 = arr1start, p2 = arr2start, p3 = p1, arr1end = p2 - 1;
    
    	//主循环
    	while (p1 <= arr1end && p2 <= arr2end)
    	{
    		if (arr[p1] < arr[p2]) temp[p3++] = arr[p1++];
    		else temp[p3++] = arr[p2++];
    	}
    
    	//一个数组排序完成后,剩下的移动过去即可
    	while (p1 <= arr1end) temp[p3++] = arr[p1++];
    	while (p2 <= arr2end) temp[p3++] = arr[p2++];
    
    	//将所有数据移回原来数组
    	for (int i = arr1start; i <= arr2end; i++) arr[i] = temp[i];
    }

    全部代码

    test.c:

    #include"sort.h"
    
    int main(void)
    {
    	int arr[LEN] = { 0 };
    	int i = 0;
    	srand((unsigned int)time(NULL));
        
        //生成随机数进行检验  也可以自己输入数据
    	for (i = 0; i < LEN; i++)
    	{
    		arr[i] = rand() % 100;
    	}
    	printf("数组排序前:\n");
    	print_arrray(arr, LEN);
    
    	merge_sort(arr, LEN);
    
    	printf("数组排序后:\n");
    	print_arrray(arr, LEN);
    
    	return 0;
    }

    sort.h:

    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<string.h>
    
    #define LEN 10//随机数的个数
    
    void print_arrray(int* arr, int len);
    
    
    void merge_sort(int* arr, int len);
    
    void merge_sort_divide(int* arr, int* temp, int start, int end);
    
    void merge(int* arr, int* temp, int arr1star, int arr2start, int arr2end);

    sort_function.c:

    #include"sort.h"
    
    void print_arrray(int* arr, int len)
    {
    	int i = 0;
    	for (i = 0; i < len; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    }
    
    
    //将两个有序数组合并为一个
    void merge(int* arr, int* temp, int arr1start, int arr2start, int arr2end)
    {
    	int p1 = arr1start, p2 = arr2start, p3 = p1, arr1end = p2 - 1;
    
    	//主循环
    	while (p1 <= arr1end && p2 <= arr2end)
    	{
    		if (arr[p1] < arr[p2]) temp[p3++] = arr[p1++];
    		else temp[p3++] = arr[p2++];
    	}
    
    	//一个数组排序完成后,剩下的移动过去即可
    	while (p1 <= arr1end) temp[p3++] = arr[p1++];
    	while (p2 <= arr2end) temp[p3++] = arr[p2++];
    
    	//将所有数据移回原来数组
    	for (int i = arr1start; i <= arr2end; i++) arr[i] = temp[i];
    }
    
    void merge_sort_divide(int* arr, int* temp, int start, int end)
    {
    	if (start < end)
    	{
    		int mid = (start + end) / 2;
    		merge_sort_divide(arr, temp, start, mid);
    		merge_sort_divide(arr, temp, mid + 1, end);
    		merge(arr, temp, start, mid + 1, end);
    	}//分成许多小的数组最后执行合并
    }
    
    
    void merge_sort(int* arr, int len)
    {
    	int* temp = malloc(sizeof(int) * len);
    	merge_sort_divide(arr, temp, 0, len - 1);
    	free(temp);
    }

    运行结果:

     

    牛客网 初学者编程118题小乐乐与序列_牛客题霸_牛客网

     我的初代思路:极其听话地先去重再排序。

    初代代码:

    #include<stdio.h>
     
    int main(void)
    {
        int arr[60] = { 0 };
        int n = 0;
        int i = 0;
        int j = 0;
        int k = 0;
        int count = 0;
        int flag = 0;
        scanf("%d", &n);
        for (i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
        }
        for (i = 0; i < n - count; i++)
        {
            for (k = i + 1; k < n - count; k++)
            {
                flag = 0;
                for (j = k; j < n - count; j++)
                {
                    if(arr[j] == arr[i])
                    {
                        flag = 1;
                        count++;
                        k = j - 1;
                        break;
                    }
                }
                for (j; j < n - count; j++)
                {
                    arr[j] = arr[j + 1];
                }
            }
        }
         
        //for (i = 0; i < n - count; i++)
        //{
            //printf("%d ", arr[i]);
        //}
        int p = 0;
        int min = 0;
        for (i = 0; i < n - count; i++)
        {
            p = i;
            min = arr[i];
            for (j = i + 1; j < n - count; j++)
            {
                if(arr[j] < min)
                {
                    p = j;
                    min = arr[j];
                }
            }
            if(p != i)
            {
                int t = arr[i];
                arr[i] = arr[p];
                arr[p] = t;
            }
        }
         
        for (i = 0; i < n - count; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return 0;
    }
    

     数据太少了

    然后改进:

    改成了5000个数据

    然后出现了这个

     

    这是n的值

    我就只能在堆上要这么多数据,并且学习了一个算法——快速排序,结果超时了,超过一秒程序直接暂停。

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
     
    void W(int* p, int left, int right)//先去重
    {
        int flag = 0;
        flag = *(p + left);
        int t = right;
        //int ret = right - left;
        while (left < right)
        {
            if (*(p + right) < flag)
            {
                *(p + left) = *(p + right);
                left++;
                while (left < right)
                {
                    if (*(p + left) > flag)
                    {
                        *(p + right) = *(p + left);
                        right--;
                        break;
                    }
                    else
                    {
                        left++;
                    }
                }
            }
            else
            {
                right--;
            }
        }
         
        *(p + left) = flag;
     
        if (left > 1)
        {
            W(p, 0, left - 1);
        }
        if (right < t - 1)
        {
            W(p, right + 1, t);
        }
    }
     
    int main(void)
    {
        //int arr[10000] = { 0 };
        //int* p = (int*)calloc(80000, sizeof(int));
        int* p = (int*)malloc(80000*sizeof(int));
        if (p != NULL)
        {
            int n = 0;
            int i = 0;
            int j = 0;
            int k = 0;
            int count = 0;
            int flag = 0;
            scanf("%d", &n);
            for (i = 0; i < n; i++)
            {
                scanf("%d", p + i);
            }
            for (i = 0; i < n - count - 1; i++)
            {
                for (k = i + 1; k < n - count; k++)
                {
                    flag = 0;
                    for (j = k; j < n - count; j++)
                    {
                        if (*(p + j) == *(p + i))
                        {
                            flag = 1;
                            count++;
                            k = j - 1;
                            break;
                        }
                    }
                    for (j; j < n - count; j++)
                    {
                        *(p + j) = *(p + j + 1);
                    }
                }
            }
     
            //for (i = 0; i < n - count; i++)
            //{
                //printf("%d ", arr[i]);
            //}
             
            W(p, 0, n - 1);
             
            for (i = 0; i < n - count; i++)
            {
                printf("%d ", *(p + i));
            }
            printf("\n");
        }
        free(p);
        p = NULL;
        return 0;
    }
    

    改进顺序,先排序后去重,在去重的同时打印:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
     
    void W(int* p, int left, int right)
    {
        int flag = 0;
        flag = *(p + left);
        int t = right;
        while (left < right)
        {
            if (*(p + right) < flag)
            {
                *(p + left) = *(p + right);
                left++;
                while (left < right)
                {
                    if (*(p + left) > flag)
                    {
                        *(p + right) = *(p + left);
                        right--;
                        break;
                    }
                    else
                    {
                        left++;
                    }
                }
            }
            else
            {
                right--;
            }
        }
         
        *(p + left) = flag;
     
        if (left > 1)
        {
            W(p, 0, left - 1);
        }
        if (right < t - 1)
        {
            W(p, right + 1, t);
        }
    }
     
    int main(void)
    {
        int* p = (int*)malloc(72641*sizeof(int));
        //int* q = (int*)malloc(70000*sizeof(int));
        if (p != NULL)
        {
            int n = 0;
            int i = 0;
            int k = 0;
            scanf("%d", &n);
            for (i = 0; i < n; i++)
            {
                scanf("%d", p + i);
            }
            W(p, 0, n - 1);
             
            for (i = 0; i < n - 1; i++)
            {
                if(*(p + i) != *(p + i + 1))
                {
                    printf("%d ", *(p + i));
                }
            }
            printf("%d ", *(p + n - 1));
        }
        free(p);
        p = NULL;
        return 0;
    }

     还是超时

    然后用归并排序解决问题:

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
     
    //将两个有序数组合并为一个
    void merge(int* arr, int* temp, int arr1start, int arr2start, int arr2end)
    {
        int p1 = arr1start, p2 = arr2start, p3 = p1, arr1end = p2 - 1;
     
        //主循环
        while (p1 <= arr1end && p2 <= arr2end)
        {
            if (arr[p1] < arr[p2]) temp[p3++] = arr[p1++];
            else temp[p3++] = arr[p2++];
        }
     
        //一个数组排序完成后,剩下的移动过去即可
        while (p1 <= arr1end) temp[p3++] = arr[p1++];
        while (p2 <= arr2end) temp[p3++] = arr[p2++];
     
        //将所有数据移回原来数组
        for (int i = arr1start; i <= arr2end; i++) arr[i] = temp[i];
    }
     
    void merge_sort_divide(int* arr, int* temp, int start, int end)
    {
        if (start < end)
        {
            int mid = (start + end) / 2;
            merge_sort_divide(arr, temp, start, mid);
            merge_sort_divide(arr, temp, mid + 1, end);
            merge(arr, temp, start, mid + 1, end);
        }
    }
     
     
    void merge_sort(int* arr, int len)
    {
        int* temp = malloc(sizeof(int) * len);
        merge_sort_divide(arr, temp, 0, len - 1);
        free(temp);
    }
    int main(void)
    {
        int* p = (int*)malloc(100000*sizeof(int));
        if (p != NULL)
        {
            int n = 0;
            int i = 0;
            int a = 0;
            scanf("%d", &n);
            for (i = 0; i < n; i++)
            {
                scanf("%d", p + i);
            }
            merge_sort(p, n);
             
            for (i = 0; i < n - 1; i++)
            {
                if(*(p + i) != *(p + i + 1))
                {
                    printf("%d ", *(p + i));
                }
            }
            printf("%d ", *(p + n - 1));
        }
        free(p);
        p = NULL;
        return 0;
    }
    

    最后说明一下为什么我从堆上要了10万个数,因为它真的用了

     经历了22次试错,因为自测都能通过,真正测试的10组中最后4组都是大数

     难题就要慢慢解决,写出来真的很有成就感,虽然那些大佬一眼就看出来了,但是我一个小鸟做出来感觉已经不错了,我会一直努力的。

     

     

     好吧,这几天没有太努力,让这张图片激励一下我吧!

    展开全文
  • 归并排序(非递归)——C语言实现

    千次阅读 多人点赞 2022-04-14 16:48:56
    一、递归实现归并排序的问题 递归实现快速排序一样,递归实现归并排序一样需要在栈上建立栈帧,消耗栈空间,当提柜深度过深时,就会出现栈溢出的现象。为了解决这个缺陷,本文将带来非递归实现归并排序的算法。 二、...


    在这里插入图片描述


    在这里插入图片描述

    🚆一、递归实现归并排序的问题

      递归实现快速排序一样,递归实现归并排序一样需要在栈上建立栈帧消耗栈空间,当递归深度过深时,就会出现栈溢出的现象。为了解决这个缺陷,本文将带来非递归实现归并排序的算法。

    ✈️二、利用循环实现归并排序

    🍟2.1 思想

      我们利用一个新的数组,新数组和原数组等长,先1个数为一组,相邻两组进行归并,并将归并完的数拷贝回原数组,这样归并完一次后数组就变成两两有序;然后2个数为一组,相邻两组进行归并,这样归并完后就四四有序了;然后4个数为一组,相邻两组进行归并,这样归并完后就八八有序了;依次类推,8个数为一组,相邻两组进行归并 ...16个数为1组,32个数为1组...

    🥪2.2 图解

    在这里插入图片描述

    🚢三、代码实现

    void MergrSortNonR(int* arr, int n)
    {
    	//创建临时数组
    	int* tmp = (int*)malloc(sizeof(int)*n);
    
    	int gap = 1;//代表gap个数和gap个数归并,初始为1
    	while (gap < n)
    	{
    		for (int i = 0; i < n; i += 2 * gap)
    		{
    			//每次需要归并的区间为 [i,i+gap-1]和[i+gap,i+2*gap-1]
    			//开始进行归并
    			int begin1 = i;
    			int end1 = i + gap - 1;
    			int begin2 = i + gap;
    			int end2 = i + 2 * gap - 1;
    			int index = i;    //归并时放入临时数组的位置,从两个需要归并的区间的最左边开始
    
    			while (begin1 <= end1 && begin2 <= end2)
    			{
    				//谁小谁下放至临时数组
    				if (arr[begin1] < arr[begin2])
    				{
    					tmp[index++] = arr[begin1++];
    				}
    				else
    				{
    					tmp[index++] = arr[begin2++];
    				}
    			}
    
    			//循环结束把还没放下来的数放下来,两个循环只会进去一个
    			while (begin1 <= end1)
    			{
    				tmp[index++] = arr[begin1++];
    			}
    			while (begin2 <= end2)
    			{
    				tmp[index++] = arr[begin2++];
    			}
    		}
    		//一轮归并完再拷贝
    		for (int j = 0; j <n ; j++)
    		{
    			arr[j] = tmp[j];
    		}
    		gap *= 2;
    	}
    
    	//销毁临时数组
    	free(tmp);
    }
    

    代码写完了,各位觉得这个代码有问题吗?
    哈哈,当然有,问题很大,这个代码只能对2^n个数进行排序,多一个都不行

    🛩️四、代码剖析

      在排序的过程中会出现三种情况,分别为右区间不存在右区间存在但是算多了左区间算多了。针对这三种情况我们怎么解决呢?

    🧀4.1 右区间不存在

    在这里插入图片描述我们看下用上面的代码排一下这个数组:
    在这里插入图片描述

    崩了???

    对于上面的情况,第一轮两两归并时,最后的3就没有右区间和他归并,怎么办?
    答案就是:直接break掉
    有的人可能会担心,直接break掉会不会导致还有数没有归并完?
    答案就是:不会
    因为不存在右区间的情况一定出现在本轮归并的末尾,所以不存在会漏掉其他数。 怎么处理?
    在归并前加上一个判断即可

    	if (end1 >= n-1)
    	{
    		break;
    	}
    

    🍿4.2 右区间存在但是算多了

    在这里插入图片描述
      对于上面这种情况,当进行第二轮归并时,最后的两组为[3 10]和[8 ?],其实这个时候右区间只有8一个数,但是代码在计算end2的时候其实已经计算到8的后面去了,所以会出现什么情况?
    在这里插入图片描述
    在这里插入图片描述

    对于这种情况我们需要对end2进行修正。
    怎么修正?
    将end2修正为最后一个数的下标n-1

    	if (end2 >= n)
    	{
    		end2 = n - 1;
    	}
    

    🌭4.3 右区间不存在的同时左区间算多了

    在这里插入图片描述
      还是这个例子,当进行第三轮归并时,[ 1 4 7 9 ]和[ 0 2 8 10 ]进行归并,[ 3 8 10]和[???]进行归并,这里不仅缺省右区间,左区间还少一个数,但是代码在计算end1时,依旧会算到8的后面,如果我们在一轮归并完后再拷贝,就会导致我们拷贝回去的代码进一个随机数。如下图所示
    在这里插入图片描述
    所以我们不能等到一轮归并完之后一起将数组拷贝回原数组,应该一组归并完后立刻将数据拷贝回原数组

    🚀五、修改后完整代码

    void MergrSortNonR(int* arr, int n)
    {
    	//创建临时数组
    	int* tmp = (int*)malloc(sizeof(int)*n);
    
    	int gap = 1;//代表gap个数和gap个数归并,初始为1
    	while (gap < n)
    	{
    		for (int i = 0; i < n; i += 2 * gap)
    		{
    			//每次需要归并的区间为 [i,i+gap-1]和[i+gap,i+2*gap-1]
    			//开始进行归并
    			int begin1 = i;
    			int end1 = i + gap - 1;
    			int begin2 = i + gap;
    			int end2 = i + 2 * gap - 1;
    			int index = i;    //归并时放入临时数组的位置,从两个需要归并的区间的最左边开始
    
    			//归并过程中,右区间不存在
    			//这里直接break掉,因为必定已经归到最后了
    			if (end1 >= n-1)
    			{
    				break;
    			}
    
    			//如果右区间存在,但是算多了,需要修正
    			if (end2 >= n)
    			{
    				end2 = n - 1;
    			}
    
    			while (begin1 <= end1 && begin2 <= end2)
    			{
    				//谁小谁下放至临时数组
    				if (arr[begin1] < arr[begin2])
    				{
    					tmp[index++] = arr[begin1++];
    				}
    				else
    				{
    					tmp[index++] = arr[begin2++];
    				}
    			}
    
    			//循环结束把还没放下来的数放下来,两个循环只会进去一个
    			while (begin1 <= end1)
    			{
    				tmp[index++] = arr[begin1++];
    			}
    			while (begin2 <= end2)
    			{
    				tmp[index++] = arr[begin2++];
    			}
    
    			//一次归并完后就把归并完的数据赶紧拷贝回原数组
    			//不要留着全部归并完再拷贝,文章里会讲原因
    			for (int j = i; j <= end2; j++)
    			{
    				arr[j] = tmp[j];
    			}
    		}
    		//不要一起拷贝
    		//for (int j = 0; j <n ; j++)
    		//{
    		//	arr[j] = tmp[j];
    		//}
    		gap *= 2;
    	}
    	
    
    	//销毁临时数组
    	free(tmp);
    }
    

            👆回到顶部👆

    在这里插入图片描述

    展开全文
  • 主要介绍了 C语言开发之归并排序详解及实例的相关资料,需要的朋友可以参考下
  • 直接插入、折半插入、冒泡、快速、简单选择等排序方法 用c语言实现 代码运行正常 不会有任何的问题
  • 一、C语言实现归并排序 1、函数调用说明 目录 一、C语言实现归并排序 1、函数调用说明


    前言

    本文主要记录了C语言归并排序串、并行的两种实现方式,是本人历经为时俩天半的心得体会(手动滑稽),希望可以给未来完成程序实践课的学弟学妹提供一些帮助。


    一、什么是归并排序?

            先谈谈本人对于递归排序的认识吧,本人所认为的递归排序就是将一个无序的数组无限平分,直到最后一次平分后的数组内只剩一个元素,此时我们就可以认为这时的数组是有序的。把数组无限分割直至数组内剩一个元素的步骤就是递归中的递,这时我们就需要比较数组前后两部元素的大小进行排序合并,这个步骤是合并数组,然后再通过递归的函数将排好序的数组归还到原数组,进而输出,实现归并排序。

    二、涉及到的函数及功能

            由于这次程序实践要求程序实现的功能较多,所以先来介绍一下其中主要的函数和功能

    1、计算程序运行时间

            这里使用的是头文件time.h中的time函数,代码示例如下:

        time_t begin_time,end_time;
        begin_time=time(NULL);
        ##################
    
        执行程序主体
    
        ##################
        end_time=time(NULL);
        printf("%lfs", difftime(end_time,begin_time));

            

    2、生成随机数

            

        srand((unsigned )time(NULL));//使用srand()函数使产生的随机数与时间关联,避免出现伪随机数的情况
        for(int i=0;i<n;i++)
        {
            arr[i]=1+rand()%(10000);//使用rand()生成随机数
        }
        for (int i = 0; i < n; i++)
        {
            printf("%d\t",arr[i]);//两个for循环实现循环生成数组并输出
        }

    3、定义动态数组

    由于实践要求,要定义长度为10^6的数组,int是定义不了这么长的数组的,这里我们就用到了malloc()函数。

    int *tmp = (int *) malloc(sizeof(int) * n);//定义一个长度为n的整型数组
    
    free(tmp);//释放malloc()函数使用过的内存空间

     4、有关Linux多线程的函数

    #include<pthread.h>//使用多线程需要引入pthread.h头文件
    
        pthread_t thread;//先进行线程声明,声明一个名为thread的线程
    
        pthread_create(&thread,NULL,Merge_Sort,arg);//创建线程
    
        pthread_join(thread,NULL);//线程等待,等待线程运行
        
        pthread_exit(0);//线程结束,结束线程
    

    关于多线程本人了解并不深入,可以参考其他博主关于多线程的详细讲解。 

    三、串行与并行(多线程)归并排序的代码实现

    1、实现串行归并排序

    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>//malloc()函数的头文件,也可以单独使用malloc.h头文件
    
    void Merge_Sort(int arr[],int start,int end);//声明递归函数
    void Merge(int arr[],int start,int mid,int end);//声明合并函数
    void Input_print();//声明一个分担主函数功能的函数,避免主函数过于冗长
    
    int n;
    
    int main()
    {
        time_t begin_time,end_time;
        begin_time=time(NULL);
        Input_print();
        end_time=time(NULL);
        printf("%lfs", difftime(end_time,begin_time));//输出程序运行时间,并输出单位
        return 0;
    }
    
    void Input_print()
    {
        int* arr=(int*) malloc(20000000*sizeof(int ));
        printf("Please enter the length of the array:\n");
        scanf("%d",&n);
        printf("Randomly generate random %d numbers in the array:\n",n);
        srand((unsigned )time(NULL));
        for(int i=0;i<n;i++)
        {
            arr[i]=1+rand()%(1000000);
        }
        for (int i = 0; i < n; i++)
        {
            printf("%d\t",arr[i]);
        }
        printf("\n");
        
        Merge_Sort(arr,0,n-1);
        for(int i=0;i<n;i++)//循环输出排序后数组中的元素
            printf("%4d\n",arr[i]);
        printf("\n");
        free(arr);
    
    }
    
    void Merge_Sort(int arr[],int start,int end)
    {
        if(end-start!=0)//设定执行条件避免无限循环
        {
            int mid=(start+end)/2;
            printf("start:%d,end:%d\n",start,end);//这里是一项实践任务,完成对平分后数组角标的输出
            Merge_Sort(arr,start,mid);
            Merge_Sort(arr,mid+1,end);
            Merge(arr,start,mid,end);
        }
        else
            printf("start:%d,end:%d\n",start,end);//这里是一项实践任务,完成对平分后数组角标的输出
    }
    
    
    void Merge(int arr[],int start,int mid,int end) {
        int *tmp = (int *) malloc(sizeof(int) * n);//定义一个临时数组
        int i, j, k;
        i = start;
        j = mid + 1;
        k = start;
        while (i <= mid && j <= end)//while循环进行数组合并,把同一级的数组中的元素轮流进行比较,哪个小,哪个就放入数组tmp[]
        {
            if (arr[i] < arr[j])
            {
                tmp[k] = arr[i];
                i++;
                k++;
            } else {
                tmp[k] = arr[j];
                k++;
                j++;
            }
        }
        while (i <= mid) {//把剩余的数挨个放到数组中去
            tmp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= end) {//把剩余的数挨个放到数组中去
            tmp[k] = arr[j];
            k++;
            j++;
        }
        for (int m = start; m <= end; m++)//for循环将数组tmp赋值到arr中
            arr[m] = tmp[m];
        free(tmp);
    }

    2、实现并行(多线程)归并排序

     值得注意的是这里用到的多线程归并排序只能在Linux系统下运行

    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    #include<pthread.h>
    
    
    void Merge(int arr[],int start,int mid,int end);
    void Input_print();
    void* Merge_Sort(void* arg);//注意线程函数的命名格式
    void Merge_sort(int start,int end);
    
    int n;
    int *x;//定义一个指针
    int main()
    {
        time_t begin_time,end_time;
        begin_time=time(NULL);
        Input_print();
        end_time=time(NULL);
        printf("%lfs", difftime(end_time,begin_time));
        return 0;
    }
    
    void Input_print()
    {
        int arr[100000];
        printf("Please enter the length of the array:\n");
        scanf("%d",&n);
        printf("Randomly generate random %d numbers in the array:\n",n);
        srand((unsigned )time(NULL));
        for(int i=0;i<n;i++)
        {
            arr[i]=1+rand()%(10000);
        }
        for (int i = 0; i < n; i++)
        {
            printf("%d\t",arr[i]);
        }
        printf("\n");
        x = arr;//指针指向arr
        int arg[2];
        arg[0] = 0;
        arg[1] = n;
    
    
        pthread_t thread;//声明一个主线程
    
        pthread_create(&thread,NULL,Merge_Sort,arg);//创建线程
    
        pthread_join(thread,NULL);//线程等待
        Merge_sort(0,n-1);
        printf("The sorted arry is:\n" );
        for(int i=1;i<=n;i++)
            printf("%4d\n",arr[i]);
        pthread_exit(0);//线程结束
    
    }
    
    /*void Merge_sort(int start,int end)
    {
        if(end-start!=0)
        {
            int mid=(start+end)/2;
            printf("start:%d,end:%d\n",start,end);
            Merge_sort(start,mid);
            Merge_sort(mid+1,end);
        }
        else
            printf("start:%d,end:%d\n",start,end);
    }*/
    //本块代码是专门实现输出平分时数组前后元素角标的,不需要请省略
    
    void* Merge_Sort(void* arg)
    {
        int *argu = (int*)arg;//强制转化arg类型为整型,并把值赋给argue
        int start = argu[0];
        int end = argu[1];
    
        if(start<end)
        {
            int *arr = x;//定义一个指针,把x赋值给arr
            pthread_t thread1;
            pthread_t thread2;//声明两个线程
    
            int arg1[2];
            int arg2[2];
    
            int mid = (start + end) / 2;
            arg1[0] = start;
            arg1[1] = mid;
            arg2[0] = mid + 1;
            arg2[1] = end;
    
            pthread_create(&thread1,NULL,Merge_Sort,arg1);
            pthread_create(&thread2,NULL,Merge_Sort,arg2);//创建线程
    
            pthread_join(thread1,NULL);
            pthread_join(thread2,NULL);//线程等待
    
            Merge(arr,start,mid,end);
            pthread_exit(0);//线程结束
        }
    
        return NULL;
    }
    
    void Merge(int arr[],int start,int mid,int end)
    {
        int *tmp = (int *) malloc(sizeof(int) * n);
        int i, j, k;
        i = start;
        j = mid + 1;
        k = start;
        while (i <= mid && j <= end) {
            if (arr[i] < arr[j]) {
                tmp[k] = arr[i];
                i++;
                k++;
            } else {
                tmp[k] = arr[j];
                k++;
                j++;
            }
        }
        while (i <= mid) {
            tmp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= end) {
            tmp[k] = arr[j];
            k++;
            j++;
        }
        for (int m = start; m <= end; m++)
            arr[m] = tmp[m];
        free(tmp);
    }


     总结

    以上就是关于归并排序的内容,本文仅仅简单介绍了归并排序,本人对归并排序的理解也有很多的不足之处,若有什么不足欢迎大家留言指正。(完结撒花

     


    展开全文
  • // Mix two sorted tables in one and split the result into these two tables.int *Mix(int *tab1,int *tab2,int count1,int count2){int i,i1,i2;i = i1 = i2 = 0;int * temp = (int *)malloc(sizeof(int)*(count...
  • C语言(使用时间)生成随机数 简单易懂(int pseudo_rand())
  • 100个随机数排序

    千次阅读 多人点赞 2020-12-30 17:59:29
    printf("\n归并排序比较次数是:%d\n", count1); printf("归并排序结果:\n"); for (i = 1; i ; i++) { if (i % 10) printf("%5d", L.R[i]); else { printf("%5d", L.R[i]); printf("\n"); } } system("pause"); }
  • 1. 排序函数:插入排序、归并排序、快速排序(递归、不递归、枢轴存放)、计数排序、基数计数排序。 2. 应用题:颜色排序、在一个无序序列中找到第K大/小的数。 3. 测试程序:数据生成、普通测试、读文件测试、写...
  • C语言实现归并排序

    2021-05-26 04:09:10
    #include#include#include#include#define random(i) (rand()%i)#define N 12#define INFINITY 99999999//要排序的数存放在a数组汇总,p,q,r是数组下标void Merge(int *a,int p,int q,int r){int n1=q-p+1;...
  • /* 要生成和返回随机数的函数 */ void getRandom(int *target, const int length) { /* 设置种子 */ srand((unsigned) time(NULL)); for (int i = 0; i < length; ++i) { target[i] = rand()...
  • 1、 编写函数分别实现插入排序和归并排序算法 2、 编写主函数通过调用函数实现对待排数据的调用 3、 待排数据利用随机函数循环产生10万个以上的数据 4、 利用求系统时间的函数,分别求出2个排序函数调用前和...
  • 利用归并排序法对序列排序的示意图(递归法):一、算法分析:利用递归的分治方法:1、将原序列细分,直到成为单个元素;2、在将分割后的序列一层一层地按顺序合并,完成排序。细分通过不断深入递归完成,合并通过递归...
  • 随机快速排序(C语言) 分治法基本思想 ...乍看起来快速排序和归并排序非常相似,都是将问题变小,先排序子串,最后合并。不同的是快速排序在划分子问题的时候经过多一步处理,将划分的两组数据划分为一大
  • } } //归并排序 void merge(int * array, int start, int mid, int end) { int *tmp = (int *)malloc((end-start+1)*sizeof(int)); //汇总缓冲区 int i = start; //第一个有序区索引 int j = mid+1; //第二个...
  • 递归实现归并排序 #include<stdio.h> #include<time.h> #include<stdlib.h> #include<math.h> typedef int ElementType; const int N=1000000; void Swap(ElementType*,ElementType*); void...
  • 对于c语言初学者来说第一个接触的排序方法一般是冒泡排序法. 冒泡排序法是通过设置双层循环嵌套来比较相邻的两个元素,而同样是通过设置双层循环嵌套的选择排序法则是将数组分为两段,一段为已排序列,另一端为未排...
  • #include<stdio.h> #include <time.h> #include<stdlib.h> #define N 10000 double T, T1, T2, T3, T4, T5, T6;... //clock_t是clock()...void Bubblesort(int arr[], int size)//冒泡排序 { in...
  • C语言归并排序(递归实现)

    千次阅读 2019-09-27 17:08:39
    //用时间做种,每次产生随机数不一样 //随机生成数组 int k,list[ARRAY]; for(k=0;k;k++){ list[k]=rand()%RANGE+1; } // int list[]={5,2,1,6,9,8,3,4,7,}; // int list[]={6,2,7,3,9,1,}; int len=...
  • printf("归并排序merge()内存分配故障!"); exit(0); } for( count=0; count; count++){ L[count] = a[low+count]; } for( int count=0; count; count++){ R[count] = a[low+count+m]; } for(i=0,...
  • 几分钟学会归并排序和快速排序

    千次阅读 多人点赞 2020-12-20 12:20:01
    简单易懂的常用两种排序 学习笔记
  • 八大排序之归并排序

    2020-04-08 22:54:17
    // TODO 归并排序 public class MergeSort { public static void main(String[] args) { // int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; // 测试时间复杂度 O(n log n) int [] arr = new int[80000]; ...
  • C语言实现各排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序 1.引入所需头文件 #include <stdio.h> #include <malloc.h> #动态申请内存 #include <stdlib....
  • 归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。其中二路归并类似二叉树的后序遍历。归并排序的思考更多的是解决在磁盘中的外排序...
  • C语言实现多线程排序

    2019-10-05 09:54:00
    创建线程执行归并排序 */ pthread_t tid; pthread_create( & tid, NULL, merge_sort, arg); /* 进程同步 */ pthread_join(tid, NULL); /* 打印已排序数组 */ int j; for (j = 0 ; j ; j++ ...
  • 文章目录前因后果排序源码堆排代码快排代码希尔排序代码归并排序代码测试环境100w数据量下的效率测试快排>希尔>归并>堆排1000w数据下的测试快排>希尔>归并>堆排(差距拉大)1亿数据量的测试快排>...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 945
精华内容 378
热门标签
关键字:

随机数归并排序c语言