java - 递归排序:快速排序语法
问题描述
程序应该使用快速排序对一组数字进行排序。使用从 10,000,000 个随机生成的数字开始的数据集。我一直在学习快速排序。另一个,我完成了归并排序。但是,快速排序是语法。我不知道为什么它是语法。
public static void main(String[] args)throws Exception{
for(int n = 1; n<=100; n++)
{// begin for
int size = 10000000; //change this num to change the size of the random array 10,000,000
int[] a = new int[size];
int[] temp = new int[a.length]; //temporary array, it's empty.
//fill the array with random integers
for(int i = 0; i< a.length; i++)
a[i] = (int)(Math.random()*100000 + 1);
long startTime = System.nanoTime();
quickSort(a, temp, 0,(a.length - 1));
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.printf("%12.8f %n", (double)duration/100000000);
}// End for
}// end main
public static void quickSort(int[] a, int[] temp, int startIndex, int endIndex)
{// begin quickSort
int pivotIndex; //the index of pivot returned by the quciksort partition
if(startIndex < endIndex)
{//Begin if
pivotIndex = partition(a, temp, startIndex, endIndex);
quickSort(a, temp, startIndex, pivotIndex -1);
quickSort(a, temp, pivotIndex+1, endIndex);
}//End if
}//end quickSort
public static int partition(int[] a, int[] temp, int startIndex, int endIndex) {
int pivotIndex;
int pivot;
int midIndex = startIndex;
pivotIndex = (startIndex + endIndex) / 2;
pivot = a[pivotIndex];
swap(a, temp, pivotIndex, endIndex);
for (int i = startIndex; i < endIndex; i++) {
if (a[i] < pivot) ;
{
swap(a, temp, i, midIndex);
midIndex = midIndex + 1;
}
}
swap(a, temp, midIndex, endIndex);
return midIndex;
}// end partition
public static void swap(int[]a, int[]temp, int first, int second)
{//Begin swap
for(int i = first; i <= second; i++){
temp[i] = a[i];
}
int c;
c = a[first];
a[first] = a[second];
a[second] = c;
}//End swap
public static void writeLines(int[] a, String fileName) throws Exception
{ // Begin writeLines(int[] a, String fileName)
// create a File class object with the given file name
java.io.File out = new java.io.File(fileName);
// Create a PrintWriter output stream and link it to the File object
java.io.PrintWriter outfile = new java.io.PrintWriter(out);
// write the elements of an int array, separated by spaces
for (int i = 0; i < a.length; i++)
{ // Begin for (int i = 0; i < a.length; i++)
outfile.print(a[i] + " ");
} // End for (int i = 0; i < a.length; i++)
// print a newline at the end of the list of integers
outfile.println();
outfile.close();
} // End writeLines(int[] a, String fileName) throws Exception
}//end quickSORT
我有语法。它说的是 quick.partition 和 quick.quickSort。
解决方案
简单来说,Hoare 的快速排序通过以下方式工作:
- 有一个数据数组
- 挑选一些中间元素
- 在逻辑上将数组分为 3 类:
- 中间元素左侧的所有内容 - 我们将其称为下部
- 中间元素
- 中间元素右侧的所有内容 - 我们将其称为上部
- 记住中间元素的值
- 从下部的最左边开始寻找大于中间元素的值,或者换句话说,它试图找到不应该在下部的东西,因为它太大了
- 当它找到一个时,它会从上半部分的右侧开始寻找一个“对于上半部分来说太小”的元素
- 如果找到满足这些条件的值,则交换它们
- 这种情况反复发生,直到对于下部来说太大的所有东西都被转移到上部,而对于上部来说太小的所有东西都被转移到下部
- 结果是一个“部分排序”的数组;中间元素左边的一切都比它小,中间元素右边的一切都比它大
- 算法重新开始,这次只将下半部分视为整个数组,然后对上半部分执行相同操作
- 通过取整体,然后将其减半,然后将其四等分,然后......您达到了一个点,您只需确保对一堆对或单个元素进行排序,然后就完成了
您的算法使用了类似于 Hoare 和 Lomuto 分区策略的组合,但更像是 Lomuto。有多种分区策略(选择如何将数组划分为部分)取决于数据容器的工作方式(Hoare 的策略要求容器可以随机访问或从每一端访问,如双链表,Lomuto 只需要一个可以在一个方向上读取的数据容器)但是快速排序的基本算法是这样一种概念,即您将所有内容分成两堆“想要更小的值”和“想要更大的值”,在两堆之间反复交换东西直到“更小”和“更大” " 真的是这样,然后再对较小的一堆,然后对较大的一堆再次执行该过程。
如果你还在纠结,不妨考虑一下:如果你认为它就像将大量只使用字符 A 和 Z 的单词按字母顺序排序,你可能会有一种将所有东西堆成一堆的策略:2 堆以 A 开头的那些和以 Z 开头的那些。然后你做 4 堆,那些以 AA、AZ、ZA 和 ZZ 开头的堆。然后你移动到 8 堆三个字母 AAA、AAZ、AZA、AZZ、ZAA、ZAZ、ZZA 和 ZZZ(如果你现在睡着了,这可能是合适的)。这也是一种“分而治之的策略”;你会达到一个程度,你已经把一堆堆分开了,以至于它们每个只包含一个东西,然后如果你按顺序收集一堆堆(如果你在布置它们时小心翼翼,它们已经是有序的了) 然后它们被排序
哦,您的代码有一个错误,因为您在 if 之后添加了一个分号,这会创建一个空语句(使 if 无用),而且您似乎也没有使用随身携带的 temp 数组。就像这个算法希望混合两种不同的排序策略但未完成
推荐阅读
- c# - Xamarin.Forms - DatePicker 复制
- c++ - 如何遍历文本文件中的行并将其与其他行进行比较(C++)
- ruby-on-rails - 尝试在 Rails 上实现搜索功能时获取“表单中的第一个参数不能包含 nil 或为空”
- java - 我不能使用正则表达式替换包含“\”字符的文本
- sql - 左连接不返回任何行
- javascript - 如何在已设置命令处理程序的 discord.js 上使用参数
- python - 如何切片直到最后一项以形成新列?
- python - TensorFlow:将图像导入张量流模型
- c++ - C++ 堆栈帧/激活记录和“this”指针
- scala - 具有值类字段的实体的 Doobie 查询