快速排序 vs 归并排序：有什么区别？

2025年4月19日 | 阅读 9 分钟

排序是指将集体数据按特定格式（如升序或降序）排列。通常，它用于以排序的方式排列同类数据。使用排序算法，我们可以按顺序排列数据，并轻松快速地搜索元素。排序技术取决于两种情况，即执行程序所需的总时间和总空间。在本节中，我们将讨论快速排序和归并排序，并对它们进行比较。

快速排序

快速排序是一种基于比较的排序算法，它遵循分治技术来排序数组。在快速排序中，我们通常使用枢轴（键）元素来根据某些条件比较和交换元素的位置。当枢轴元素在数组中获得固定位置时，这表明比较和交换过程已终止。之后，数组被分成两个子数组。第一个分区包含所有小于枢轴（键）元素的元素，而另一个分区包含所有大于枢轴元素的元素。之后，它再次在每个子数组中选择一个枢轴元素，并重复相同的过程，直到数组中的所有元素都被排序为止。

快速排序算法

Partition (A, p, r)

X <- A[r]
I <- p-1
For j <- p to r -1
Do if A[j] <= x
Then I <- I + 1
Exchange A[i] <-> A[j]
Exchange A[I + 1] <--> A[r]
Return I + 1

Quicksort (A, p, r)

While (p < r)
Do q <- Partition (A, p, r)
R <- q-1
While (p < r)
Do q <- Partition (A, p, r)
P <- q + 1

使用快速排序算法对数组进行排序的步骤

假设我们有一个包含元素 X[1], X[2], X[3], ... , X[n] 的数组 X 需要进行排序。让我们按照以下步骤使用快速排序对数组进行排序。

步骤 1：将数组的第一个元素设置为枢轴或键元素。此处，我们假设枢轴为 X[0]，左指针指向第一个元素，右指针指向数组元素的最后一个索引。

步骤 2：现在我们从右侧索引开始扫描数组元素，然后

如果 X[key] 小于 X[right] 或如果 X[key] < X[Right]，

持续减小右端指针变量，直到它等于键。
如果 X[key] > X[right]，则交换键元素与 X[right] 元素的位置。
设置 key = right，并将左索引加 1。

步骤 3：现在我们再次从左侧开始扫描元素，并将每个元素与键元素进行比较。X[key] > X[left] 或 X[key] 大于 X[left]，则执行以下操作

持续将左元素与 X[key] 进行比较，并将左索引加 1，直到键等于左。
如果 X[key] < X[left]，则交换 X[key] 与 X[left] 的位置，然后转到步骤 2。

步骤 4：重复步骤 2 和 3，直到 X[left] 等于 X[key]。因此，我们可以说，如果 X[left] = X[key]，则表示过程终止。

步骤 5：之后，左侧的所有元素都将小于键元素，而右侧的其余元素都将大于键元素。这表明需要将数组划分为两个子数组。

步骤 6：类似地，我们需要对子数组重复执行上述过程，直到整个数组排序完成。

让我们看一个快速排序的例子。

示例：考虑一个包含 6 个元素的数组。使用快速排序对数组进行排序。

arr[] = {50, 20, 60, 30, 40, 56}

在上面的数组中，50 处于其正确的位置。因此，我们将小于枢轴的元素分成一个子数组，将大于枢轴元素的元素分成另一个子数组。

因此，我们得到了排序后的数组。

让我们用 C 语言实现上述逻辑。

Quick.c

#include <stdio.h>
int division_of_array(int x[], int st, int lt); // declaration of functions
void quick_sort(int x[], int st, int lt);
void main()
{
	int i;
	int ar[6] = {50, 20, 60, 30, 40, 56}; // given array elements
	quick_sort(ar, 0, 5);  // it contains array, starting index and last index as an parameters.
	print(" Sorted Array is : \n");
	for(i=0; i<6; i++)
	{
		printf("Array = %d\t", ar[i]);
	}
	int division_of_array(int x[], int st, int lt)
	{
		int left, right, temp, key, flag;
		key = left = st; // initially these variables are in same place.
		right = lt;
		flag = 0;
		while(flag != 1)
		{
			while((x[key] <= x[right]) && (key != right))
			right--;
			if(key == right) // if pivot element is equal to the last index.
			flag = 1;
			else if(x[key] > x[right]) // if pivot is greater than last index.
			{
				temp = x[key];
				x[key] = x[right];
				x[right] = temp;
				key = right;
			}
			if (flag != 1)
			{          /* Repeat the while loop until pivot is greater than left and equal to the left. */
				while((x[key] >= x[left]) && (key != left))
				left++;
				if(key == left)
				flag = 1;
				else if(x[key] < x[left])
				{
					temp = x[key];
					x[key] = x[left];
					x[left] = temp;
					key = left;
				}
			}
		}
		return key;
	}
}void quick_sort(int x[], int st, int lt)
{
	int key;
	if(st<lt) // left index value is greater than right index.
	{
		key = division_of_array(x, st, lt);
		quick_sort(x, st, key-1);
		quick_sort(x, key+1, lt);
	}
	
}

