零、前言

最近做面试题中，遇到一些平时学习中比较少注意到的问题，记录下来以便后来者学习讨论。

请添加图片描述

一、快速排序的步骤原理

要了解快速排序为什么不稳定，还需要从它的步骤原理入手。
那么，快速排序的步骤是什么呢？

1、选取基准数字。
2、开始遍历，如果数字比基准大，则位置不变，如果比基准小，则将该值与前面第一个比基准大的值交换位置，如果前面没有比基准大的数字就不用替换了。
3、完成一边遍历后，交换头部的基准数字和最后一个比基准数字小的数字的位置，可以保证基准数字前面的值都小，后面的都大。
4、重复1-3的步骤。

快速排序动图如下：

二、什么是稳定性？

既然要讨论快速排序为什么不稳定，那么也应该明确什么是稳定性！

通常，在排序算法中，稳定性 是指如果两个元素在原始数组中的相对顺序保持不变，则在排序后它们的相对顺序也应该保持不变。
换句话说，如果有两个相等的元素，它们的位置在排序之前是 a 和 b，且 a 在 b 的前面，那么在排序后，a 仍然应该在 b 的前面。

三、不稳定的地方在哪里？

1、选取基准数字上，一般选取 头部（或尾部），此时，如果相等的元素可能被分到不同的 子数组 中，从而改变它们的 相对顺序。

举个例子

数组为 [5, 3, 2, 5, 1]，在基准数字选择为 第一个 元素时，第一次分割后，数组变为 [3, 2, 1, 5, 5]，其中左边的子数组 [3, 2, 1] 中的元素都小于基准 5，右边的子数组 [5, 5] 中的元素都不小于基准 5。然后，递归地对左右两部分进行排序，最后得到排序后的数组 [1, 2, 3, 5, 5]。
.
例子中，结果是正确的，但是可以看到，原数组中的两个相等的元素 5 的相对位置在排序后发生了变化。原本，第一个出现的 5 在第二个出现的 5 的前面，但在排序后，第一个出现的 5 在第二个出现的 5 的后面。而相等元素的相对顺序应该保持不变，显然这就违背了 稳定性 的定义。

2、既然选择头部和尾部都不稳定，那如果选取基准数字是 随机选取 ，或者数组随机化，会不会也导致出现排序的不稳定？答案是肯定的。

        假设基准数字是随机选择，此时它们的相对顺序是无法确定的。
        在快速排序每一次迭代中，基准数字将数组分割为两个子数组，其中一个子数组中的元素都小于基准，另一个子数组中的元素都大于基准。如果有相等的元素，那么它们可能会被随机选择的基准分配到不同的子数组中。
        这样，在每一次迭代中，相等元素的相对顺序可能会发生变化，因为它们被随机分配到不同的子数组。
        这样看来，基准数字的 随机选取 似乎是稳定的。
        然而，由于基准数字是随机选择的，每次排序的结果可能都会不同。在某些情况下，随机选择的基准可能会导致相等元素的相对顺序发生变化，而在其他情况下，它们的相对顺序可能会保持不变。
        因此，快速排序在基准数字随机选择的情况下，虽然能够提高平均性能可能是稳定的，但也可能是不稳定的。

3、若是使用 交换，一旦中间元被交换，与中间元相同的值与中间元的相对位置可能会被改变，除非新开O(n)空间。
而如果是 插入 则该算法稳定，不过数组的插入本身效率低。

四、怎么让快速排序变得稳定？

从前面的分析，我们不难找到，快速排序之所以不稳定是因为，相等元素的相对顺序发生变化。
要使得快速排序变得稳定，变要从此处切入。

那么便有以下思路：

(1) 保留相等元素的相对顺序 :
在进行元素比较和交换时，只有在相邻元素的值不相等时才进行交换。这样可以确保相等元素的相对顺序保持不变。但这个方法可能会导致排序的性能降低，因为需要额外的比较操作。
(2) 使用稳定的排序算法进行子数组的排序
在快速排序的过程中，当遇到子数组的大小较小时，可以切换到使用稳定的排序算法，如归并排序或插入排序，对该子数组进行排序。这样可以保证子数组的稳定性，并最终保持整个排序的稳定性。

