那个冒泡排序更快点？

Question

package test;import java.sql.SQLException;import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;public class Test {
private static Log log = LogFactory.getLog(Test.class); /**
 * @param args
 * @throws SQLException
 */
public static void main(String[] args) throws SQLException {
int[] arr1 = new int[]{45,6,45,457,345,3,45,34,6,7,6,7,436,86,346,634,23,4,23};
show1(arr1);
System.out.println();
int[] arr2 = new int[]{45,6,45,457,345,3,45,34,6,7,6,7,436,86,346,634,23,4,23};
show2(arr2);
}

public static void show1(int[] arr){
int count1 = 0;
int count2 = 0;
for(int i = 0;i < arr.length-1;i++){
for(int j = 0;j<arr.length-i-1;j++){
++count1;
if(arr[j]>arr[j+1]){
++count2;
arr[j] = arr[j] + arr[j+1];
arr[j+1] = arr[j] - arr[j+1];
arr[j] = arr[j] - arr[j+1];
}
}
}
System.out.println(count1);
System.out.println(count2);
for(int k = 0;k<arr.length;k++){
System.out.print(arr[k]+"\t");
}
}

public static void show2(int[] arr){
int count1 = 0;
int count2 = 0;
for(int i = 0;i < arr.length;i++){
for(int j = i+1;j<arr.length;j++){
++count1;
if(arr[i]>arr[j]){
++count2;
arr[i] = arr[i] + arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
}
}
System.out.println(count1);
System.out.println(count2);
for(int k = 0;k<arr.length;k++){
System.out.print(arr[k]+"\t");
}
}}第一个是学校教的，第二个是我自己想的（忘了，不知道是自己想的还是在哪里看的反正一直用的是第二个）
我测试的是第二个交换次数少。结果：
从小到大
171
81
3 4 6 6 6 7 7 23 23 34 45 45 45 86 345 346 436 457 634
171
61
3 4 6 6 6 7 7 23 23 34 45 45 45 86 345 346 436 457 634 从大到小
171
82
634 457 436 346 345 86 45 45 45 34 23 23 7 7 6 6 6 4 3
171
51
634 457 436 346 345 86 45 45 45 34 23 23 7 7 6 6 6 4 3

Answer 1

效率问题，指点一下，一是你程循环的次数，二是你判断的次数，我们知道两个方法都是针对数组操作的，那么效率是一样的。由此是不是知道了。循环中放if判断是相当消费效率的，那么if越少，就效率越快!

Answer 2

这两个的时间按复杂度都是o(n^2)的 
只是实现方式不太一样而已
我这里也给个冒泡的
不过在排序的过程中有些优化
特别的是当一个数组已经排好的话 时间复杂度就是 o(n)的了public static void bubbleSort(int... arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
temp = 0;
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
arr[j] ^= arr[j - 1];
arr[j - 1] ^= arr[j];
arr[j] ^= arr[j - 1];
temp++;
}
}
if(temp == 0){
break;
}
}
}

Answer 3

arr[j] = arr[j] + arr[j+1];
arr[j+1] = arr[j] - arr[j+1];
arr[j] = arr[j] - arr[j+1];这样交换是不正确的！

Answer 4

/**
 * 冒泡排序  
 */
public void BubbleUp(){
long save;
for (int i = 0; i < elems; i++) {
for (int j = elems-1; j > i; j--) {
if(a[j] > a[j-1]){
save = a[j];
a[j] = a[j-1];
a[j-1] = save;
}
}
}
display();
}
/**
 * 选择排序  
 */
public void selectionSort(){
int out,in,min;
long save;
for (out = 0; out < elems-1; out++) {
min = out;
for (in = out+1; inif(a[in] < a[min])
min = in;
}
save = a[out];
a[out] = a[min];
a[min] = save;
}
display();
}
/**
 * 插入算法
 */
public void insertAlgorithm(){
int in,out;
for (out = 0; out < elems; out++) {
long temp = a[out];
in = out;
while(in > 0 && a[in-1] <= temp){
a[in] = a[in-1];
--in;
}
a[in] = temp;
}
display();
}

Answer 5

一般来说
归并和快排是比较快
但归并比较浪费空间
对于一个有序的数组来说
插入和冒泡都是O(n)的时间复杂度
相反 快排却退化到了O(n^2)的时间复杂度
但常规下还是快排比较好吧
下边是5种常规排序，楼主可以看看
个人写的可能不好
有什么建议的话希望能给以提示// 递增
public static void bubbleSort(int... arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
temp = 0;
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
arr[j] ^= arr[j - 1];
arr[j - 1] ^= arr[j];
arr[j] ^= arr[j - 1];
temp++;
}
}
if(temp == 0){
break;
}
}
} public static void selectSort(int... arr) {
int temp;
for (int i = 0; i < arr.length - 1; i++) {
temp = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[temp]) {
temp = j;
}
}
if (temp == i)
continue;
arr[i] ^= arr[temp];
arr[temp] ^= arr[i];
arr[i] ^= arr[temp];
}
} public static void quickSort(int[] arr) {
innerQuickSort(arr, 0, arr.length - 1);
} private static void innerQuickSort(int[] arr, int head, int end) {
if (head >= end) {
return;
}
int index = head;
int temp = 0;
for (int i = head; i < end; i++) {
if (arr[i] <= arr[end]) {
temp = arr[index];
arr[index] = arr[i];
arr[i] = temp;
index++;
}
}
temp = arr[index];
arr[index] = arr[end];
arr[end] = temp;
innerQuickSort(arr, head, index - 1);
innerQuickSort(arr, index + 1, end);
}

public static void insertSort(int... arr)
{
int index, temp;
for(int i = 1; i < arr.length; i++)
{
index = i;
temp = arr[i];
while(index-- > 0 && arr[index] > temp);
for(int j = i; j > index + 1; j--)
{
arr[j] = arr[j - 1];
}
arr[index + 1] = temp; 
}
} public static void mergeSort(int... arr)
{
if(arr.length > 1)
{
int len1 = arr.length / 2;
int len2 = arr.length - len1;
int arr1[] = new int[len1];
int arr2[] = new int[len2];
for(int i = 0; i < len1; i++)
{
arr1[i] = arr[i];
}
for(int j = 0; j < len2; j++)
{
arr2[j] = arr[len1 + j];
}
mergeSort(arr1);
mergeSort(arr2);
int index1 = 0;
int index2 = 0;
int index = 0;
while(index1 < len1 && index2 < len2)
{
if(arr1[index1] < arr2[index2])
{
arr[index++] = arr1[index1++];
}
else
{
arr[index++] = arr2[index2++];
}
}
while(index1 < len1)
{
arr[index++] = arr1[index1++];
}
while(index2 < len2)
{
arr[index++] = arr2[index2++];
}
}
}

Answer 6

int a, b;
a = 100, b = 1000;
a ^= b ^= a ^= b;int a, b;
a = 100, b = 1000;
a += b -= a += b;