1. Toy模板网首页
  2. > Toy博客

【数据结构】快速排序，归并排序

10月前 作者：嘎嘎旺 分类：Toy博客 阅读(41) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】快速排序，归并排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

快速排序

1.hoare版本
【数据结构】快速排序，归并排序,数据结构,数据结构,算法
根据动图的演示，整理的思路如下，
1.定义left,right,key。key默认是左边第一个元素，像两个指针，左边找比key大的，右边找比k小的，找到的话，交换二者，往返这个过程，当left与right相遇时，交换key和此时相遇的值.

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
int PartSort1(int* a, int left, int right)
{
	int keyi =left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left<right && a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left],&a[right]);

	}
	swap(&a[keyi], &a[left]);
	return left;

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	PartSort1(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

【数据结构】快速排序，归并排序,数据结构,数据结构,算法
单趟下来，6出现在正确的位置。
1.为什么大循环是left<right?
当两个小人走到一块去的时候，我们应该交换key位置的值，和相遇时候的值了，而不是让他们两个岔开.
2.为什么在小循环中要加left<right?
假如说数组是10,10,10,10,10,10,10,10,10
在小循环中一直找小，找不到就会越界.
3.return的值有什么用？
return的值相当于分了界，然后就可以分别对子区间使用快排了.
【数据结构】快速排序，归并排序,数据结构,数据结构,算法

针对每个子区间，使用快排

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
int PartSort1(int* a, int left, int right)
{
	int keyi =left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left<right && a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left],&a[right]);

	}
	swap(&a[keyi], &a[left]);
	return left;

}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int mid=PartSort1(a,begin,end);
	QuickSort(a,begin, mid - 1);
	QuickSort(a,mid+1,end);

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

递归结束条件，如果有两个数据的话还能排一次，如果只有一个数据的话就不用排了
1.为什么要右边先走，左边再走，为啥相遇的值一定比key小或者等于key？
情况1：右边找小，找不到小，一直往左走，与key碰面，相遇的值为key;
情况2：右边找到了小，停在那里，左边找大，一直找不到大，相遇点就停在了比key小的那里
情况3：交换值之后，右边一直找不到小，一直走，相遇点就是左边刚交换完，还没有动的比key小的值.
情况4：交换值之后，右边继续移动，找到小停在那，左边找不到大，相遇点就是比key小的.

2.挖坑法
【数据结构】快速排序，归并排序,数据结构,数据结构,算法
1.创建临时变量key保存最左侧坑位的值，右边找小找到小之后，将找到的小值填到左边的坑位去，这里变成坑位.左边找大，找到大之后，将该值填入右侧的坑位，依次循环，相遇之后，将key放到相遇点

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}

int PartSort2(int* a, int left, int right)
{
	int key = a[left];
	int pole = left;
	while (left < right)
	{
		while (left < right && a[right] >=key)
		{
			right--;
		}
		a[pole] = a[right];
		pole = right;

		
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[pole] = a[left];
		pole = left;
		
	}
	a[left] = key;
	return left;

}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int mid=PartSort2(a,begin,end);
	QuickSort(a,begin, mid - 1);
	QuickSort(a,mid+1,end);

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

3.前后指针法

前后指针法

#include<stdio.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
int PartSort3(int* a, int left, int right)
{
	int keyi = left;
	int cur = left + 1;
	int prev = left;
	while (cur<=right)
	{
		if (a[cur] < a[keyi])
		{
			prev++;
			swap(&a[cur], &a[prev]);
		}




		cur++;
    }
	swap(&a[keyi], &a[prev]);
	return prev;

}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int mid=PartSort3(a,begin,end);
	QuickSort(a,begin, mid - 1);
	QuickSort(a,mid+1,end);

}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", arr[i]);


	}


}