1、采用双指针的快速排序

A 思路简述

基于快速排序的分治思想。选择数组中的一个元素作为枢轴（一般是第一个元素），然后将数组划分为两个子数组，其中一个子数组的元素都小于等于枢轴元素，另一个子数组的元素都大于枢轴元素。然后对这两个子数组分别递归调用快速排序算法，继续进行划分和排序。递归的基本情况是子数组的长度为1或0，即已经有序或为空数组，不需要再进行排序。通过不断划分和排序，最终实现整体的排序。在划分过程中，通过比较元素与枢轴的大小关系，将元素放置到正确的位置上，并维护相等元素的相对顺序。通过递归和划分的方式，快速排序算法能够高效地对一个数组进行排序

B 参考代码 :

// 划分过程
int partition(vector<int>& a, int l, int r) 
{
    int p = a[l]; // 选择枢轴
    int i = l + 1 , j = r;

    while (i <= j) 
    {
        if (a[i] <= p) 
            i++;
		else if (a[j] > p)
            j--;
        else 
            swap(a[i], a[j]); 	// 保留相等元素的相对顺序
    }
    swap(a[l], a[j]);

    return j;
}

void quick_Sort_01(vector<int>& a, int l, int r) 
{
    if (l  < r) 
    {
        int p = partition(a, l , r);
        quick_Sort_01(a, l , p - 1);	// 递归排序左侧子数组
        quick_Sort_01(a, p + 1, r);		// 递归排序右侧子数组
    }
}

C 算法分析

(1) 划分过程：
划分过程使用了双指针法，通过比较元素与枢轴的大小关系，将元素分为两个子数组。在相等元素时，使用交换操作保持相等元素的相对顺序。
(2) 递归过程:
使用递归来对划分得到的子数组进行快速排序，分别递归调用quickSort函数。对于左子数组，递归调用quick_Sort_01(a, l, p-1)，对于右子数组，递归调用quick_Sort_01(a, p+1, r)。
(3) 返回结果
该算法是对原始数组进行原地排序，只是对原数组进行交换操作实现的排序，不需要返回额外的结果。

2、基于递归的快速排序

在这里插入图片描述
如果对递归定义不清晰，请点击👉👉👉 【算法思想】啊，递"龟” 还是递归？

A 思路简述

选择一个枢轴元素，将原始数组划分为两个子数组，其中一个子数组的元素都小于枢轴元素，另一个子数组的元素都大于等于枢轴元素。然后对两个子数组分别递归调用该算法进行排序，最后合并两个排序好的子数组，得到最终的排序结果。这个过程不断递归，直到子数组的长度为1或0，即达到了基本情况。通过分治和递归的思想，这个算法能够将一个大问题拆解为多个小问题，最终实现整体的排序。

B 参考代码


vector<int> quick_Sort_02(vector<int>& arr) 
{
    if (a.size() <= 1) 								//(1)
        return a;
    
    vector<int> l, r;
    for (int i = 1; i < a.size(); i++) 				//(2)
    {
        if (a[i] < a[0]) 							//(3)
            l.push_back(a[i]);
        else 										//(4)
            r.push_back(a[i]);
    }
    
    l = quick_Sort_02(l), r = quick_Sort_01(r);		//(5)
    l.push_back(a[0]);								//(6)
    l.insert(l.end(), r.begin(), r.end());			//(7)
    
    return l;
}

(1) 如果数组大小为1或更小，则已经排序完成
(2) 根据第一个元素（枢轴）对数组进行划分
(3) 将小于枢轴的元素放入左侧向量
(4) 将不小于枢轴的元素放入右侧向量
(5) 递归地对左右向量进行排序
(6) 将枢轴元素追加到左向量末尾
(7) 将排序后的右向量追加到左向量后面
(8) 返回合并后的排序向量

C 算法分析

