一个字符串数组使用快速排序 [英] Using quicksort on a string array
问题描述
我是一个编程的学生，而不是后整个任务我就请求帮助解决什么，我已经试过了，现在时间来了解。我任务是分拣使用快速排序法的字符串数组。其他的一切我一直在负责，因为这问题的一部分是好的，但是当我通过打印字符串数组测试的排序方法，它是完全混乱的，没有任何看似莫名其妙。请帮我在我的code或几个明显的错误，我忽略查明错误。提供的字符串数组是65名这个名单： http://pastebin.com/jRrgeV1E 和方法的code低于
私有静态无效快速排序（字符串[]一，诠释开始，诠释完）
{
//指数为左到右扫描
INT I =启动;
//指数为从右到左扫描
INT J =结束; //仅检查2或更多个元件的阵列。
如果（J - I＆GT; = 1）
{
//排序方法的枢轴点被任意设置到阵列INT的第一个元素。
字符串支点= a [i];
//只有两个指标之间的扫描，直到他们满足。
而（J＆GT; I）
{
//从左侧，如果当前元素是字典顺序比小于（原始）
//字符串数组中的第一个元素，继续前进。停止推进计数器，当我们到达
//右侧或字典顺序比枢轴字符串更大的元件。
而（A [I] .compareTo（支点）℃的放大器;＆安培; I＆LT; =＆到底放;＆放大器; J＆GT;我）{
我++;
}
//从右侧，如果当前元素是字典顺序比越大（原始）
//字符串数组中的第一个元素，继续前进。停止推进计数器，当我们到达
//左边或字典顺序比枢轴字符串更少的元件。
而（A [J] .compareTo（支点）大于0和放大器;＆放大器; J＆GT; =＆开始放;＆放大器; J＆GT; = 1）{
j--;
}
//检查两个要素为中心，在扫描前的最后一个比较交叉。
如果（J I标记）
掉期（A，I，J）;
}
//此时，两次扫描已经在阵列的中心彼此交叉，并停止。
//左分区和右分区包含数字右侧组，但不
//整理自己。下面的递归code排序的左，右分区。 //与左分区的最后一个元素交换枢转点。
掉期（一，启动，J）;
//排序左分区
快速排序（A，启动，J - 1）;
//排序正确的分区
快速排序（A，J + 1，结束）;
}
}
/ **
*这个方法有利于快速排序法的需要交换两个元素，河内的风格塔。
* /
私有静态无效掉期（字符串[]一，INT I，诠释J）
{
字符串TEMP = a [i];
一个由[i] = A [J]。
一个研究[J] =温度;
}
好吧，我错了，它会工作，发现您的微小的失误。
您会发现，你在while循环条件导致错误
如果您更改（A [I] .compareTo（支点）℃的放大器;＆安培; I＆LT; =年底和放大器;＆放大器; J＆GT; I）和（A [J] .compareTo（支点）大于0和放大器;＆放大器; J＆GT; =启动＆放大器;＆放大器; J＆GT; = 1）到
（A [I] .compareTo（支点）LT; = 0＆放大器;＆安培; I＆LT;末＆放大器;＆放大器; J＆GT; I）和（A [J] .compareTo（支点）＆GT; = 0＆放大器;＆放大器; J＆GT;启动和放大器;＆放大器; J＆GT; = 1）。
I'm a programming student and rather than post the whole assignment I'll just ask for help solving what I've tried for hours now to understand. I'm tasked with sorting an array of strings using the quicksort method. Everything else I've been tasked with as part of this problem is fine but when I tested the sorting method by printing out the String Array, it's completely jumbled up without any seeming rhyme or reason. Please help me pinpoint the error in my code, or the several glaring errors I've overlooked. The array of strings provided is this list of 65 names: http://pastebin.com/jRrgeV1E and the method's code is below:
private static void quickSort(String[] a, int start, int end)
{
// index for the "left-to-right scan"
int i = start;
// index for the "right-to-left scan"
int j = end;
// only examine arrays of 2 or more elements.
if (j - i >= 1)
{
// The pivot point of the sort method is arbitrarily set to the first element int the array.
String pivot = a[i];
// only scan between the two indexes, until they meet.
while (j > i)
{
// from the left, if the current element is lexicographically less than the (original)
// first element in the String array, move on. Stop advancing the counter when we reach
// the right or an element that is lexicographically greater than the pivot String.
while (a[i].compareTo(pivot) < 0 && i <= end && j > i){
i++;
}
// from the right, if the current element is lexicographically greater than the (original)
// first element in the String array, move on. Stop advancing the counter when we reach
// the left or an element that is lexicographically less than the pivot String.
while (a[j].compareTo(pivot) > 0 && j >= start && j >= i){
j--;
}
// check the two elements in the center, the last comparison before the scans cross.
if (j > i)
swap(a, i, j);
}
// At this point, the two scans have crossed each other in the center of the array and stop.
// The left partition and right partition contain the right groups of numbers but are not
// sorted themselves. The following recursive code sorts the left and right partitions.
// Swap the pivot point with the last element of the left partition.
swap(a, start, j);
// sort left partition
quickSort(a, start, j - 1);
// sort right partition
quickSort(a, j + 1, end);
}
}
/**
* This method facilitates the quickSort method's need to swap two elements, Towers of Hanoi style.
*/
private static void swap(String[] a, int i, int j)
{
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
Ok, i was mistaken that it would work and found your tiny mistake.
Take a look at wikipedias pseudo code
You will notice that your conditions in the while loop are causing the error
if you change (a[i].compareTo(pivot) < 0 && i <= end && j > i) and (a[j].compareTo(pivot) > 0 && j >= start && j >= i) to
(a[i].compareTo(pivot) <= 0 && i < end && j > i) and (a[j].compareTo(pivot) >= 0 && j > start && j >= i).
这篇关于一个字符串数组使用快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