4.快速排序非递归版
【数据结构】快速排序，归并排序,数据结构,数据结构,算法
采用非递归代替递归分割步骤，当区间只有一个值时，将不在入栈.

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void swap(int*p,int*q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;

}
typedef struct Stack//定义一个栈的结构体变量	
{
	int* a;
	int top; // 栈顶
	int capacity; // 容量
}Stack;
void StackInit(Stack* ps)
{
	assert(ps);//断言，防止为空指针
	ps->a = NULL;//所指向的地址为空
	ps->capacity = ps->top = 0;//容量和栈中元素个数均为0
}
void StackPush(Stack* ps, int data)
{
	assert(ps);
	if (ps->capacity == ps->top)//如果栈中的元素个数等于栈的容量时考虑扩容，
	{
		int newcapcity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果刚开始时都等于0，就先给4个空间大小，后面如果满的话，容量扩大1倍
		int* newnode = (int*)realloc(ps->a, sizeof(int) * newcapcity);//申请空间，将申请好的空间首地址传给newnode指针
		assert(newnode);//断言，防止malloc失败
		ps->a = newnode;//将newnode保存的申请空间的首地址传给ps->a,让ps->a指向创建好的空间
		ps->capacity = newcapcity;//容量大小更新为新容量大小



	}
	ps->a[ps->top] = data;//像存数组一样存数据
	ps->top++;//指向下一个
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	return ps->top == 0;//ps->top为栈中元素个数.==0栈中无元素，无元素要返回1， 无元素ps->t0p==0，这个表达式结果是1，返回1;





}
// 出栈
void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));//防止栈内无元素，继续出栈
	ps->top--;
}
// 获取栈顶元素
int StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];//ps->top为栈中元素个数，由于数组下标是从0开始，所以栈顶元素下标为ps->top-1;

}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
	assert(ps);
	return ps->top;

}
// 销毁栈
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);//free掉动态申请的内存
	ps->a = NULL;//防止野指针
	ps->capacity = ps->top = 0;//容量和栈中元素个数置为0



}
int PartSort1(int* a, int left, int right)
{
	int keyi =left;
	while (left < right)
	{
		while (left<right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left<right && a[left]<= a[keyi])
		{
			left++;
		}
		swap(&a[left],&a[right]);

	}
	swap(&a[keyi], &a[left]);
	return left;

}
void QuickSort(int* a, int begin, int end)
{
	Stack st;
	StackInit(&st);
	StackPush(&st,end);
	StackPush(&st,begin);
	while (!StackEmpty(&st))
	{
		
		int left = StackTop(&st);
			StackPop(&st);
		int right = StackTop(&st);
			StackPop(&st);

		int mid = PartSort1(a, left, right);

		if (mid + 1 < right)
		{
			StackPush(&st,right);
			StackPush(&st,mid+1);

		}
		if (left < mid-1)
		{
			StackPush(&st,mid-1);
			StackPush(&st,left);

		}








	}

StackDestroy(&st);
}

int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);


	}


}

归并排序

基本思想：
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
【数据结构】快速排序，归并排序,数据结构,数据结构,算法
【数据结构】快速排序，归并排序,数据结构,数据结构,算法

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include<string.h>
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
		return;
	int mid = (begin + end) / 2;

	_MergeSort(a, begin,mid, tmp);
	_MergeSort(a, mid+1, end, tmp);
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;
	int j = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[j++] = a[begin1++];
		}
		if (a[begin2] < a[begin1])
		{
			tmp[j++] = a[begin2++];
		}
}
	while (begin1 <= end1)
	{
		tmp[j++] = a[begin1++];

	}
	while (begin2 <= end2)
	{
		tmp[j++] = a[begin2++];

	}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));





	
}
//归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	_MergeSort(a, 0, n - 1, tmp);
	free(tmp);
	
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10,8 };
	MergeSort(arr, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ",arr[i]);


	}


}

【数据结构】快速排序，归并排序,数据结构,数据结构,算法
0-0,1-1return回0-1，
【数据结构】快速排序，归并排序,数据结构,数据结构,算法
2-2return回0-2
【数据结构】快速排序，归并排序,数据结构,数据结构,算法
归并排序非递归版

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap<n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				if (a[begin2] < a[begin1])
				{
					tmp[j++] = a[begin2++];
				}





			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];

			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];

			}













		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;

	}
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5 };
	MergeSortNonR(arr, 8);
	for (int i = 0; i < 8; i++)
	{
		printf("%d ",arr[i]);


	}


}

【数据结构】快速排序，归并排序,数据结构,数据结构,算法
gap=1，两个两个排序，然后整体拷贝回去.
gap=2,四个四个排序，然后整体拷贝回去.
gap=8 八个排序，然后整体拷贝回去.

int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10 };
	MergeSortNonR(arr, 9);
	for (int i = 0; i < 9; i++)
	{
		printf("%d ",arr[i]);


	}


}

我们换成9个数据，发现程序崩溃.

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap<n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			printf("gap=%d [%d,%d][%d,%d]\n",gap, begin1, end1, begin2, end2);
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				if (a[begin2] < a[begin1])
				{
					tmp[j++] = a[begin2++];
				}





			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];

			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];

			}













		}
		memcpy(a, tmp, sizeof(int) * n);
		gap *= 2;

	}
}

【数据结构】快速排序，归并排序,数据结构,数据结构,算法
修正边界

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap<n)
	{
		int j = 0;
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2 = i + gap;
			int end2 = i + 2 * gap - 1;
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				if (a[begin2] < a[begin1])
				{
					tmp[j++] = a[begin2++];
				}





			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];

			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];

			}

			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));











		}
		
		gap *= 2;

	}
}
int main()
{
	int arr[] = { 6,1,2,7,9,3,4,5,10 };
	MergeSortNonR(arr, 9);
	for (int i = 0; i < 9; i++)
	{
		printf("%d ",arr[i]);


	}


}

