Java 中使用 ArrayList 的基本冒泡排序
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/30951974/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Basic Bubble Sort with ArrayList in Java
提问by gummiBear
I was implementing a comparator, and it wasn't working, so I thought I'd write a basic bubble sort.
我正在实现一个比较器，但它不起作用，所以我想我会写一个基本的冒泡排序。
int[] numbers = { 5, 8, 14, 1, 5678 };
int tempVar;
for (int i = 0; i < numbers.length; i++)
{
for(int j = 0; j < numbers.length; j++)
{
if(numbers[i] > numbers[j + 1])
{
tempVar = numbers [j + 1];
numbers [j + 1]= numbers [i];
numbers [i] = tempVar;
}
}
}
for (int i = 0; i < numbers.length; i++)
{
System.out.println(numbers[i].toString());
}
Is this tutorial correct at all? https://blog.udemy.com/bubble-sort-java/
本教程完全正确吗？ https://blog.udemy.com/bubble-sort-java/
I followed the example and applied it to Last Names in an arraylist, but the results are a bit wack.
我按照示例将其应用于数组列表中的姓氏，但结果有点古怪。
String a;
String b;
Person c;
Person d;
for (int i=0; i< list.size(); i++){
for(int j=0; j< list.size()-1; j++){
a = list.get(i).getLastName();
b = list.get(j+1).getLastName();
c = list.get(i);
d = list.get(j+1);
if ( a.compareTo(b) < 0 ) {
Person temp = d;
list.set(j+1, c);
list.set(i, temp);
}
}
}
I'd really like to get a grip on a few methods (like figuring out why my comparator didn't work), but right now I'd just like to get a Bubble Sort to work correctly. Thanks.
我真的很想掌握一些方法（比如弄清楚为什么我的比较器不起作用），但现在我只想让冒泡排序正常工作。谢谢。
采纳答案by gummiBear
Thanks to everyone for pointing me in the right direction. One problem was I forgot to .trim() so compareTo wasn't working and neither was comparing with charAt(0).
感谢大家为我指明了正确的方向。一个问题是我忘记了 .trim() 所以 compareTo 不起作用，也没有与 charAt(0) 进行比较。
Also, I found a better implementation of loops for Bubble-Sort.
另外，我发现了一个更好的冒泡排序循环实现。
This is what now works:
这是现在的工作：
String a;
String b;
Person c;
Person d;
for (int i= 0; i< list.size() ; i++){
for(int j=0; j< list.size() - i-1; j++){
a = list.get(j).getLastName().toUpperCase().trim();
b = list.get(j+1).getLastName().toUpperCase().trim();
c = list.get(j);
d = list.get(j+1);
if ( a.compareTo(b) > 0) {
Person temp = d;
list.set(j+1, c);
list.set(j, temp);
}
}
回答by aakansha
In Bubble sort you need to compare only the adjacent elements and swap them(depending up on the condition).
在冒泡排序中，您只需要比较相邻元素并交换它们（取决于条件）。
If you are doing ascending order than comparing the adjacent elements and swap if(arr[j]>arr[j+1]).
This moves the largest elements to the end in the first iteration.Thus there are n-1iterations in outer loop to sort the array where n is the length of the array.
如果您正在执行升序而不是比较相邻元素和 swap if(arr[j]>arr[j+1])。这将在第一次迭代中将最大元素移动到末尾。因此n-1在外循环中有迭代来对数组进行排序，其中 n 是数组的长度。
Read this first Bubble sortas the tutorial you mentioned is completely wrong
阅读第一个冒泡排序，因为您提到的教程完全错误
Corrected code
更正的代码
for (int i = 0; i < numbers.length-1; i++)
{
for(int j = 0; j < numbers.length-i-1; j++)
{
if(numbers[j] > numbers[j + 1])
{
tempVar = numbers [j + 1];
numbers [j + 1]= numbers [j];
numbers [j] = tempVar;
}
}
}
Here is the working link
这是工作链接
回答by maraca
This is a strange and inefficient implementation, you compare each number which each other. Something like this is much more intuitive (could be improved a little performance-wise, but that is not the point, you will just save a lot of time not accidently making mistakes with the indices and if you really care about performance and not readability use mergesort or quicksort as Java does [Java is using quicksort for primitive types and mergesort for Objects, probably because for primitive types it doesn't matter if the algorithm is stable or not]):
这是一个奇怪且低效的实现，你比较每个数字。像这样的东西更直观（可以在性能方面稍微改进，但这不是重点，您将节省大量时间而不是意外地在索引上犯错，如果您真的关心性能而不是可读性，请使用归并排序或快速排序与 Java 一样[Java 对原始类型使用快速排序，对对象使用归并排序，可能是因为对于原始类型，算法是否稳定并不重要]）：
public void bubbleSort(int[] arr) {
boolean change;
do {
change = false;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
change = true;
}
}
} while (change);
}
Applied to your code (sorts ascending):
应用于您的代码（按升序排序）：
boolean change;
do {
change = false;
for (int i = 0; i < list.size() - 1; i++) {
c = list.get(i);
d = list.get(i + 1);
a = c.getLastName();
b = d.getLastName();
// add special comparison for null values if a or b can be null ("" is ok)
// toLowerCase() is to compare case-insensitive ('a' != 'A')
if (a.toLowerCase().compareTo(b.toLowerCase()) > 0) {
list.set(i, d);
list.set(i + 1, c);
change = true;
}
}
} while (change);
Sidenote: s.toUpperCase().compareTo(s.toLowerCase()) == 0would be trueif sonly contains symbols.
旁注：s.toUpperCase().compareTo(s.toLowerCase()) == 0是true，如果s只包含符号。
回答by rakeb.mazharul
If you write,
如果你写，
for(int j = 0; j < numbers.length; j++)
Then, you will get ArrayIndexOutOfBoundsExceptionfor the following line,
然后，您将获得ArrayIndexOutOfBoundsException以下行，
tempVar = numbers [j + 1];
Because, the array numbershas length 5with last index 4(as index starts from 0). So, when j = 4, the loop breaking condition j < numbers.lengthor 4 < 5is true, but you will get exception accessing numbers [4 + 1]index.
因为，数组的numbers长度5为最后一个索引4（因为索引从 开始0）。因此， when j = 4，循环中断条件j < numbers.lengthor 4 < 5is true，但您将获得访问numbers [4 + 1]索引的异常。
So try
所以试试
for(int j = 0; j < numbers.length -1; j++)
or
或者
for(int j = i; j < numbers.length -1; j++) // more efficient
Now for the second snippet of your code, can you tell me what exactly the problemyou get?
现在对于您的代码的第二个片段，您能告诉我您遇到的问题究竟是什么吗？
From a wildguess, your a.compareTo(b) < 0is not working like what you want.
从一个疯狂的猜测来看，您a.compareTo(b) < 0的工作并不像您想要的那样。
Note that compareToreturns a value less than 0 if string ais lexicographicallyless than the string b.
请注意，如果 string在字典序上小于string ，则compareTo返回一个小于 0 的值。ab
I'm confused what exactly you want, hence produces the following code which may help you to overcome your problem:
我很困惑你到底想要什么，因此产生以下代码可以帮助你克服你的问题：
import java.util.ArrayList;
public class Sort{
private static ArrayList<String> list = new ArrayList<String>();
public static ArrayList<String> sortByName(String [] input) {
String temp;
for (int i=0; i< input.length; i++){
for(int j= i; j< input.length-1; j++){
char first = input[i].charAt(0);
char sec = input[j +1].charAt(0);
if (first < sec) {
temp = input[j +1];
input[j +1] = input[i];
input[i] = temp;
}
}
list.add(input[i]);
}
return list;
}
public static void main(String[] args) {
String string[] = {"Ezen", "Allen" , "Wilker", "Kruden", "Crocket"};
bubbleSortByName(string);
}
}
Output is a listcontaining:
输出是一个list包含：
list = [Wilker, Kruden, Ezen, Crocket, Allen]
列表 = [Wilker、Kruden、Ezen、Crocket、Allen]
回答by Yagmur SAHIN
Bubble Sort Swap Printer in JAVA:
static void countSwaps(int[] a) {
int swaps = 0;
for(int i=0; i<a.length-1; i++){
for(int j=0; j<a.length-i-1; j++){
if (a[j] > a[j+1]){
int temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
swaps++;
}
}
}
System.out.println("Array is sorted in " + swaps +" swaps.");
}
回答by Balkrishna Rawool
There is a small problem with the sort program you used originally.
你最初使用的排序程序有一个小问题。
int j=0
should be
应该
int j=i
Also you didn't exactly replace it for string sorting.
你也没有完全替换它来进行字符串排序。
a.compareTo(b) < 0
should be
应该
a.compareTo(b) > 0
Check this:
检查这个：
import java.util.*;
public class HelloWorld{
public static void main(String[] args){
ArrayList<Person> list = new ArrayList<Person>();
list.add(new Person("xyz"));
list.add(new Person("abc"));
list.add(new Person("pqr"));
list.add(new Person("lmn"));
String a;
String b;
Person c;
Person d;
for (int i=0; i< list.size(); i++){
for(int j=i; j< list.size()-1; j++){
a = list.get(i).getLastName();
b = list.get(j+1).getLastName();
c = list.get(i);
d = list.get(j+1);
if ( a.compareTo(b) > 0 ) {
Person temp = d;
list.set(j+1, c);
list.set(i, temp);
}
}
}
for(Person person: list){
System.out.println(person.lastName);
}
}
}
class Person{
String lastName;
Person(String str){
lastName = str;
}
public String getLastName(){
return lastName;
}
}
