快排C语言三种实现方法(大同小异)

快速排序C语言版(附带视频讲解)

注：3种快排的名字是我自己取的，并非专业名称

方法一(最常用的方法)：左端抽轴(pivot)法

思路 && 操作：

1. 排序准备：取左边第一位数为pivot轴，即pivot = a[0]，
   再令left = a[0]，right = a[N-1]
2. 排序过程：此时从右端(right)开始，比较right对应的数
   与pivot轴的大小，如果右边比pivot大(a[right] > pivot)
   下标左移(right–)，反之，将a[right]放在a[left]位置
3. 完成一次操作(PartSort())循环结束条件为：left != right
4. 递归函数进入条件：left < right

视频讲解：请点击->动画

代码如下：

#include <stdio.h>
#define N 15

int PartSort(int * a, int left, int right);
void QuickSort(int * a, int left, int right);
void Print(int * a);

int main(void)
{
	int i, a[N] = {5, 8, 1, 7, 4, 9, 48, 14, 0, 99, 45, 2, 84, 65, 6};

	printf("Before sort:\n");
	Print(a);
	printf("\nAfter sort:\n");
	QuickSort(a, 0, N-1);
	Print(a);
	
	return 0;
}

int PartSort(int * a, int left, int right)
{
	int pivot = a[left];
	while (left != right)
	{
		while (left < right && a[right] >= pivot)
		   right --;
		a[left] = a[right];
		while (left < right && a[left] <= pivot)
		   left ++;
		a[right] = a[left];
	}
	a[left] = pivot;
	
    return left;
}

void QuickSort(int * a, int left, int right)
{
	int mid = 0;
	

	if (left < right)
	{
	   mid = PartSort(a, left, right);
		QuickSort(a, left, mid-1);
		QuickSort(a, mid+1, right);
	}
	
	return;
}

void Print(int * a)
{
	int i;
	for (i = 0; i < N; i ++)
	   printf("%d ", a[i]);
	printf("\n");
	
	return;
}
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

运行结果如下：

方法二：右端基准(basic)法

思路 && 操作：

1. 排序准备：选取最右端数字为basic(基准)，最左端标记为L(left)，
   右端倒数第二个数标记为R(right)
2. 排序过程：从左端开始，L指向的数比basic所指数小，则L向后移动一位(left++)
   否则则停下；后，右端开始出发，如果R所指向的数字比basic大，则R向前移动
   一位(right–)，直到R也停下，此时将二者对应的数字进行交换，L后移，R前移
   各一位完毕后，再从左端开始重复以上操作
3. 完成一次操作(PartSort())循环结束条件为 :left < rigt(而非left != rigt)
   因为数字交换导致的L和R分别进位可能会导致二者"擦肩而过"，永世不得相遇
4. 递归函数进入条件为：left < right 代码如下

视频讲解：请点击->动画

注：该视频所讲述略有瑕疵，视频中说L(left)与R(right)相遇后，L与R所指的同一个数(a)要与basic基准交换。实际上，交不交换取决于该数(a)与basic的大小，如果该数(a)大于basic基准，肯定要作交换，但是反之，就不能直接交换了，需要用该数(a)的下一个数与basic交换，想想为什么

举个例子：3 2 1 5(basic) —进行操作— 3 2 1 5(basic)

​ L R ----doing… — L&R

这个时候1 就不能和 5 换位置，换了就变成 3 2 5 1，1比5小怎么在5右侧？

实际上：每一次的basic的轴都是将一组数分割成两组的中心轴！

代码如下：

#include <stdio.h> 
#define N 15 

void Swap(int * a, int left, int basic);
int PartSort(int * a, int left, int right);
void QuickSort(int * a, int left, int right);
void Print(int * a);

int main(void)
{
	int a[N] = {5, 8, 1, 7, 4, 9, 48, 14, 0, 99, 45, 2, 84, 65, 6};

	printf("Before sort:\n");
	Print(a);
	QuickSort(a, 0, N-1);
	printf("\nAfter sort:\n");
	Print(a);
	
	return 0;
} 

void Swap(int * a, int left, int  param)
{
	int temp;
	temp = a[left];
	a[left] = a[param];
	a[param] = temp;

    return;
}

int PartSort(int * a, int left, int right)
{
	int basic = right --;
	
	while (left < right)
	{
		while (left < right && a[left] <= a[basic])
		   left ++;
		while (left < right && a[right] >= a[basic])
		   right --;
		if (left != right)  
		{
			Swap(a, left, right);
			left ++;
			right --;
	    }
		
	}
	if (a[left] > a[basic])  Swap(a, left, basic);
	else  Swap(a, ++ left, basic);
	
	return left;
}

void QuickSort(int * a, int left, int right)
{
	int mid = 0;
	
	if (left < right)
	{
		mid = PartSort(a, left, right);
		QuickSort(a, left, mid-1);
		QuickSort(a, mid+1, right);
	}
	
	return;
}

void Print(int * a)
{
	int i;
	for (i = 0; i < N; i ++)
	   printf("%d ", a[i]);
	printf("\n");
	return;
}
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

运行结果如下：

方法三：快慢指针(i,j)法

思路 && 操作：

1. 排序准备：快慢指针的构建，i为慢指针，j为快指针；取最右端为pivot轴
   指针初始位置为： j为最左端，i为j的前一位(没错，刚开始i不对应数字)
2. 排序过程：如果快指针j对应的数字比pivot小，则慢指针i前进1位， 然后将
   快慢指针对应的值进行交换；如果快指针j对应的数字比pivot大，则慢指针i
   不动最后，将慢指针右1位的数字（即i+1）对应的数字与pivot轴进行交换
3. 完成一次操作(PartSort())循环结束条件为：快指针小于pivot轴位置(即j < pivot)
4. 递归函数进入条件：start < end

视频讲解：请点击->视频

代码如下：

#include <stdio.h>
#define N 15

void QuickSort(int * a, int start, int end);
int PartSort(int * a, int start, int end);
void Swap(int * a, int i, int j);
void Print(int * a);

int main(void)
{
	int a[N] = {5, 8, 1, 7, 4, 9, 48, 14, 0, 99, 45, 2, 84, 65, 6};
	
	printf("Before sort:\n");
	Print(a);
	QuickSort(a, 0, N-1);
	printf("\nAfter sort:\n");
	Print(a); 
	
	return 0;
} 

void QuickSort(int * a, int start, int end)
{
	int mid = 0;
	
   if (start < end)
	{
		mid = PartSort(a, start, end);
		QuickSort(a, start, mid-1);
		QuickSort(a, mid+1, end); 
	} 
	
	return;
}

int PartSort(int * a, int start, int end)
{
	int i = start - 1;
	int j = start, pivot = end;
	
	for (; j < end; j ++)
	{
		if (a[j] < a[pivot])
		{
			i ++;
			Swap(a, i, j);
		}
	}
	Swap(a, i + 1, pivot);
	pivot = i + 1; 
	
	return pivot;
}

void Swap(int * a, int i, int j)
{
	int temp;
	
	temp = a[i];
	a[i] = a[j];
	a[j] = temp;
	
	return;
}

void Print(int * a)
{
	int i;
	for (i = 0; i < N; i ++)
	   printf("%d ", a[i]);
	printf("\n");
	
	return;
}
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

运行结果如下：

以上就是与大家分享的全部内容啦，如果觉得对你有帮助，不妨点赞、收藏哦，当然如果有什么谬误，还请大家不吝赐教！谢谢观看！