3秒的你对战“它”有没有胜算——quicksort

目录

1.快排思路

2.分块实现

3.代码实现

 

1.快排思路

快速排序的基本思路就是选择一个基数.（我们这个基数的选择都是每一组最左边的数）

然后排成：

1.基数左边都是不大于它的࿰c;左边都是不小于它的

2.然后左边、右边继续进行这个基本思路

以完成排序作为最后的结束

2.分块实现

以6个数为一个例子吧！

4࿰c;2 ࿰c;6࿰c;3࿰c;1࿰c;5

第一步：确定一个基数࿰c;以每次排序最左边的数为基数。本次是4。

第二步：左边（用i表示）从第二个数开始与基数进行比较（遇见比基数大的停止比较）࿰c;右边（用j表示）从最右边开始与基数进行比较（遇见比基数小的停止比较）

第三步：当i࿰c;j停止时࿰c;它们所对应的值进行交换࿰c;直到i࿰c;j同时指向同一个值的时候࿰c;将这个值与基数进行交换。

接着进行循环这三个步骤࿰c;每一次基数的左边进行上面的操作࿰c;每一次基数的右边也进行上面的操作。直至排序完成。

3.代码实现

1.创建一个较大一点的数组（用于储存输入的数）和需要排序的个数

这里先创建全局变量࿰c;为了减少内存的利用

#include <stdio.h>
int arr[100], n;
int main()
{
	
	return 0;
}

2.输入需要排序的个数和输入一组数

int a;
	scanf("%d", &n);
	for (a = 0; a < n; a++)
	{
		scanf("%d", &arr[a]);
	}

3.排序（核心）（创建函数进行排序）

1）以最左边的值为基数࿰c;从最右边的数进行比较࿰c;遇到小于或者等于基数的值的时候停止࿰c;记下此时该数的下标。然后左边开始查找࿰c;遇到大于或者等于基数的值的时候停止࿰c;记下此时该数的下标。

while (arr[j] >= arr[temp]&&i<j)
		{
			j--;
		}
		while (arr[i] <= arr[temp] && i < j)
		{
			i++;
		}

2）交换下标所对应的数࿰c;当左右下标对应同一个值时࿰c;将该值与基数交换（第一次排序完毕）

while (i < j)
	{
		
		while (arr[j] >= arr[temp]&&i<j)
		{
			j--;
		}
		while (arr[i] <= arr[temp] && i < j)
		{
			i++;
		}
		t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
	}
	t = arr[left];
	arr[left] = arr[i];
	arr[i] = t;

3）用递归的方式不断的进行排序࿰c;基数左边࿰c;右边都需要用递归࿰c;递归结束的条件（左下标大于右下标）

if (i > j)
		return 0;
quicksort(left, i);//左
	quicksort(j+1, right);//右

该排序函数模块

int quicksort(int left,int right)
{
	int temp = left;
	int i = left;
	int j = right - 1;
	int t = 0;
	if (i > j)
		return 0;
	while (i < j)
	{
		
		while (arr[j] >= arr[temp]&&i<j)
		{
			j--;
		}
		while (arr[i] <= arr[temp] && i < j)
		{
			i++;
		}
		t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
	}
	t = arr[left];
	arr[left] = arr[i];
	arr[i] = t;
	quicksort(left, i);//左
	quicksort(j+1, right);//右
	return 0;
}

4）打印出来拍好的序列

for (a = 0; a < n; a++)
	{
		printf("%d ", arr[a]);
	}
	printf("n");

听我讲了这么久࿰c;我们已经实现了快速排序

下面看完整的代码

#include <stdio.h>
int arr[100], n;
int quicksort(int left,int right)
{
	int temp = left;
	int i = left;
	int j = right - 1;
	int t = 0;
	if (i > j)
		return 0;
	while (i < j)
	{
		
		while (arr[j] >= arr[temp]&&i<j)
		{
			j--;
		}
		while (arr[i] <= arr[temp] && i < j)
		{
			i++;
		}
		t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
	}
	t = arr[left];
	arr[left] = arr[i];
	arr[i] = t;
	quicksort(left, i);//左
	quicksort(j+1, right);//右
	return 0;
}
int main()
{
	int left, right;
	int a;
	scanf("%d", &n);
	for (a = 0; a < n; a++)
	{
		scanf("%d", &arr[a]);
	}
	left = 0;
	right = n;
	quicksort(left,right);
	for (a = 0; a < n; a++)
	{
		printf("%d ", arr[a]);
	}
	printf("n");
	return 0;
}