枢轴选择：
传统的快速排序算法通常选择第一个或最后一个元素作为枢轴，并根据枢轴将数组划分为两个子数组。而这个方法将第一个元素作为枢轴，然后遍历剩余元素，将小于枢轴的元素放入左侧向量，大于枢轴的元素放入右侧向量。因此，枢轴元素不会在位置交换时移动。
循环方式：
传统的快速排序算法使用递归来划分和排序子数组。这个方法使用循环来遍历数组元素，并根据枢轴将它们划分为左右两个子数组，分别递归调用quick_Sort_02函数。对于左子数组，递归调用quick_Sort_02(l)，对于右子数组，递归调用quick_Sort_02®。
子问题处理：
在递归调用时，这个方法使用类似快速排序的思想对左右子数组进行排序。然而，不同于原地排序的传统快速排序算法，这个方法每次递归都创建一个新的排序向量。
过递归调用MySort函数对子数组进行排序，并将排序好的左右子数组进行合并后返回最终的排序结果。

3、采用归并算法的快速排序

int partition(vector<int>& a, int l, int r) 
{
    int p = a[l]; // 选择枢轴
    int i = l + 1 , j = r;

    while (i <= j) 
    {
        if (a[i] <= p) 
            i++;
		else if (a[j] > p)
            j--;
        else 
            swap(a[i], a[j]); 	// 保留相等元素的相对顺序
    }
    swap(a[l], a[j]);

    return j;
}
void merge(vector<int>& a, int l, int mid, int r)  	//(1)
{
	int n1 = mid - l + 1;
	int n2 = r - mid;

	vector<int> left(n1), right(n2);

	
	for (int i = 0; i < n1; i++) 					// (2) 
    	left[i] = a[l + i];	
	for (int j = 0; j < n2; j++)					// (3) 
    	right[j] = a[mid + 1 + j];

	int i = 0, j = 0, k = l;

	while (i < n1 && j < n2) 						// (4)
	{
    	if (left[i] <= right[j]) 
    	{
        	a[k] = left[i];
        	i++;
    	} 
    	else 
    	{
        	a[k] = right[j];
        	j++;
    	}
   	 	k++;
	}

	while (i < n1) 									//(5)
	{
    	a[k] = left[i];
    	i++;
    	k++;
	}

	while (j < n2) 
	{
    	a[k] = right[j];
    	j++;
    	k++;
	}
}


void mergeSort(vector<int>& a, int l, int r) 		//(6)
{
	if (l < r) 
	{
		int mid = l + ((r - l) >> 1);
		mergeSort(a, l, mid); 						// (7)
		mergeSort(a, mid + 1, r); 					// (8)
		merge(a, l, mid, r); 						// (9)
	}
}

void quickSort(vector<int>& a, int l, int r, int jud) 
{
	if (l < r) 
	{
		if (r - l + 1 < jud) 
			mergeSort(a, l, r); 					// (10)
		else 
		{
			int p = partition(a, l, r);
			quickSort(a, l, p - 1, jud);  // (11)
			quickSort(a, p + 1, r, jud);  // (12)
		}
}

(1) 采用归并排序，merge()函数用于将两个有序子数组 合并 为一个有序数组。它接收一个数组 arr，以及左边界 l，中间位置 mid 和右边界 r，将位于左边界到中间位置的子数组和中间位置到右边界的子数组进行合并。
(2) 将元素拷贝到临时数组 left 中去。
(3) 将元素拷贝到临时数组 right 中去。
(4) 合并临时数组的元素到原数组
(5) 将剩余元素拷贝到数组
(6) mergeSort() 函数使用归并排序进行子数组排序,用于递归地将数组划分为子数组，然后调用 merge 函数进行合并。它接收一个数组 arr，以及左边界 low 和右边界 high，在数组范围内进行递归划分和排序。
(7) 递归排序左侧子数组
(8) 递归排序左侧子数组
(9) 合并两个有序子数组
(10) 判断待排序子数组的长度是否小于阈值 threshold,如果小于阈值，则调用稳定的归并排序算法 mergeSort 对该子数组进行排序。这样可以保证在处理较小范围的子数组时，算法仍能达到较高的效率，并且保持排序的稳定性。
如果大于等于阈值，则继续进行快速排序的操作。
(11) 递归排序左侧子数组
(12) 递归排序右侧子数组