当前位置:   article > 正文

C语言实现快速排序_快速排序代码c语言

快速排序代码c语言


快速排序:快速排序是冒泡排序的改进,它的 基本思想是定义一个基准数(一般取第一或最后一个数),每次快排把比这个基准数小的放一边,比它大的放另一边,再把基准数插入,这样基准数的位置就排好了,然后再对两边进行快排,最后就达到了有序。

一、递归实现快速排序

1、挖坑法

挖坑法就是定义一个基准数(key),把key取出,形成一个坑
在这里插入图片描述
然后从右向左找一个比key小的数 ,把它挖出放到前面那个坑,这样就又形成了一个新的坑
在这里插入图片描述
再从左向右找一个比key大的数,把它挖出放到后面那个坑 ,然后形成一个新坑
在这里插入图片描述
然后又从右向左找一个比key小的数,再挖坑填坑
在这里插入图片描述
再从左向右找一个比key大的数,挖坑填坑在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
最后begin>=end挖坑就结束了,这时候把key放入最后一个坑,快排的单次排序就结束了,此时key(6)的一边比它小一边比它大,6的位置就排好了。
代码如下:

int PartSort1(int*a,int left,int right)
{
	int begin = left;
	int end = right;
	/*int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);*/
	int key = a[left];
	int pivot = left;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

当我们实现了单次排序后就可以采用分而治之的思路,把6的两边分成两个区间进行递归排序
代码如下:



void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyindex = PartSort1(a, left, right);
	QuickSort(a, left, keyindex - 1);//对key的左边进行递归排序
	QuickSort(a, keyindex + 1, right);//对key的右边进行递归排序
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

2、左右指针法

左右指针法的思想是定义两个指针左指针和右指针,每次右指针向左移动找一个比key(key和上面的挖坑法一样)小的数,左指针向右移找一个比key大的数,然后把这个两个数交换,然后再移动交换,最后左指针和右指针相遇的时候把key和左指针交换序列就排好了。
图解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这样我们的的单次排序就好了,然后就和挖坑法一样分成左右区间,再递归排序就好了

int PartSort2(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);
	int key = a[left];
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[left]);
	return begin;
}
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	//int keyindex = PartSort1(a, left, right);
	int keyindex = PartSort2(a, left, right);
	//int keyindex = PartSort3(a, left, right);
	QuickSort(a, left, keyindex - 1);
	QuickSort(a, keyindex + 1, right);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

3、 前后指针法

前后指针法和左右指针法类似,都是定义两个指针,通过指针找比key大的数,然后交换,最后交换key和prev指针,单次排序就好了,然后进行递归排序,序列就有序了。
图解:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
经过上面的步骤单次排序就好了。
代码如下:

int PartSort3(int* a, int left, int right)
{
	int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);
	int prev = left, cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	//int keyindex = PartSort1(a, left, right);
	int keyindex = PartSort2(a, left, right);
	//int keyindex = PartSort3(a, left, right);
	QuickSort(a, left, keyindex - 1);
	QuickSort(a, keyindex + 1, right);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

完整代码:

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include <stdlib.h>

void PrintArray(int* a, int n)//把数组中的元素打印出来
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)//交换两个值
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//挖坑法
int PartSort1(int*a,int left,int right)
{
	int begin = left;
	int end = right;
	int key = a[left];
	int pivot = left;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}
//左右指针法
int PartSort2(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int key = a[left];
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[left]);
	return begin;
}
//前后指针法
int PartSort3(int* a, int left, int right)
{
	int prev = left, cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyindex = PartSort1(a, left, right);//挖坑法
	//int keyindex = PartSort2(a, left, right);//左右指针法
	//int keyindex = PartSort3(a, left, right);//前后指针法
	QuickSort(a, left, keyindex - 1);
	QuickSort(a, keyindex + 1, right);
}
void TestQuickSort()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(a, 0,sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestQuickSort();
	return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109

二、非递归实现快速排序

递归实现快速排序虽然代码更简洁清晰,可读性更好;但其时间和空间消耗比较大、很多计算都是重复的、调用栈可能会溢出。因此,我们还需要掌握非递归实现快速排序。
非递归实现快速排序我们是用栈来实现的,每次单次排序前我们把要排的区间放入栈,再从栈中取出进行单次排序,再把key的左右区间放入栈,再对其单次排序,再取出……直到栈为空,我们就排好了。
图解:
在这里插入图片描述
把keyindex的两边入栈
在这里插入图片描述
然后再入栈,再取出排序
在这里插入图片描述
……(中间省略)
在这里插入图片描述
在最后我们可以看到,栈已经被取空了,排序就结束了
代码如下:

void PrintArray(int* a, int n)//把数组中的元素打印出来
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)//交换两个值
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void QuickSortNonR(int *a,int n)
{
	ST st;
	StackInit(&st);
	StackPush(&st, n - 1);
	StackPush(&st, 0);
	while (!StackEmpty(&st))
	{
		//把区间从栈中取出排序
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyindex = PartSort3(a, left, right);//此处也可以挖坑或前后指针
		//把左右区间入栈
		if (keyindex+1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyindex + 1);
		}
		if (keyindex-1 > left)
		{
			StackPush(&st, keyindex - 1);
			StackPush(&st, left);
		}
	}
}
void TestQuickSortNonR()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

三、快速排序的优化

优化1:三数取中

我们知道快速排序是根据key的值采用分而治之的思路实现的,但是,如果key的值太小或太大就会出现一边倒的情况,那么快速排序的效率就会降低很多,如图:
在这里插入图片描述
对此,科学家们引入了三数取中
代码如下:

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (mid > left)
	{
		if (mid < right)
			return mid;
		else
			return right;
	}
	else
	{
		return left;
	}
}
int PartSort1(int*a,int left,int right)
{
	int begin = left;
	int end = right;
	//三数取中
	int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);
	
	int key = a[left];
	int pivot = left;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47

即让key取left、right和(left+right)之中的中间值

优化2:小区间排序

在均分下,对一个序列我们要递归logN次,而随着递归层数的增加我们递归调用的空间就越来越多,如图:
在这里插入图片描述
从上图我们可以看出,当需要排列的数足够多时,最后几层递归调用的空间是非常大的,所以在最后的几层小区间(具体大小可以自己定,但一般是十几)排序是我们不采用递归排序,而是直接用插入排序来代替,这样递归调用的空间就会大大减少,效率就提高了。
代码如下:

void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyindex = PartSort1(a, left, right);
	//int keyindex = PartSort2(a, left, right);
	//int keyindex = PartSort3(a, left, right);
	//小区间优化
	if (keyindex - left-1 > 10)
	{
		QuickSort(a, left, keyindex - 1);
	}
	else
	{
		InsertSort(a + left, keyindex - left);
	}
	if (right - keyindex-1 >10)
	{
		QuickSort(a, keyindex + 1, right);
	}
	else
	{
		InsertSort(a + keyindex + 1, right - keyindex);
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

四、快速排序的时间复杂度及稳定性

快速排序在最坏的情况下时间复杂度为O(N^2),最好情况下时间复杂度为O(N*logN),但在引入三数取中后快速排序基本不会出现最坏情况。
快速排序在最好的情况下空间复杂度为O(logN),最坏为O(N)。
快速排序可能会改变两个相同元素的位置,因此快排不稳定

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/编程探险家2/article/detail/63008
推荐阅读
相关标签
  

闽ICP备14008679号