一、快速排序
【分治法】快速排序在每一轮挑选一个基准元素，并让其他比他大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解为两个部分。
【基元素选择】①最简单的方式是选择数列的第一个元素，但是在极端情况下快速排序需要进行n轮，时间复杂度为【】
②为避免极端情况发生，可以随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。
二、快速排序步骤
①选定了基元素后，就把其他元素中小于基元素的都交换到基元素一边，大于基元素的都交换到基元素的另一边。
②双边循环法：《1》选定基元素后，并且设置两个索引left和right，指向数列的最左和最右两个元素。
《2》接下来进行第一次循环，从right索引开始，让索引指向的元素和基元素做比较，如果>=基元素，则索引左移动；如果索引<基元素，则right索引停止移动；切换到Left索引移动。
《3》当left索引移动时，让left索引指向的元素和基元素作比较，如果<=基元素，则left索引右移动，如果>基元素，则停止left移动，切换为right索引移动。
《4》如此反复。
③单边循环法：《1》只从数组的一边对元素进行遍历和交换
《2》如果遍历到的元素>基元素，则继续往后遍历
《3》如果遍历到的元素<基元素，则把数组第一个索引指定为mark，然后把mark索引右移动1位，因为<基元素的区域边界增大了1；然后把最新遍历到的元素和mark索引所在的位置的元素交换位置，因为最新遍历的元素归属小于基元素区域。
三、快速排序核心
/***
* Title: "算法" 项目
* 主题 : 快速排序
* Description:
* 功能 :
* Date: 2020-07-04
* Version: 1.2
* Author: Coffee
* Modify Recoder:
*/
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Kernal
{
class QuickSort
{
/// <summary>
/// 分治（双边循环法）
/// </summary>
/// <param name="array">待交换数组</param>
/// <param name="startIndex">起始下标</param>
/// <param name="endIndex">结束下标</param>
/// <returns></returns>
public static void DoubleLoop(int[] array, int startIndex, int endIndex)
{
//递归结束条件
if (startIndex >= endIndex)
{
return;
}
//得到基准元素位置
int pivotIndex = ParitionDouble(array, startIndex, endIndex);
//根据基准元素，分成两部分进行递归排序
DoubleLoop(array, startIndex, pivotIndex - 1);
DoubleLoop(array, pivotIndex + 1, endIndex);
}
/// <summary>
/// 分治（单边循环法）
/// </summary>
/// <param name="array">待交换数组</param>
/// <param name="startIndex">起始下标</param>
/// <param name="endIndex">结束下标</param>
/// <returns></returns>
public static void SingleLoop(int[] array, int startIndex, int endIndex)
{
//递归结束条件
if (startIndex>=endIndex)
{
return;
}
//得到基准元素
int pivotIndex = ParitionSingle(array, startIndex, endIndex);
//根据基准元素，分成两部分进行递归排序
SingleLoop(array,startIndex,pivotIndex-1);
SingleLoop(array,pivotIndex+1,endIndex);
}
/// <summary>
/// 分治（双边循环法）
/// </summary>
/// <param name="array">待交换数组</param>
/// <param name="startIndex">起始下标</param>
/// <param name="endIndex">结束下标</param>
/// <returns></returns>
private static int ParitionDouble(int[] array,int startIndex,int endIndex)
{
//取第1个位置（也可以选择随机位置）的元素作为基准元素
int pivot = array[startIndex];
int left = startIndex;
int right = endIndex;
while (left!=right)
{
//控制right索引比较并左移
while (left<right && array[right]>pivot)
{
right--;
}
//控制left索引比较并右移
while (left<right && array[left]<=pivot)
{
left++;
}
//交换left和right索引所指向的元素
if (left<right)
{
int tmp = array[left];
array[left] = array[right];
array[right] = tmp;
}
}
//pivot和索引重合点交换
array[startIndex] = array[left];
array[left]=pivot;
return left;
}
/// <summary>
/// 分治（单边循环法）
/// </summary>
/// <param name="array">待交换数组</param>
/// <param name="startIndex">起始下标</param>
/// <param name="endIndex">结束下标</param>
/// <returns></returns>
private static int ParitionSingle(int[] array, int startIndex, int endIndex)
{
//取第1个位置（也可以选择随机位置）的元素作为基准元素
int pivot = array[startIndex];
int mark = startIndex;
for (int i = startIndex+1; i <= endIndex; i++)
{
if (array[i]<pivot)
{
mark++;
int tmp = array[mark];
array[mark] = array[i];
array[i] = tmp;
}
}
array[startIndex] = array[mark];
array[mark] = pivot;
return mark;
}
}//Class_end
}
四、使用方法
①、引用命名空间：using Kernal;
②、QuickSort+方法名称；
③、在方法中传入列表即可。
五、示例
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using Kernal;
namespace CommonSort
{
class Program
{
static void Main(string[] args)
{
//时间计时器
Stopwatch _SW = new Stopwatch();
Console.WriteLine("原数组为：");
int[] array = {69, 25, 78, 1, 56, 24, 98, 71, 2, 6, 1, 5, 8, 9};
int[] array2 = { 69, 25, 78, 1, 56, 24, 98, 71, 2, 6, 1, 5, 8, 9 };
Display(array);
Console.WriteLine("\n--------------- 分治（双边循环法）----------------------");
_SW.Start();
Console.WriteLine(" 分治（双边循环法）为：");
QuickSort.DoubleLoop(array,0,array.Length-1);
Display(array);
_SW.Stop();
Console.WriteLine("花费时间为：{0} 毫秒",_SW.Elapsed.TotalMilliseconds);
Console.WriteLine("\n--------------- 分治（单边边循环法）----------------------");
_SW.Restart();
Console.WriteLine(" 分治（单边边循环法）为：");
QuickSort.SingleLoop(array2, 0, array2.Length - 1);
Display(array2);
_SW.Stop();
Console.WriteLine("花费时间为：{0} 毫秒", _SW.Elapsed.TotalMilliseconds);
Console.Read();
}//Main_end
//显示结果
private static void Display(int[] array)
{
string str = null;
foreach (var item in array)
{
str += item + " ";
}
Console.WriteLine(str);
}
}//Class_end
}
六、结果如下
