算法描述
1.假定数组首位元素为“枢轴”,设定数列首位(begin)与末位(end)索引;
2.由末位索引对应元素与“枢轴”进行比较,如果末位索引对应元素大于“枢轴”元素,对末位索引减一(end--),直到比较出大于“枢轴”元素,将该元素覆盖到首位,对应索引上的数值空出;
3.由首位索引对应元素与“枢轴”进行比较,如果首位索引对应元素小于“枢轴”元素,对首位索引加一(begin++);直到比较出小于“枢轴”元素,将该元素覆盖到步骤2中空出位置,同时对应索引上的数值空出;
4.重复步骤2与步骤3,直到begin==end结束循环,这时候begin与end已指向同一位置,将“枢轴”元素覆盖到该位置;
5.这时候该位置前面元素都小于“枢轴”元素,该位置后面元素都大于“枢轴”元素,第一轮循环结束,对前后两部分执行相同步骤,通过“递归”最终将数组中数值完成排序;
代码实现
public int[] Quick(int[] arr, int begin, int end) // 通过自我调用实现“递归”
{
if (begin >= end) {
return arr; }
int pivotIndex = QuickCondition(arr, begin, end); // 获得“枢轴”索引
Quick(arr, begin, pivotIndex - 1); // 对所有小于“枢轴”元素再次比较
Quick(arr, pivotIndex + 1, end);// 对所有大于“枢轴”元素再次比较
return arr; }
public int QuickCondition(int[] arr, int begin, int end) {
int pivot = arr[begin]; // 设定首位为“枢轴”元素
while (begin < end) {
while (arr[end] > pivot && begin < end) // 通过比较找到小于“枢轴”元素的索引,进行替换
{ end--; } arr[begin] = arr[end];
while (arr[begin] < pivot && begin < end) // 通过比较找到第大于“枢轴”元素的索引,进行替换
{ begin++; } arr[end] = arr[begin]; } arr[begin] = pivot; // 当begin == end 跳出循环将“枢轴”覆盖到该索引上
return begin; }
完整代码
using System;
namespace QuickSortApplication {
class Program {
static void Main(string[] args) {
var setArray = new SetArray();
var quickSort = new QuickSort();
int[] arr = setArray.GetArray();
int[] array = quickSort.Quick(arr, 0, arr.Length - 1); quickSort.DisPlay(array); Console.ReadLine(); } }
class SetArray {
public int[] GetArray() {
int length;
int[] arr; Console.WriteLine("请输入数组长度:"); length = Convert.ToInt32(Console.ReadLine()); arr = new int[length]; for (int i = 0; i <= length - 1; i++) { Console.Write("请输入数组第{0}位数值:", i); arr[i] = Convert.ToInt32(Console.ReadLine()); } Console.Clear(); Console.Write("arr[] = {"); foreach (int item in arr) { Console.Write(item + " "); } Console.Write("}\n"); return arr; } }
class QuickSort {
public int[] Quick(int[] arr, int begin, int end) // 通过自我调用实现“递归”
{
if (begin >= end) {
return arr; }
int pivotIndex = QuickCondition(arr, begin, end); // 获得“枢轴”索引
Quick(arr, begin, pivotIndex - 1); // 对所有小于“枢轴”元素再次比较
Quick(arr, pivotIndex + 1, end);// 对所有大于“枢轴”元素再次比较
return arr; }
public int QuickCondition(int[] arr, int begin, int end) {
int pivot = arr[begin]; // 设定首位为“枢轴”元素
while (begin < end) {
while (arr[end] > pivot && begin < end) // 通过比较找到小于“枢轴”元素的索引,进行替换
{ end--; } arr[begin] = arr[end];
while (arr[begin] < pivot && begin < end) // 通过比较找到第大于“枢轴”元素的索引,进行替换
{ begin++; } arr[end] = arr[begin]; } arr[begin] = pivot; // 当begin == end 跳出循环将“枢轴”覆盖到该索引上
return begin; }
public void DisPlay(int[] arr) { Console.Write("快速排序:"); foreach (int item in arr) { Console.Write(item + " "); } Console.WriteLine(); } } }