【算法改进要点 】 在上节讨论的冒泡排序中，由于扫描过程中只对相邻的两个元素进行比较，
因此在互换两个相邻元素时只能消除一个逆序。如果能通过两个（不相邻的）元素的交换，
消除待排序记录中的多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能
消除多个逆序。
【 算法思想 】 从待排序记录序列中选取一个记录（通常选取第一个记录）为枢轴，其关键字
设为 K 1 ，然后将其余关键字小于 K 1 的记录移到前面，而将关键字大于 K 1 的记录移到后面，
结果将待排序记录序列分成两个子表，最后将关键字为 K 1 的记录插到其分界线的位置处。
将这个过程称作 一趟快速排序。通过一次划分后，就以关键字为 K 1 的记录为界，将待排序
序列分成了两个子表，且前面子表中所有记录的关键字均不大于 K 1 ，而后面子表中的所有
记录的关键字均不小于 K 1 。对分割后的子表继续按上述原则进行分割，直到所有子表的表
长不超过 1 为止，此时待排序记录序列就变成了一个有序表。
【算法步骤】
假设待划分序列为 r[left]， r[left+1]， … ，r[right]，具体实现上述划分过程时，可以设两个指针 i 和 j，它们的初值分别为 left 和 right。首先将基准记录 r[left]移至变量 x 中，使r[left]，即 r[i]相当于空单元，然后反复进行如下两个扫描过程，直到 i 和 j 相遇：
⑴ j 从右向左扫描，直到 r[j].key < x.key 时，将 r[j]移至空单元 r[i]，此时 r[j]相当于空单元。
⑵ i 从左向右扫描，直到 r[i].key > x.key 时，将 r[i]移至空单元 r[j]，此时 r[i]相当于空单元。
当 i 和 j 相遇时， r[i]（或 r[j]）相当于空单元，且 r[i]左边所有记录的关键字均不大于基准记录的关键字，而 r[i]右边所有记录的关键字均不小于基准记录的关键字。最后将基准记录移至 r[i]中，就完成了一次划分过程。对于 r[i]左边的子表和 r[i]右边的子表可采用同样的方法进行进一步划分。
C#实现：
快速排序：递归调用（挖坑法）
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 交类排序
/// </summary>
public class ChangeSort
{
/// <summary>
/// 快排：（递归）挖坑法
/// </summary>
/// <param name="a"></param>
/// <param name="startIndex"></param>
/// <param name="endIndex"></param>
public static void QuickSort_1(int[] a, int startIndex, int endIndex)
{
if (startIndex >= endIndex)
{
return;
}
int pivotIndex = GetPivotIndex(a, startIndex, endIndex);
QuickSort_1(a, startIndex, pivotIndex - 1);
QuickSort_1(a, pivotIndex + 1, endIndex);
}
/// <summary>
/// 获得基准的位置:（填坑法）方法1
/// </summary>
/// <param name="a"></param>
/// <param name="startIndex"></param>
/// <param name="endIndex"></param>
/// <returns></returns>
public static int GetPivotIndex(int[] a, int startIndex, int endIndex)
{
int pivot = a[startIndex]; //取第一个元素为基准数
int left = startIndex;
int right = endIndex;
int index = startIndex;//挖坑法：坑的位置
while (left <= right)
{
//right 指针从右向左进行比较
while (left <= right)
{
if (a[right] < pivot)
{
a[left] = a[right];
index = right;
left++;
break;
}
right--;
}
//left 指针从左向右进行比较
while (left <= right)
{
if (a[left] > pivot)
{
a[right] = a[left];
index = left;
right--;
break;
}
left++;
}
}
a[index] = pivot;
return index;
}
}
快速排序：非递归（使用栈消除递归）
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
/// <summary>
/// 交类排序
/// </summary>
public class ChangeSort
{
/// <summary>
/// 快速排序：（非递归）用栈消除递归
/// </summary>
/// <param name="a"></param>
/// <param name="startIndex"></param>
/// <param name="endIndex"></param>
public static void QuickSort_2(int[] a, int startIndex, int endIndex)
{
if (startIndex >= endIndex)
{
return;
}
Stack<Dictionary<string, int>> quickSortStack = new Stack<Dictionary<string, int>>();
Dictionary<string, int> rootParam = new Dictionary<string, int>();
rootParam.Add("startIndex", startIndex);
rootParam.Add("endIndex", endIndex);
quickSortStack.Push(rootParam);
while(quickSortStack.Count!=0)
{
Dictionary<string, int> param = quickSortStack.Pop();
int pivotIndex = GetPivotIndex_2(a, param["startIndex"], param["endIndex"]);
if(param["startIndex"]<pivotIndex-1)
{
Dictionary<string, int> leftParam = new Dictionary<string, int>();
leftParam.Add("startIndex", param["startIndex"]);
leftParam.Add("endIndex", pivotIndex - 1);
quickSortStack.Push(leftParam);
}
if (pivotIndex+1 < param["endIndex"])
{
Dictionary<string, int> rightParam = new Dictionary<string, int>();
rightParam.Add("startIndex", pivotIndex + 1);
rightParam.Add("endIndex", param["endIndex"]);
quickSortStack.Push(rightParam);
}
}
}
/// <summary>
/// 获得基准的位置:（指针法）方法2
/// </summary>
/// <param name="a"></param>
/// <param name="startIndex"></param>
/// <param name="endIndex"></param>
/// <returns></returns>
public static int GetPivotIndex_2(int[] a, int startIndex, int endIndex)
{
int pivot = a[startIndex]; //取第一个元素为基准数
int left = startIndex;
int right = endIndex;
while (left < right)
{
while (left < right && a[right] >= pivot)
{
right--;
}
if (left < right)
{
a[left] = a[right];
left++;
}
while (left < right && a[left] < pivot)
{
left++;
}
if (left < right)
{
a[right] = a[left];
right--;
}
}
a[left] = pivot;
return left;
}
}
测试用例;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class _014_ChangeSort : MonoBehaviour
{
void Start()
{
int[] a = Utilit.RandArray(20, 10);//new int[] { 4,3,2,1,0,5,6,7,8,9};
int[] b = (int[])a.Clone();
Debug.Log("---------------快速排序:挖坑法--------------");
ChangeSort.QuickSort_1(a, 0, a.Length - 1);
Utilit.Print(a, 0);
Debug.Log("---------------快速排序:非递归--------------");
ChangeSort.QuickSort_2(b, 0, a.Length - 1);
Utilit.Print(b, 0);
}
}
测试结果：
![]()
img.jpg
img.jpg
交换类排序总结：
img.jpg
image.png
