C# 带有随机主元的快速排序
我正在尝试将 heapSort 算法修改为带有随机枢轴的版本,但我不知道该怎么做。
有人可以帮助我吗?
这是代码:
//QuickSort w C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort
{
class Program
{
//Zamienia miejscami , zwykły swap
static void Swap<T>(ref T lhs, ref T rhs)
{
T temp;
temp = lhs;
lhs = rhs;
rhs = temp;
}
//Procedura qiucksort
static void qsort(int[] tab, int left, int right)
{
if (left < right)
{
int m = left;
for (int i = left + 1; i <= right; i++)
if (tab[i] < tab[left])
Swap(ref tab[++m], ref tab[i]);
Swap(ref tab[left], ref tab[m]);
qsort(tab, left, m - 1);
qsort(tab, m + 1, right);
}
}
static void Main(string[] args)
{
int[] a = { 0, 12, 34, 9, 54, 12, 77, -3, -20 };
int i;
int left = 0;
int right = 8;
Console.WriteLine("Data before sort ");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
//Wywołanie procedury qsort
qsort(a, left, right);
Console.WriteLine("Data after sort");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
这是使用随机枢轴更改的代码,此代码崩溃于: Swap(ref tab[++m], ref tab[i]);
//QuickSort in C# with random pivot
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
命名空间快速排序
{
班级计划
{
//常用的Swap函数
static void Swap(ref T lhs, ref T rhs)
{
T 温度;
温度=lhs;
左轴 = 右轴;
rhs = 温度;
}
//qiucksort procedure
static void qsort(int[] tab, int left, int right)
{
if (left < right)
{
System.Random myRandom = new System.Random(); //Creating instance of random variable
int m = myRandom.Next(left, right); //pivot = random number between left a right
Swap(ref tab[left],ref tab[m]);
for (int i = left + 1; i <= right; i++)
if (tab[i] < tab[left])
Swap(ref tab[++m], ref tab[i]);
Swap(ref tab[left], ref tab[m]);
qsort(tab, left, m - 1);
qsort(tab, m + 1, right);
}
}
static void Main(string[] args)
{
Console.Title = "QuickSort";
int[] a = { 0, 12, 34, 9, 54, 12, 77, -3};
int i;
int left = 0;
int right = 7;
Console.WriteLine("Data before sort ");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
//call quicksort procedure
qsort(a, left, right);
Console.WriteLine("Data after sort");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
I am trying to modify the heapSort algorithm into version with random pivot , and I dont know what to do.
Could any one help me ?
This is the code:
//QuickSort w C#
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort
{
class Program
{
//Zamienia miejscami , zwykły swap
static void Swap<T>(ref T lhs, ref T rhs)
{
T temp;
temp = lhs;
lhs = rhs;
rhs = temp;
}
//Procedura qiucksort
static void qsort(int[] tab, int left, int right)
{
if (left < right)
{
int m = left;
for (int i = left + 1; i <= right; i++)
if (tab[i] < tab[left])
Swap(ref tab[++m], ref tab[i]);
Swap(ref tab[left], ref tab[m]);
qsort(tab, left, m - 1);
qsort(tab, m + 1, right);
}
}
static void Main(string[] args)
{
int[] a = { 0, 12, 34, 9, 54, 12, 77, -3, -20 };
int i;
int left = 0;
int right = 8;
Console.WriteLine("Data before sort ");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
//Wywołanie procedury qsort
qsort(a, left, right);
Console.WriteLine("Data after sort");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
This is changed code with random pivot , this code crashes at: Swap(ref tab[++m], ref tab[i]);
//QuickSort in C# with random pivot
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace QuickSort { class Program { //common Swap function static void Swap(ref T lhs, ref T rhs) { T temp; temp = lhs; lhs = rhs; rhs = temp; }
//qiucksort procedure
static void qsort(int[] tab, int left, int right)
{
if (left < right)
{
System.Random myRandom = new System.Random(); //Creating instance of random variable
int m = myRandom.Next(left, right); //pivot = random number between left a right
Swap(ref tab[left],ref tab[m]);
for (int i = left + 1; i <= right; i++)
if (tab[i] < tab[left])
Swap(ref tab[++m], ref tab[i]);
Swap(ref tab[left], ref tab[m]);
qsort(tab, left, m - 1);
qsort(tab, m + 1, right);
}
}
static void Main(string[] args)
{
Console.Title = "QuickSort";
int[] a = { 0, 12, 34, 9, 54, 12, 77, -3};
int i;
int left = 0;
int right = 7;
Console.WriteLine("Data before sort ");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
//call quicksort procedure
qsort(a, left, right);
Console.WriteLine("Data after sort");
for (i = 0; i < a.Length; i++)
Console.Write(" {0} ", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
您当前的枢轴是第一个元素,您可以选择它
要使用随机枢轴,首先
因为否则您将不得不更改你的分割算法(不幸的是,这是内联的)彻底。
但
随机枢轴远非理想。如果这是半严重的情况,请考虑三中位数枢轴
Your current pivot is the first element, you select it with
To use a random pivot, first
Because otherwise you would have to change your split algorithm (which is inline unfortunately) drastically.
But
A random pivot is far from ideal. If this is halfway serious, consider a median-of-three pivot