属于冒泡排序的升级, 都属于交换排序类。即它也是通过不断比较和移动来实现排序的,只不过它的实现,增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,关键字较小的记录从后面直接移动到前面,从而减少了比较次数和移动交换次数。
using System;
using System.Linq;
namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
int[] sqList = new int[] { 97, 0, 5, 4, 3, 1, 5, 9, 11, 13 };
QuickSort(sqList);
sqList.ToList().ForEach(s => Console.Write(s + " "));
Console.ReadLine();
}
static void QuickSort(int[] sqList)
{
QSort(sqList, 0, sqList.Length-1);
}
static void QSort(int[] sqList, int low, int high)
{
int pivot;
if (low < high)
{
pivot = Partition(sqList, low, high);
QSort(sqList, low, pivot - 1);
QSort(sqList, pivot + 1, high);
}
}
static int Partition(int[] sqList, int low, int high)
{
int pivotkey = sqList[low];
while (low < high)
{
while (low < high && sqList[high] >= pivotkey)
{
high--;
}
Swap(sqList, low, high); //将比枢轴值小的记录交换到低端
while (low < high && sqList[low] <= pivotkey)
{
low++;
}
Swap(sqList, low, high); //将比枢轴值大的记录交换到高端
}
return low; //返回枢轴所在位置
}
static void Swap(int[] sqList, int index1, int index2)
{
int value1 = sqList[index1];
sqList[index1] = sqList[index2];
sqList[index2] = value1;
}
}
}
网友评论