写给自家娃看的算法书----快速排序，C语言实现

太过爱你忘了你带给我的痛 2023-03-01 09:47 5阅读 0赞

排序方法可以分为比较算法和非比较算法两大类。其中比较算法就有7种：  
冒泡排序 (初级) ----> 快速排序 (高级)  
选择排序 (初级) ----> 堆排序 (高级)  
插入排序 (初级) ----> 希尔排序 (高级)  
归并排序 (高级)  
这里只介绍一种非比较排序：桶排序。  
8种排序算法中快速排序、堆排序和归并排序这三种算法位列“十大算法”，可见排序算法的重要性。

如果有一个数组arr = \{4, 1, 5, 9, 7, 2, 8, 6, 4, 3\}。希望把它按照从小到大排序，我们该怎么做呢？当然是排序喽。我们在学C语言的时候已经学过最简单，但是效率也是最低的冒泡排序了。这里就不再赘述。我们就稍稍讨论一下冒泡排序的问题：  
冒泡排序就是一个数据跟相邻的数据进行比较，如果次序不符合要求，那就交换一下，然后继续往下交换，直到一轮循环结束。这样一轮下来，只能保证一个数据到达最底部。接下去进行第二轮、第三轮。。。一共需要n轮，整个排序结束。所以时间复杂度为O(N2)。  
冒泡排序的问题是只有相邻的两个元素之间才能进行比较，这样就比较慢了。如果让整个数组中的任意两个元素都能相互比较大小，是不是就能加速呢？我们来看看快速排序吧。

## 1 快速排序 ##

快速排序的思想是让一个元素作为基准，然后虫虫 (i) 和东东 (j) 帮忙找到基准的家，接着交换基准元素与占据他家的元素。这时基准元素就找到了家。最后把基准元素的左边部分用同样的方法继续排序，右边部分也用同样排序，直到整个数组中的元素变得有序。这个方法比较厉害的是把数组分成三部分：左边部分、中间正确摆放的一个元素、右边部分。  
我们可以让任意一个元素都放到它正确的位置，简单起见，我们就取最左边的元素作为基准。问题来了，我们怎么知道这个元素的家在哪呢？这就是快速排序最奥妙的地方了。如果我们能让比基准小的元素都放在左边，比基准大的元素都放在右边，那么中间的位置就是这个基准该在的位置。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]  
具体来说，如果虫虫在数组最左边，东东在数组最右边 (初始状态)。东东是弟弟，所以虫虫让弟弟先开始往左走，如果遇到 >= 基准的元素就继续走，遇到 < 基准的元素就停下来；接着是虫虫开始往右走，如果遇到 <= 基准的元素就继续走，遇到 > 基准的元素就停下来。如果两个小朋友都停下来的时候他们还没有相遇，那就交换这两个小朋友所在的元素。接着继续东东往左走，虫虫往右走。一直到两兄弟相遇。这个相遇的地方就是基准的家啦。把占据了基准家的元素跟最左边的元素交换一下位置，基准就到家了。  
上面的过程就把一个数组分成了三段。左边一段和右边一段分别用同样的方法继续就可以了。中间那个元素因为已经找到正确的位置了，它就不需要动了。下面我们就来看看虫虫和东东帮基准找家的代码：

int num = arr[low]; //取最左边的元素作为基准 
    int i = low; //虫虫在最左边 
    int j = high; //东东在最右边 
    
    while(i < j) //虫虫和东东没有相遇的时候继续走 
    {
        
    	//虫虫是哥哥，要让着弟弟，所以每次都是东东先走。 
    	while(i < j && num <= arr[j]) //没有相遇，且右边的元素比基准大 
    	{
        
    		j--; //东东往左走一步 
    	}
    	while(i < j && num >= arr[i]) //没有相遇，且左边的元素比基准大
    	{
        
    		i++; //虫虫往右走一步
    	}
    	
    	if(i < j) //两个小朋友都停止的时候，如果他们还没有相遇 
    	{
        
    		swap(i, j); //还没有找到家，两个元素交换一下。虫虫和东东没有交换哦 
    	}
    }
    
    //i==j时，虫虫和东东找到基准元素的家了，位置就是i 
    //交换一下基准和家里的元素，也就是让基准元素回家 
    swap(low, i);