1.修改边界后往回拷贝的就不是n了，而是这个end2 - i + 1
2.如果是9个数据的时候，最后一个数据在gap=8中才开始排序
【数据结构】快速排序，归并排序,数据结构,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-808735.html

到了这里，关于【数据结构】快速排序，归并排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】快速排序，归并排序

    【数据结构】快速排序，归并排序

    1.hoare版本 根据动图的演示，整理的思路如下， 1.定义left,right,key。key默认是左边第一个元素，像两个指针，左边找比key大的，右边找比k小的，找到的话，交换二者，往返这个过程，当left与right相遇时，交换key和此时相遇的值. 单趟下来，6出现在正确的位置。 1.为什么大循环

    2024年01月20日
    浏览(41)
  • 【数据结构】非递归实现快速排序与归并排序

    【数据结构】非递归实现快速排序与归并排序

    递归是可以向非递归进行变化的： 比如很经典的 斐波那契数列 可以用 递归 实现也可以用 循环 实现 但是有些复杂的递归仅仅依靠循环是很难控制的， 所以我们需要借助数据结构中的 栈与队列 帮助我们用非递归模拟递归， 故有的时候我们说非递归不是递归却胜似递归 通过

    2024年01月21日
    浏览(51)
  • 【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序

    【数据结构】 七大排序详解(贰)——冒泡排序、快速排序、归并排序

    ==冒泡排序（Bubble Sort）==也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会

    2024年02月09日
    浏览(123)
  • 【数据结构与算法】归并排序详解：归并排序算法，归并排序非递归实现

    【数据结构与算法】归并排序详解：归并排序算法，归并排序非递归实现

    归并排序是一种经典的排序算法，它使用了分治法的思想。下面是归并排序的算法思想： 递归地将数组划分成较小的子数组，直到每个子数组的长度为1或者0。 将相邻的子数组合并，形成更大的已排序的数组，直到最终得到一个完全排序的数组。 归并排序的过程可以分为三

    2024年01月22日
    浏览(70)
  • 【数据结构】冒泡，快速，直接插入，归并，选择排序

    【数据结构】冒泡，快速，直接插入，归并，选择排序

    🎊专栏【数据结构】 🍔喜欢的诗句：更喜岷山千里雪 三军过后尽开颜。 🎆音乐分享【Dream It Possible】 大一同学小吉，欢迎并且感谢大家指出我的问题🥰 目录   🎁冒泡排序 🏳️‍🌈图解 🏳️‍🌈实现过程 🏳️‍🌈代码 🎁快速排序 🏳️‍🌈图解 🏳️‍🌈实现过

    2024年02月06日
    浏览(82)
  • 数据结构——排序算法——归并排序

    数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中，由于第二个列表已经有序，所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中，每次插入时，只需要从上次插入的位置开始，继续向后寻找插入位置即可。这样一来，我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(47)
  • 数据结构和算法笔记4：排序算法-归并排序

    数据结构和算法笔记4：排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下： 分解：分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决：使用归并排序递归地排序两个子序列。 合并：合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程，下面是要排序

    2024年01月21日
    浏览(63)
  • 数据结构与算法—归并排序&计数排序

    数据结构与算法—归并排序&计数排序

    目录 一、归并排序 1、主函数 2、递归实现 3、优化递归  4、非递归实现 5、特性总结： 二、计数排序 1、代码： 2、特性总结： 三、各种排序总结 时间空间复杂度汇总  基本思想： 归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用 分治法 的一个非常典型的

    2024年02月04日
    浏览(47)
  • 数据结构算法--5 归并排序

    数据结构算法--5 归并排序

    我们先看一下归并排序是怎么归并的  两个有序列表，有low指针指向2，high指针指向6，mid指针指向9 再建一个新列表，12，所以1放到列表，右指针右移一位，再比较2和3，2放入列表，左指针右移一位，以此类推，肯定有一部分列表率先没有数，这时将另一列表直接append进入新

    2024年02月11日
    浏览(47)
  • 数据结构与算法：归并排序

    数据结构与算法：归并排序

    在讲解归并排序前，我们先看到一个问题： 对于这样两个有序的数组，如何将它们合并为一个有序的数组？ 在此我们处理这个问题的思路就是：开辟一个新的数组，然后分别安置一个指针在左右数组，利用指针遍历数组，每次对比将比较小的那个元素插入到数组的尾部。 像

    2024年01月21日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包