a=13
tab1={}
for i=1, a do
tab1[i]=math.random(100)
end
function fuc(tab,left,right)
i=left
j=right
x=tab1[left]
while(i<j) do
while(i<j) do
if(tab1[j]<x)then
tab1[i]=tab1[j]
break
else
j=j-1
end
end
while(i<j) do
if(tab1[i]>x)then
tab1[j]=tab1[i]
break
else
i=i+1
end
end
tab1[i]=x
fuc(tab1,left,i-1)
fuc(tab1,i+1,right)
end
end
fuc(tab1,1,a)
for k,v in pairs(tab1) do
print(k.." "..v)
end
这个是用lua实现的快速排序
有一个问题 在a=13以下的排序都是ok的
但是a=13以上的排序就会有问题 这是为什么呢..
同学你好,老师看是没有问题的, 也没有加任何条件,同学可以换一种写法试试:
https://blog.csdn.net/qq_35158695/article/details/54849965
Trigger老师 经过反复排查 找到了问题 写在这里就当记录吧.
1 fuc里面的参数是tab 而上面我全部协程了tab1 并没有用fuc的参数 而是直接调用了tab1表
2 上面递归调用的位置错了 不应该在while里面调用 而是应该在while结束之后在进行调用
3 判断条件有问题 应该再加一个执行这个方法的判断条件 那就是让left>=right
下面贴一下正确代码lua
a=20
tab1={}
for i=1, a do
tab1[i]=math.random(100)
end
for k,v in pairs(tab1) do
print(" "..v)
end
function fuc(tab,left,right)
if(left>=right)
then
return
end
i=left
j=right
x=tab[left]
while(i<j) do
while(i<j) do
if(tab[j]<=x)then
tab[i]=tab[j]
print(tab[j].."~~")
break
else
j=j-1
end
end
while(i<j) do
if(tab[i]>x)then
tab[j]=tab[i]
print(tab[i].."~~")
break
else
i=i+1
end
end
end
tab[i]=x
fuc(tab,left,i-1)
fuc(tab,i+1,right)
end
fuc(tab1,1,a)
for k,v in pairs(tab1) do
print(k.." "..v)
end
C#带注释代码
namespace _006_快速排序
{
class Program
{
//快速排序需要传入三个参数:数组本身,左边的第一个索引,右边的最后一个索引
//这个方法不需要返回值,因为他就是直接改变了这个数组本身,而并不是返回一个改变了的数组.
static void QuickSort(int[] dataArray, int left, int right)
{
///开始排序的时候,以左边的第一个数为基数.
/// 从右往左开始遍历,如果有一个数小于这个基数,那么这个数就放在原来基数的位置.
if (left < right)//如果左下标小于右下标就进行下面的循环.
{
int x = dataArray[left];//设置左边第一个数为基数
int i = left;//左边的第一个位置为开始的位置.
int j = right;//右边的第一个数为结束的位置.
while (true && i < j)
{
while (true && i < j)
{
if (dataArray[j] <= x)//当右边的一个数小于x的时候,把他放入基数的左边的坑里
{
dataArray[i] = dataArray[j];
break;
}
else
{
j--;//让j向左移动一个位置
}
}
while (true && i < j)
{
if (dataArray[i] > x)//然后再从左开始往右.如果有一个数大于基数,让他放在基数的右边
{
dataArray[j] = dataArray[i];
break;
}
else
{
i++;//i向右移动一个位置
}
}
}
dataArray[i] = x;//运行完上面的一个循环,那么这个基数的左边一定小于基数,基数的右边一定大于基数.而且这个时候i=j所以这个数的位置就能确定下来了.
//确定下来中间的基数之后,现在右分成了2个小数组.
QuickSort(dataArray, left, i - 1);//左边的数组是以左边第一个位置开头,以i-1结尾.
QuickSort(dataArray, i + 1, right);//右边的数组是以i+1开头,以right结尾.
//不停的执行这个方法,当这个方法里面的left不小于right的时候就不会接着调用这个函数了.那么也就执行完了.
}
}
static void Main(string[] args)
{
int[] dataArray = new[] { 42, 20, 17, 27, 13, 8, 17, 48 };
QuickSort(dataArray,0,dataArray.Length-1);
foreach (int i in dataArray)
{
Console.Write(i + " ");
}
Console.ReadKey();
}
}
}