[数据结构] 基于交换的排序 冒泡排序&&快速排序

标题：[数据结构] 基于交换的排序 冒泡排序&&快速排序

@水墨不写bug

（图片来源于网络） 

目录

（一）冒泡排序

优化后实现：

（二）快速排序

I、实现方法： 

（1）hoare法

hoare法实现快排：

 （2）挖坑法

挖坑法实现：

（3）双指针法 

双指针法实现： 

 II、快速排序复杂度分析：

比较完备的快速排序实现如下：

正文开始：

（一）冒泡排序

 

时间复杂度：O（N^2）

空间复杂度：O（1）

特点：数组接近有序时，可通过优化来提高效率。

稳定性：稳定

冒泡排序：

        基本思想：大数下沉，小数上浮。

        实现思路：从内循环到外循环，从一趟到多趟。

        冒泡排序通过两层循环来实现，内层循环实现其中的一趟遍历，在一趟的遍历中，需要注意要控制好左右区间边界，冒泡排序的实现方式是多样的，无论用何种实现方式，最主要的是控制好边界，以及内外层循环的衔接；以下是一种冒泡排序的写法：

void BubbleSort(vector<int>& nums)
{
	int n = nums.size();
	for (int j = 0; j < n - 1; ++j)
	{
		for (int i = 0; i < n - 1 - j; ++i)
		{
			if (nums[i] > nums[i + 1])
			{
			
				::swap(nums[i], nums[i + 1]);
			}
		}
	}
}

优化：

        如果在一次遍历的过程中，没有进入if（）交换，这已经说明数组已经有序，可以直接停止排序。

优化后实现：

void BubbleSort(vector<int>& nums)
{
	int n = nums.size();
	for (int j = 0; j < n - 1; ++j)
	{
		int ex = 0;
		for (int i = 0; i < n - 1 - j; ++i)
		{
			if (nums[i] > nums[i + 1])
			{
				ex = 1;
				::swap(nums[i], nums[i + 1]);
			}
		}
		if (ex == 0)
			break;
	}
}

（二）快速排序

时间复杂度：O（NlogN）

空间复杂度：

特点：当数据接近有序，比如逆序的时候；或者选取的key在数据中大量存在时，快速排序时间复杂度会退化为O（N^2），这是相当严重的缺陷。

稳定性：不稳定。

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。

        基本思想：任取待排序元素序列中的某元素（记为key）作为基准值，按照key值将待排序集合分割成两子序列，左子序列中所有元素均小于基准值key，右子序列中所有元素均大于基准值key。然后递归，左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

        本质就是将数组根据key值分为两部分，一部分比key大，一部分比key小。对于每一个部分，再次进行如上操作，直到数组不可再分为止。这就是递归实现的浅层次的直观理解。但是递归不是本文的重点，关于递归，我会在后面与你分享。 

I、实现方法： 

（1）hoare法

        hoare法是快排的提出者hoare提供的方法，是一种经典的实现方法。

实现原理：

        定义两个下标：左下标L  和  右下标R；

        随机选取一个key值，习惯上我们选择区间的最左侧的元素为key；

        让右下标先走，向左寻找比key小的值，找到后停下来：

 停下来后：

 左下标再向右寻找比key大的值，找到后停下来：

此时，交换两个下标对应的值：

 

接下来继续执行上述步骤（R先走），我展示关键步骤：

 两下标找到要求目标并交换：

直到遇到特殊情况：两下标相遇

 

 这时停止停止循环，将最左侧元素与相遇处的元素交换位置：
即可完成一次二分。

        接下来，对于左右区间再次进行上述操作，直到区间不可再分为止。

---

但是如何保证相遇处的值一定小于key呢？

对于相遇这个事件，有且仅有两种情况：

只可能是R向左移动遇到L；或者是L向右移动遇到R；

        （1）R向左移动遇到L：有两种可能情况

                        a，第一次R由于没有找到比key小的值，直接一路向左遇到left，此时left就是key，然后执行自己与自己交换：此时相遇的位置的值就是key本身。

                        b，第一次之后R向左遇到L，你要想清楚，在此之前L停止的地方是被交换后的原先R的值（它是比key小的）；在这样的前提条件下，R向左移动与L相遇了，说明R没有找到小于key的元素，与L相遇后指向L的比key小的值。

        （2）L向右移动遇到R

                        R先走，在找到比key小的位置停下，在此前提下，L向右移动与R相遇了，L指向R的比key小的值。

hoare法实现快排：

