首页 > 代码库 > 面试指南 - 请实现一个快速排序算法
面试指南 - 请实现一个快速排序算法
快速排序算法是诸多排序算法中性能较优的一种，也是很多内建排序类型所采用的算法。该算法在.NET面试和笔试中经常被考查到，下面将详细介绍快速排序的算法思想及代码示例。
所涉及的知识点：
- 使用C#实现快速排序算法
分析问题：
快速排序算法是公认的最为优秀的内部排序算法之一，其实实现思想很简单，并且在一般情况下性能较高。下面是该算法的基本思想：
- 假设待排序的序列为L[m...n]，其中L[m...midlle-1]中的每个元素都小于L[midlle]，而L[midlle+1...n]中的每个元素都大于L[midlle]。
- 递归调用快速排序算法，对L[m...midlle-1]和L[midlle+1...n]分别进行排序。
- 由于是原地排序，所以递归结束后自然形成了有序序列。
下列代码给出了快速排序的一个实现示例：
1 using System; 2 3 namespace Guying.Demo.ConsoleApp 4 { 5 class QuickSort 6 { 7 static void Main(string[] args) 8 { 9 int[] data = http://www.mamicode.com/new int[] { 1, 1, 4, 3, 6, 7, 4, 5, 0, 0 }; // 建立测试数组10 Run(data, 0, data.Length - 1); // 进行快速排序11 for (int i = 0; i < data.Length; i++)12 Console.Write("{0}, ", data[i]);13 Console.Read();14 }15 16 /// <summary>17 /// 快速排序算法18 /// </summary>19 /// <param name="data">排序数组</param>20 /// <param name="low">排序下限</param>21 /// <param name="high">排序上限</param>22 static void Run(int[] data, int low, int high)23 {24 /**25 * 简单设定中间值，并以此为一趟快速排序的分割点26 * 注意这里是一个简单的算法27 * 如果想对这个算法进行优化的话，可以采取随机的方法来获取分割点28 * */29 int middle = data[(low + high) / 2];30 31 int i = low, j = high; // 设定移动上下标32 33 // 直至分割出两个序列34 do35 {36 // 扫描中值左边元素37 while (data[i] < middle && i < high) i++;38 // 扫描中值右边元素39 while (data[j] > middle && j > low) j--;40 // 找到了一对可交换的值41 if (i <= j)42 {43 // 交换44 int temp = data[i];45 data[i] = data[j];46 data[j] = temp;47 i++;48 j--;49 }50 } while (i <= j);51 // 递归对比分割点元素都小的那个序列进行快速排序52 if (j > low) Run(data, low, j);53 // 递归对比分割点元素都大的那个序列进行快速排序54 if (i < high) Run(data, i, high);55 }56 }57 }
编译并执行上述代码，可以得到如下结果：
说明：
快速排序算法在最坏的情况下运行时间为O(n2)，平均运行时间为O(nlgn)。快速排序的对象都读入内存中，所以输入内部输入内部排序。
快速排序基于比较关键字来确定元素的位置，所以它属于比较排序。同时，快速排序具有原地排序特性和不稳定特性，这意味着快速排序不需要额外的排序空间，但是不能确保相等的元素位置不被交换。
答案：
快速排序是最为高效的内部排序算法之一，其基本思想在于把排序对象分割为两列子序列，而其中一个子序列的值都大于另一个子序列的值，并且进一步递归排序所有子序列。
《.NET程序员面试真题》学习笔记
面试指南 - 请实现一个快速排序算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。