输出

Sorted Array is:
Array = 50  20  60  30  40  56

归并排序

归并排序是最重要的排序技术之一，它基于分治策略。它是用于排序文件中可用数据的最流行的排序技术。归并排序算法将给定数组分成两半（N/2）。然后，它递归地将两个子数组的元素集分成单个或单个元素，或者我们可以说直到无法再分割为止。之后，它比较相应元素以对元素进行排序，最后，将所有子元素合并以形成最终排序的元素。

使用归并排序算法对数组进行排序的步骤

假设我们有一个给定的数组，那么首先我们需要将数组分成子数组。每个子数组可以存储 5 个元素。
这里我们将第一个子数组命名为 A1，并将其分成接下来的两个子数组 B1 和 B2。
类似地，右子数组命名为 A2，并将其分成接下来的两个子数组 B3 和 B4。
此过程将持续重复，直到子数组被分割成单个元素且不再可能进行分区。
之后，比较每个元素与对应的元素，然后开始合并过程，将每个元素以升序排列。
合并过程将继续，直到所有元素都按升序合并。

让我们看一个归并排序的例子。

示例：考虑一个包含 9 个元素的数组。使用归并排序对数组进行排序。

arr[] = {70, 80, 40, 50, 60, 11, 35, 85, 2}

因此，我们使用归并排序得到了排序后的数组。

让我们用 C 语言实现上述逻辑。

Merge.c

#include <stdio.h>
//#include <conio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int end)
{
	int i, j, k;
	int a1 = m - l + 1;
	int a2 = end - m;
	
	// create temp subarray
	int sub1[a1], sub2[a2];
	
	// Store data to temp subarray subArr1[] and subArr2[]
	for (i = 0; i < a1; i++)
		sub1[i] = arr[l + i];
	for (j = 0; j < a2; j++)
		sub2[j] = arr[m + 1 + j];
	
	// Merge the temp array into the original array arr[]
	i = 0;
	j = 0;
	k = l;
	while (i < a1 && j < a2)
	{
		if (sub1[i] <= sub2[j])
		{
			arr[k] = sub1[i];
			i++;
		}
		else
		{
			arr[k] = sub2[j];
			j++;
		}
		k++;
	}
	
	// copry the rest element of subArr1[], if some element is left;
while (i < a1)
{
	arr[k] = sub1[i];
	i++;
	k++;	
}

	// copry the rest element of subArr2[], if some element is left;
while (j < a2)
{
	arr[k] = sub2[j];
	j++;
	k++;	
  }
}

/* st represents the first index and end represents the right index of the subarray of arr[] to be sorted using merge sort. */
void mergeSort(int arr[], int l, int end)
{
	if (l < end)
	{	
		int m = l + (end - l) / 2;
		
		mergeSort(arr, l, m);
		mergeSort(arr, m + 1, end);
		
		merge(arr, l, m, end);
	}
}

// Function to print the merge sort.
void mergePrint(int Ar[], int size)
{
	int i;
	for (i = 0; i < size; i++)
		printf("%d \t", Ar[i]);
	printf("\n");
}

int main()
{
	int arr[] = { 70, 80, 40, 50, 60, 11, 35, 85, 2 };
	int arr_size = sizeof(arr) / sizeof(arr[0]);
	
	printf(" Predefined Array is \n");
	mergePrint(arr, arr_size);
	
	mergeSort(arr, 0, arr_size - 1);
	
	printf("\n Sorted array using the Merge Sort algorithm \n");
	mergePrint(arr, arr_size);
	return 0;
}

输出

Predefined Array is
70      80      40      50      60      11      35      85      2

 Sorted array using the Merge Sort algorithm
2       11      35      40      50      60      70      80      85