void QuickSort(vector<int>& nums,int left,int right)
{
	//递归出口，此时区间不存在或者只有一个值
	if (left >= right)
		return;
	//保存左右下标的值，便于在递归时找到原来的区间边界
	int begin = left, end = right;
	//keyi来记录左区间的下标
	int keyi = left;

	while (left < right)
	{
		//右下标先走，找小
		while (left < right && nums[keyi] <= nums[right])
		{
			--right;
		}//左区间再走，找大
		while (left < right && nums[left] <= nums[keyi])
		{
			++left;
		}
		::swap(nums[left], nums[right]);
	}//此时一趟完毕，将key与相遇位置交换
	::swap(nums[left], nums[keyi]);
	keyi = left;//更新keyi

	//递归左右区间
	QuickSort(nums, begin, keyi);
	QuickSort(nums, keyi+1, end);
}

 （2）挖坑法

实现原理：

        由于左边有坑，所以右下标先走。

        找小，找到后停下来，将找到的值放在坑中，R的位置就成为了新的坑：

此时坑在右边，左边下标先走，找大：

找到后交换，左边又成为新的坑。

以此类推，直到左右相遇，相遇的位置一定是坑，此时将key放到坑中，完成单趟：

依然是左边都是比6小，右边都是比6大，说明没有错误。

挖坑法实现：

void QuickSort_(vector<int>& nums, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;
	int key = nums[left];//记住key的值
	int hole = left;//开始挖坑
	while (left < right)
	{
		//右先找比key大的
		while (left < right && nums[right] >= key)
			right--;
		//找到后，填坑，然后挖新坑
		nums[hole] = nums[right];
		hole = right;
		//左找比key小的
		while (left < right && nums[left] <= key)
			left++;
		//找到后，填坑，然后挖新坑
		nums[hole] = nums[left];
		hole = left;
	}
	//此时相遇了，把key值放在坑里
	nums[hole] = key;

	QuickSort_(nums,begin,hole);
	QuickSort_(nums,hole + 1,end);
}

（3）双指针法 

 

// 设置前指针prev，指向首元素，遍历指针cur指向第二个元素，
// 接下来cur开始找小，如果没找到小，就一直往前走；

//如果找到小的了，就先停下来，然后prev往前走一步，再和cur交换值，然后cur继续向后，重复上述步骤，
// 最后cur走出数组后，循环终止！此时prev指向的位置和keyi的位置交换。

我们详细看一下过程：

        

双指针法实现： 

void QuickSort__(vector<int>& nums, int left, int right)
{
	if (left >= right)
		return;
	int begin = left, end = right;
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)//cur走出数组循环停止
	{
		//cur一直在走，如果遇到比keyi小的，就停下来等perv走一步后交换，再接着走
		if (nums[cur] < nums[keyi] && ++prev != cur)
			swap(nums[prev], nums[cur]);
		cur++;
	}
	//cur出去后，prev的值和keyi交换
	swap(nums[keyi], nums[prev]);
	QuickSort__(nums,left,keyi);
	QuickSort__(nums,keyi+1,end);
	
}

 II、快速排序复杂度分析：

        传统的快速排序在处理一些极端问题时会显得无力，接下来我们就来讨论这些极端情况，并且给出应对极端情况的方法：

1.对于选择key不合适的问题：

        在数组元素接近逆序的时候，由于我们总是在区间的最左侧选取key，如果数组接近逆序，这时选取的key无法有效的将数组分为两个等大的数组，这就导致一次只能排序一个元素，这导致快速排序的复杂度会退化为O（N^2）,这就需要我们不能随便取key。可以通过随机数法在区间内随机取一个元素作为key即可。

2.关于选择key大量出现的问题：

        如果key大量出现，也会导致上述的情况，一次只能排序一个数，所以我们不能随便分区间，这就要求我们将数组分为三部分，左侧区间都小于key，中间区间则是数值等于key的元素，右侧区间是大于key的数值。

比较完备的快速排序实现如下：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums,0,nums.size()-1);
        return nums;
    }
    void qsort(vector<int>& nums,int l,int r){
        //递归出口
        if(l >= r) return;
        //数组分三块
        int key = GetRandom(nums,l,r);
        int cur = l,left = l-1,right = r+1;
        while(cur < right){
            if(nums[cur] < key) swap(nums[++left],nums[cur++]);
            else if(nums[cur] == key) cur++;
            else swap(nums[--right],nums[cur]); 
        }
        //递归排序子区间
        qsort(nums,l,left);
        qsort(nums,right,r);
    }
    int GetRandom(vector<int>& nums,int left,int right){
        return nums[ rand() % ( right - left + 1 ) + left];
    }
};

 完~

未经作者同意禁止转载