这里解释一下为什么一定要让东东 (j) 先走？例如要对3、1、4这几个数字进行排序。如果让东东先走 (正确的结果)，东东会在1的位置停下，然后虫虫也会在这个位置停下，接着3和1交换，3就到了正确的位置。但是如果让虫虫先走，那么虫虫会在元素4的位置停下，然后东东也就会在这个位置停下。最后3和4进行交换，4就在3的左边 (错误)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]  
既然虫虫和东东能帮一个元素找到家，自然也能用同样的方法帮其它所有元素找到家。看到“同样的方法”这几个字，我们的第一反应就是用递归。既然是递归，一定要记得递归的几个要素：1、递归的出口；2、递归函数的等价关系式。  
下面就是快速排序的代码。三个参数分别是：待排序的数组，待排序的最左边，最右边下标

void quickSort(int arr[], int low, int high)
    {
        
    	if(low > high) //递归的出口 
    	{
        
    		return;
    	}
    	
    	int num = arr[low]; //取最左边的元素作为基准 
    	int i = low; //虫虫在最左边 
    	int j = high; //东东在最右边 
    	
    	while(i < j) //虫虫和东东没有相遇的时候继续走 
    	{
        
    		//虫虫是哥哥，要让着弟弟，所以每次都是东东先走。 
    		while(i < j && num <= arr[j]) //没有相遇，且右边的元素比基准大 
    		{
        
    			j--; //东东往左走一步 
    		}
    		while(i < j && num >= arr[i]) //没有相遇，且左边的元素比基准大
    		{
        
    			i++; //虫虫往右走一步
    		}
    		
    		if(i < j) //两个小朋友都停止的时候，如果他们还没有相遇 
    		{
        
    			swap(i, j); //说明还没有到家，两个元素交换一下。虫虫和东东没有交换哦 
    		}
    	}
    	
    	//i==j时，虫虫和东东帮基准元素找到家了 
    	//交换一下基准和家里的元素，也就是让基准元素回家，把家里的元素放到最前面 
    	swap(low, i);  
    	
    	//递归函数的等价关系式：用同样的方法帮左边和右边的两段数据排序
    	quickSort(arr, low, i - 1); //左边一段数组继续递归排序 
    	quickSort(arr, i + 1, high); //右边一段数组继续递归排序
    }

下面我们看一下完整的快速排序的代码：

#include <stdio.h>
    #include <stdlib.h>
    
    int size = 9; //数组一共9个元素 
    int arr [] = {
        3, 1, 4, 5, 6, 2, 7, 8, 9}; //等待排序的数组 
    
    void swap(int i, int j)
    {
        
    	int temp = arr[i];
    	arr[i] = arr[j];
    	arr[j] = temp;
    }
    
    //三个参数：待排序的数组，待排序的最左边，最右边下标
    void quickSort(int arr[], int low, int high)
    {
        
    	//同上
    }
    
    int main()
    {
        
    	quickSort(arr, 0, size - 1); //快速排序。n个元素，最右边的下标是n - 1 	
    	return 0;
    }

这就是最基本的快速排序算法了。如果数组有N个元素，帮助基准元素找家的时间复杂度为O(N)，找到家之后，数组被分为三部分。左边一部分可以近似看作有N / 2个元素，中间只有一个元素，右边也可以看作有N / 2个元素，再次找家的时间复杂度为O(N / 2)。就这样每次的数据规模减少一半，所以为一个元素找家的平均时间复杂度为 O(log N)。一共有N个元素，所以快速排序的时间复杂度为O(N \* logN)。由于快速排序采用递归，递归树一共logN层，所以占用的空间复杂度为O(logN)。这是平均的情况下的时间复杂度和空间复杂度，还没有考虑多种可能降低排序效率的情况。

下一节，我们将解决排序效率降低的问题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70]: /images/20230209/f6c4094f2e4d470c9ef48944fd561035.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdlaWwwMDc_size_16_color_FFFFFF_t_70 1]: /images/20230209/5dbcc9e6d11f4ddb8b14870258a6fc99.png