快速排序的两种实现方法(c语言版本)

首页 > 快速排序的两种实现方法(c语言版本)

快速排序的两种实现方法(c语言版本)

经过调研发现，对任意无序整数数组，快速排序有两种实现方法，这里简单阐述下思路：

思路一：随意选择一个基准元，一般选择数组的起始元或末尾元，Weiss这本书上特意搞了个算法来选择基准元，……，总之就是基准元的选择要尽量随机。选定基准元之后，比如选择数组起始元为基准元，从数组右边开始，向左边遍历，遇到比基准元大的跳过，直至遇到比基准元小的元素停下来；再从左边向右边遍历，跳过比基准元小的，直至遇到比基准元大的元素停下来，交换左右两边的元素，再重复之前的遍历，比较和交换步骤，……，这样经过一趟排序就能将整个数组划分为两个部分，左边的部分小于基准元，右边的部分大于基准元，使用“二分法”和递归的思想，我们就能最终快速完成整个数组的排序，借用网上的效果动态如下：

啊哈磊的这篇文章对快速排序的思想做了非常深入浅出的描述，感兴趣的读者可以看看

http://bbs.ahalei.com/thread-4419-1-1.html

思路二：在不方便从数组最右端向最左端遍历的情形下，比如超长单向链表只有next指针，只能往前遍历不能往后遍历，此时还有一种变通方法，就是，选择数组的首个元素为基准元，使用两个索引，一快一慢，索引1从首个元素的前一个开始(索引为-1)，索引2遍历数组每个元素，发现比基准元小的元素，就让索引1增加1，如果发现两个索引不相等，就交换两个对应两个元素的值，这样的效果等价于把数组分为两部分，比基准元大的部分在基准元的右边，比基准元小的部分在基准元的左边，同样按照“二分法”和递归思想，最后完成整个数组的排序。

下面给出这两种思路的算法实现源码

//description: 给出快速排序的两种实现形式
//date: 2019-03-16#include 
#include int RandomInRange(int min, int max){int random = rand()%(max-min+1) + min;return random;
}int swap(int* a, int* b){int tmp = *b;*b = *a;*a = tmp;
}//利用三点确定基准点
int Median3(int arr[], int left, int right){int center = (left+right)/2;//使left，center，right升序if(arr[left]>arr[center])swap(&arr[left], &arr[center]);if(arr[left]>arr[right])swap(&arr[left], &arr[right]);if(arr[center]>arr[right])swap(&arr[center], &arr[right]);//隐藏基准点swap(&arr[center], &arr[right-1]);return arr[right-1];
}int Partition(int arr[], int n, int start, int end){if(arr==NULL || n<=0 || start<0 || end >= n){printf("Invalid input params, exit ...");exit(-1);}//生成随机索引作为基准元素，并放到数组尾部int idx = RandomInRange(start, end);swap(&arr[idx], &arr[end]);//现在arr[end]就是基准元素了//设置两个索引, small表示比基准元素小的元素的索引int small = start - 1;for(idx=start; idx0 && tpivot){}if(ipivot){}if(ii+1)Qselect(arr, k, i+1, right);}else{//对子数组做插入排序InsertSort(arr+left, right-left+1);}
}void QuickSort2(int arr[], int n){Qsort(arr, 0, n-1);
}void QuickSort(int arr[], int n, int start, int end){if(start == end)return;int pivot = Partition(arr, n, start, end);if(pivot>start)QuickSort(arr, n, start, pivot-1);if(pivot

 
下面是函数运行效果截图 
 
  
引申 
使用快速排序的思想，还可以高效解决“查找第k大数”的问题，特别是“查找数组中位数”的问题，这是后话，打算今后另做一篇博文分析。 
求无序数组的中位数(c语言版本) 
  
参考文献 
[1]. Allen Weiss 《数据结构与算法分析---C语言描述》第2版第七章 
[2].何海涛 《剑指Offer名企面试官精讲典型编程题》第2版p.80


            
                
                    更多相关：
                    
                        
                    
                        剑指offer: 面试题40. 最小的k个数
                    
                    
                        
                            题目：最小的k个数 
入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
示例 1： 
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1] 
示例 2： 
输入：arr = [0,1,2,1], k = 1
输出：[0...
                            
                        
                    
				

                    
                        JS如何深度复制对象和数组，避免指针变量引用修改值
                    
                    
                        
                            //自定义深度复制对象or数组的递归方法----------------------------------------
let copyObjOrArr = o => {let isArray = o instanceof Array;let isObject = o instanceof Object;if (!isObject)...
                            
                        
                    
				

                    
                        【数组方法大合集】原生js数组array常用工具方法大合集
                    
                    
                        
                            var array = {/* 数组求和*/sum: arr => eval(arr.join("+")),/* 判断一个数组(支持一个字符串)里面的是否有任何一个元素被包含在了某个字符串里面 */isStringContain(str, arr) {Array.isArray(arr) || (arr = [arr]);for (v...
                            
                        
                    
				

                    
                        十种经典排序算法精粹(c语言版本)
                    
                    
                        
                            下面给出这段时间我苦心研究验证过的十种经典排序算法的C语言版本，即下面的排序算法： 
插入排序，shell排序，冒泡排序，快速排序，选择排序，堆排序，归并排序，桶排序，基数排序和计数排序。整理出来以作备忘，不足之处，欢迎大家批评指正！其中计数排序分别给出了不稳定和稳定两种排序算法，测试时，使用随机生成大数组和随机手动输入的方法来测试。...
                            
                        
                    
				

                    
                        java 读取excel_Java12POI操作Excel
                    
                    
                        
                                    Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...
                            
                        
                    
				

                    
                        C++ 生成随机数
                    
                    
                        
                            要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 
要取得a到b之间的...
                            
                        
                    
				

                    
                        基于C++的本征图像分解(Intrinsic Image Decomposition)
                    
                    
                        
                            利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。
Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...
                            
                        
                    
				

                    
                        剑指offer：面试题39. 数组中出现次数超过一半的数字
                    
                    
                        
                            题目：面试题39. 数组中出现次数超过一半的数字 
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 
你可以假设数组是非空的，并且给定的数组总是存在多数元素。 
示例 1: 
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2 
限制： 
1 <= 数组长度 <= 50000 

解题： 
cl...
                            
                        
                    
				

                    
                        剑指offer：面试题33. 二叉搜索树的后序遍历序列
                    
                    
                        
                            题目：二叉搜索树的后序遍历序列 
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
参考以下这颗二叉搜索树： 
     5     /     2   6   /   1   3示例 1： 
输入: [1,6,3,2,5]
输出...